recherche d'un element dans liste de liste

Bonjour,

J’ai un programme python et je voulais avoir vos avis sur la meilleure manière de faire une recherche d’un élément dans une liste de liste.

Je possède une liste (qu’on appellera l), contenant des listes d’entiers, typiquement :

1

l = [[1, 2, 3, 4, 5, 6, 7, 8], [0, 2, 5, 9], [0, 1, 5, 6, 7, 8, 9], [0, 4, 6, 7], [0, 3, 6, 7, 8], [0, 1, 2, 6, 7], [0, 2, 3, 4, 5, 7, 8, 9], [0, 2, 3, 4, 5, 6, 8], [0, 2, 4, 6, 7, 9], [1, 2, 6, 8]]

(dans le vrai programme elle peut être beaucoup plus longue)

Ma question est, sachant que cette liste est vouée à être modifiée plusieurs fois pendant l’exécution du programme, quelle serait la meilleur solution pour tester la présence d’un entier dans l ?

J’ai pensé à deux solutions :

• une flatten list : le but est de pouvoir faire elem in l jusqu’ici, list(itertools.chain.from_iterable(l)) donne de bons résultats, mais il faudrait recréer la liste à chaque fois que l est modifiée.
• un double boucle for

En gardant à l’esprit que l sera modifiée plusieurs fois, j’aimerais savoir quelle solution est la plus rapide (l’une des deux ci-dessus, ou carrément autre chose ?)

Merci de m’avoir lu.

Bonjour,

Quand tu parles de faire une recherche, tu veux récupérer l’index de l’élément, ou juste savoir si un tel élément existe dans l’une des listes ?

Je veux pouvoir obtenir un booléen, exactement comme si je faisais elem in l.

Pourquoi double ?

Tu peux pas simplement boucler sur l, et sur chaque élément jusqu’à ce que tu trouves ou que la boucle termine, faire n in sublist ?

C’est vrai que la double boucle for était plus un réflexe naïf qu’autre chose. Je vais tester pour comparer le temps entre ta solution et le itertools, mais ça m’a l’air prometteur.

Je vois mal comment ta solution à base d’itertools pourrait être plus performantes en temps ou en espace.

Si tu mesures, je veux bien voir les chiffres auxquels tu arrives !

Je ferai alors ça avec in et any. C’est plus court et plus élégant.

1

any(n in sublist for sublist in l)

@Victor : Ta solution m’a l’air environ 2 à 3 fois plus rapide que le itertools.

@entwanne : Je ne connais pas any, je vais aller regarder ça.

Merci à vous deux pour vos réponses rapides.

J’ai utilisé une liste plus longue pour le test.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import random
import itertools
import time

ELEM = 10


l = [[1, 3, 6, 10, 11, 14, 15, 16, 18, 19, 21, 23, 27, 29, 31, 34, 37, 38, 39, 44, 45, 49], [0, 3, 5, 7, 8, 9, 10, 12, 15, 16, 17, 18, 24, 26, 28, 30, 31, 34, 35, 36, 37, 38, 40, 44, 47, 49], [4, 5, 10, 11, 12, 13, 15, 19, 22, 23, 25, 26, 29, 31, 34, 35, 36, 38, 39, 41, 46, 48, 49], [0, 1, 4, 6, 7, 8, 10, 12, 13, 17, 20, 21, 22, 26, 30, 31, 36, 37, 38, 39, 40, 41, 43, 47, 49], [2, 3, 6, 8, 11, 15, 18, 22, 24, 25, 26, 27, 29, 30, 31, 32, 33, 34, 35, 38, 39, 41, 42, 45, 47, 49], [1, 2, 6, 9, 10, 11, 12, 14, 16, 18, 20, 21, 22, 26, 28, 29, 30, 31, 32, 34, 37, 38, 39, 40, 42, 43, 44, 45, 46, 48, 49], [0, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13, 20, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 36, 37, 38, 42, 43, 45, 48], [1, 3, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 19, 21, 22, 23, 24, 27, 29, 32, 33, 35, 36, 37, 46, 48], [1, 3, 4, 6, 7, 9, 10, 11, 14, 15, 16, 18, 21, 24, 25, 26, 28, 30, 31, 32, 33, 34, 39, 41, 43, 46, 47, 48, 49], [1, 5, 6, 7, 8, 10, 12, 14, 15, 16, 17, 18, 20, 22, 24, 25, 27, 30, 31, 33, 38, 40, 41, 44, 48, 49], [0, 1, 2, 3, 5, 6, 7, 8, 9, 11, 12, 14, 15, 16, 18, 19, 20, 22, 23, 26, 30, 31, 32, 34, 35, 37, 38, 39, 41, 44, 45, 46, 48], [0, 2, 4, 5, 6, 7, 8, 10, 12, 14, 15, 16, 17, 19, 21, 23, 24, 25, 31, 32, 34, 38, 43, 44, 45, 46, 47, 48, 49], [1, 2, 3, 5, 6, 7, 9, 10, 11, 14, 15, 17, 19, 20, 21, 22, 23, 27, 32, 33, 35, 39, 41, 43, 44, 45, 49], [2, 3, 6, 7, 14, 15, 17, 18, 19, 21, 24, 25, 29, 30, 31, 33, 36, 39, 40, 41, 42, 43, 46, 49], [0, 5, 7, 8, 9, 10, 11, 12, 13, 17, 19, 21, 23, 24, 26, 28, 36, 41, 44, 45, 46, 47, 49], [0, 1, 2, 4, 7, 8, 9, 10, 11, 12, 13, 16, 17, 20, 22, 27, 28, 32, 33, 34, 35, 36, 41, 43, 46, 47, 48], [0, 1, 5, 7, 8, 9, 10, 11, 15, 21, 23, 28, 29, 30, 31, 32, 35, 38, 39, 40, 41, 42, 43, 49], [1, 3, 7, 9, 11, 12, 13, 14, 15, 18, 19, 22, 23, 24, 27, 30, 31, 32, 33, 37, 43], [0, 1, 4, 5, 8, 9, 10, 13, 17, 19, 23, 24, 25, 33, 34, 35, 38, 41, 42, 44, 45, 46, 47, 49], [0, 2, 7, 10, 11, 12, 13, 14, 17, 18, 21, 23, 25, 29, 30, 31, 32, 33, 35, 40, 41, 44, 46, 48, 49], [3, 5, 6, 9, 10, 12, 15, 21, 22, 24, 25, 27, 31, 33, 34, 35, 38, 40, 43, 47, 48], [0, 3, 5, 6, 7, 8, 11, 12, 13, 14, 16, 19, 20, 22, 24, 25, 27, 28, 29, 30, 31, 36, 39, 42, 43, 44, 47], [2, 3, 4, 5, 6, 7, 9, 10, 12, 15, 17, 20, 21, 24, 25, 26, 28, 31, 32, 36, 37, 38, 39, 40, 41, 42, 44, 46, 47, 48], [0, 2, 6, 7, 10, 11, 12, 14, 16, 17, 18, 19, 25, 28, 30, 33, 35, 36, 39, 40, 41, 42, 43], [1, 4, 7, 8, 9, 11, 13, 14, 17, 18, 20, 21, 22, 25, 26, 32, 33, 34, 39, 40, 41, 42, 45, 46, 47, 48, 49], [2, 4, 6, 8, 9, 11, 13, 18, 19, 20, 21, 22, 23, 24, 26, 27, 28, 29, 32, 35, 36, 37, 44, 46, 47], [1, 2, 3, 4, 5, 6, 8, 10, 14, 22, 24, 25, 27, 28, 29, 34, 35, 38, 39, 41, 44, 48], [0, 4, 7, 9, 12, 15, 17, 20, 21, 25, 26, 29, 30, 32, 34, 35, 36, 37, 38, 41, 43, 44, 45, 48], [1, 5, 8, 14, 15, 16, 21, 22, 23, 25, 26, 30, 33, 34, 36, 38, 43, 44, 48], [0, 2, 4, 5, 6, 7, 13, 16, 19, 21, 25, 26, 27, 30, 33, 40, 43, 44, 49], [1, 3, 4, 5, 8, 9, 10, 13, 16, 17, 19, 21, 23, 27, 28, 29, 36, 38, 39, 40, 44, 46], [0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 13, 16, 17, 19, 20, 21, 22, 32, 36, 37, 42, 46, 49], [4, 5, 7, 8, 10, 11, 12, 15, 16, 17, 19, 22, 24, 25, 27, 31, 33, 38, 39, 41, 42, 43, 45, 46, 47, 49], [4, 6, 7, 8, 9, 12, 13, 15, 17, 18, 19, 20, 23, 24, 28, 29, 32, 35, 39, 47, 48, 49], [0, 1, 2, 4, 5, 6, 8, 10, 11, 15, 18, 20, 24, 26, 27, 28, 36, 37, 38, 39, 44, 48], [1, 2, 4, 6, 7, 10, 12, 15, 16, 18, 19, 20, 23, 25, 26, 27, 33, 36, 38, 45, 46, 47, 49], [1, 2, 3, 6, 7, 13, 14, 15, 21, 22, 23, 25, 27, 28, 30, 31, 34, 35, 44, 45, 47, 48], [0, 1, 3, 5, 6, 7, 10, 17, 22, 25, 27, 31, 34, 39, 40, 41, 45, 47], [0, 1, 2, 3, 4, 5, 6, 9, 10, 11, 16, 18, 20, 22, 26, 27, 28, 30, 32, 34, 35, 41, 44, 45], [0, 2, 3, 4, 5, 8, 10, 12, 13, 16, 21, 22, 23, 24, 26, 30, 32, 33, 34, 37, 44, 46, 47, 48], [1, 3, 5, 9, 13, 16, 19, 20, 22, 23, 24, 29, 30, 37, 44, 45, 48, 49], [2, 3, 4, 8, 9, 10, 12, 13, 14, 15, 16, 18, 19, 22, 23, 24, 26, 27, 32, 37, 38, 43, 45, 46, 48, 49], [4, 5, 6, 13, 16, 18, 21, 22, 23, 24, 31, 32, 45, 48, 49], [3, 5, 6, 8, 11, 12, 13, 15, 16, 17, 20, 21, 23, 27, 28, 29, 32, 41, 44, 47, 48, 49], [0, 1, 5, 9, 10, 11, 12, 14, 18, 19, 21, 22, 25, 26, 27, 28, 29, 30, 34, 36, 38, 39, 40, 43, 46, 48, 49], [0, 4, 5, 6, 10, 11, 12, 14, 18, 24, 27, 32, 35, 36, 37, 38, 40, 41, 42, 46, 48], [2, 5, 7, 8, 10, 11, 13, 14, 15, 18, 19, 22, 24, 25, 30, 31, 32, 35, 39, 41, 44, 45, 47], [1, 3, 4, 8, 11, 14, 15, 18, 20, 21, 22, 24, 25, 32, 33, 35, 36, 37, 39, 43, 46, 49], [2, 5, 6, 7, 8, 9, 10, 11, 15, 19, 20, 22, 24, 26, 27, 28, 33, 34, 36, 39, 40, 41, 42, 43, 44, 45], [0, 1, 2, 3, 4, 5, 8, 9, 11, 12, 13, 14, 16, 18, 19, 24, 29, 31, 32, 33, 35, 40, 41, 42, 43, 44, 47]]

def ajout_sublist(l):
    longueur = random.randint(0, ELEM)
    sublist = [0]*longueur
    sublist = [ random.randint(0, ELEM-1) for k in sublist ]
    l.append(sublist)

def test_elem_sublist_1(l, n):
    for k in l:
        if n in k:
            return True
    return False

def test_elem_sublist_2(l, n):
    l = list(itertools.chain.from_iterable(l))
    return n in l

def test_elem_sublist_3(l, n):
    return any(n in sublist for sublist in l)

if __name__ == "__main__":
    t1 = time.time()
    for k in range(100):
        test_elem_sublist_1(l, ELEM)
        ajout_sublist(l)
    t2 = time.time()
    print("t2-t1 : ", t2-t1)

    t3 = time.time()
    for k in range(100):
        test_elem_sublist_2(l, ELEM)
        ajout_sublist(l)
    t4 = time.time()
    print("t4-t3 : ", t4-t3)

    t5 = time.time()
    for k in range(100):
        test_elem_sublist_3(l, ELEM)
        ajout_sublist(l)
    t6 = time.time()
    print("t6-t5 : ", t6-t5)

Remarque :

• ajout_sublist est une fonction qui simule les opérations effectuées par le programme pendant l’execution, en soit elle rajoute juste une sous liste à l (la taille de cette sous-liste importe peu, par contre je fais en sorte que cette sous-liste ne contienne pas ELEM ici pour rester dans un cas défavorable)

Pour ELEM = 10 : (4eme élément de la 1ere sous-liste)

t2-t1 : 0.001001119613647461

t4-t3 : 0.004011869430541992

t6-t5 : 0.0010030269622802734

Pour ELEM = 50 : (le pire cas possible, 50 n’étant pas présent dans l)

t2-t1 : 0.004003047943115234

t4-t3 : 0.008005142211914062

t6-t5 : 0.007004976272583008

Conclusion :

Itertools est donc dernier, et la solution de Victor semble plus rapide que any pour des listes longues.

Tes tests ne sont absolument pas rigoureux : ta liste n’est pas réinitialisée à chaque nouveau test.

l contient 50 éléments avant le premier test, 150 avant le deuxième, et 250 avant le 3ème. Ils ne sont pas réalisés dans les mêmes conditions.

Et sinon, il y a le module timeit pour réaliser ce genre de mesures.

Les temps de la première et de la troisième solution sont en fait équivalents.

Sans surprise pour ma part, et je suppose que tu t’y attendais à 100% aussi. C’est toi l’expert Python du coup corrige-moi si je dis des bêtises :

Nos solutions sont théoriquement strictement équivalentes* puisque je break et que tu utilises any qui court-circuite ?

* je dis "théoriquement" parce que je m’attends à ce qu’elles se comportent exactement de la même façon, la tienne est plus élégante amha

[edit]

En fait j’adorerais que quelqu’un qui passe par là prenne cet exemple pour écrire un petit billet montrant les bytecodes respectifs de ces deux solutions, et les comparant si ça a lieu d’être.

Oui, sans surprise.

Il peut juste y avoir un léger surcoût, parce que dans le cas de any, il y a un appel de fonction.

Il serait assez difficile d’en tirer quelque chose, justement parce que le bytecode ne montrerait qu’un appel à la builtin any, dont le code est probablement écrit en C dans CPython.

Effectivement, l’erreur était très bête de ma part.

Par contre, n’ayant jamais utilisé timeit, j’ai un peu de mal à savoir comment le faire fonctionner avec mon programme.

Edit :

Finalement j’ai utilisé le %timeit de ipython.

• Solution de Victor : 1000 loops, best of 3: 1.04 ms per loop
• Solution itertools : 1 loop, best of 3: 9.14 s per loop
• Solution entwanne  : 1000 loops, best of 3: 1.09 ms per loop

Salut,

Même si ça ne te servira peut être pas pour ce problème, ça peut t’intéresser pour la suite. Si tu testes l’appartenance de beaucoup de chiffres entre deux réorganisations de la liste (ou si les réorganisations ne contiennent que des ajouts et pas de retrait), tu as peut être intérêt à construire plutôt un set et tester l’appartenance sur le set.

Tu auras un coût en temps et espace en $O(n)$ à la création du set, mais chaque test d’appartenance se fera en temps constant.

Et si tu as beaucoup beaucoup d’éléments et peu d’espace (disque, RAM, bande passante limitée, etc), l’idéal en terme de tests d’appartenance est un Bloom filter ou un golomb-coded set (plus compact mais plus coûteux).

Cette fois, on a vraiment fait le tour du sujet !

entwanne : intéressant, merci !

@adri1 :

J’ai testé rapidement les sets, mais apparemment on ne peut pas faire de structures imbriquées (set de sets). Le temps constant reste intéressant et je note l’idée.

@Victor :

J’ai zieuté les pages wikipedia et j’ai trouvé le Filtre Bloom intéressant, même si je ne pense pas l’utiliser dans ce projet. En ce qui concerne le golomb-coded set je regarderais de manière plus approfondie plus tard, parce que je ne sais pas ce qu’est le codage unaire et binaire tronqué.

Tu n’as peut-être pas saisi tout l’intérêt, mais ce sont les nombres qui peuvent être stockés dans un set. Tu aurais ensuite une liste de sets.

Ça permet d’optimiser l’opération in, que tu fais sur les sous-listes. Tu ne fais pas de in sur la liste principale.

Ah oui, effectivement, je n’y avais pas pensé.

Mais je pense que ça reste non applicable ici, car l’ordre des nombres dans les sous-listes est important, or le set n’est pas ordonné si je ne dis pas de bêtise (Il se trouve que dans les exemples utilisés jusqu’ici les sous-listes étaient composées de nombres dans un ordre croissant mais dans le programme ça ne sera pas forcément le cas).

Tu n’as peut-être pas saisi tout l’intérêt, mais ce sont les nombres qui peuvent être stockés dans un set. Tu aurais ensuite une liste de sets.

Ben non, pour tirer avantage du set il faut faire un seul set de nombres (un peu comme la liste applatie dans l’OP), et faire le in sur le set global. Mais évidemment, ça ne présente un avantage que si il y a plusieurs tests effectués sur la même liste de listes (ou bien que seuls des ajouts simples sont faits sur cette liste de listes, auquel cas il suffit d’étendre le set, si il y a aussi des retraits simples il vaudrait mieux partir sur un Counter, si la liste est modifiée énormément entre deux tests, le coût de construction rend probablement l’idée mauvaise).

Euh, oui, plutôt

Je remarque que tes listes sont toutes monotones.

Du coup, peut-être qu’un quick-search pourrait être implémenté ?

Le gain me semble potentiellement important si les listes ne sont pas trop petites.

Oui bon alors du coup, j’avais pas fini de lire tous les posts. Si les listes n’ont aucune organisation particulière alors toute optimisation ne serra que minime.

Pour bien répondre à ta question, on aurait besoin d’avoir, un ordre de grandeur de la taille des listes, du nombre de listes, des nombres dans les listes ainsi que si possible des informations sur le nombre de modifications entre chaque vérification.

Par exemple si les testes sont très fréquent par rapport aux modifications, la mise en place d’un cache pourrait être envisagé. Par-contre si les vérifications sont très peu nombreuses par rapport aux autres traitements, il faudrait savoir si ça vaut vraiment le coup de perdre du temps à chaque modification pour optimiser la vérification.