Pourquoi les ensembles sont-ils plus rapides que les listes ?

Question

Le wiki python dit : "Les tests d'appartenance avec des ensembles et des dictionnaires sont beaucoup plus rapides, O(1), que la recherche de séquences, O(n). Lorsque vous testez "a dans b", b doit être un ensemble ou un dictionnaire plutôt qu'une liste ou un tuple."

J'utilise des ensembles à la place des listes chaque fois que la vitesse est importante dans mon code, mais dernièrement, je me suis demandé pourquoi les ensembles sont tellement plus rapides que les listes. Quelqu'un pourrait-il m'expliquer, ou m'indiquer une source qui le ferait, ce qui se passe exactement dans les coulisses de Python pour rendre les ensembles plus rapides ?

Answer 1

list : Imaginez que vous cherchez vos chaussettes dans votre placard, mais que vous ne savez pas dans quel tiroir se trouvent vos chaussettes, vous devez donc chercher tiroir par tiroir jusqu'à ce que vous les trouviez (ou peut-être que vous ne les trouvez jamais). C'est ce que nous appelons O(n) parce que, dans le pire des cas, vous allez regarder dans tous vos tiroirs (où n est le nombre de tiroirs).

set : Maintenant, imaginez que vous cherchez toujours vos chaussettes dans votre placard, mais que vous savez maintenant dans quel tiroir se trouvent vos chaussettes, disons dans le 3e tiroir. Donc, vous allez juste chercher dans le 3ème tiroir, au lieu de chercher dans tous les tiroirs. C'est ce que nous appelons O(1) car dans le pire des cas, vous ne regarderez que dans un seul tiroir.

Answer 2

Les ensembles sont mis en œuvre en utilisant tables de hachage . Chaque fois que vous ajoutez un objet à un ensemble, la position dans la mémoire de l'objet est modifiée. set est déterminé à l'aide du hachage de l'objet à ajouter. Lors du test d'appartenance, il suffit essentiellement de regarder si l'objet se trouve à la position déterminée par son hash, la vitesse de cette opération ne dépend donc pas de la taille de l'ensemble. Pour les listes, en revanche, il faut chercher dans toute la liste, ce qui devient plus lent au fur et à mesure que la liste grandit.

C'est également la raison pour laquelle les ensembles ne préservent pas l'ordre des objets que vous ajoutez.

Notez que les ensembles ne sont pas plus rapides que les listes en général - le test d'appartenance est plus rapide pour les ensembles, tout comme la suppression d'un élément. Tant que vous n'avez pas besoin de ces opérations, les listes sont souvent plus rapides.

Answer 3

Je pense que vous devriez lire un livre sur les structures de données. En gros, les listes Python sont implémentées en tant que réseaux dynamiques et les ensembles sont mis en œuvre comme un tables de hachage .

La mise en œuvre de ces structures de données leur confère des caractéristiques radicalement différentes. Par exemple, une table de hachage a un temps de consultation très rapide mais ne peut pas préserver l'ordre d'insertion.

Answer 4

Bien que je n'aie pas encore mesuré quoi que ce soit en matière de performances en python, j'aimerais tout de même souligner que les listes sont souvent plus rapides.

Oui, vous avez O(1) contre O(n). Mais rappelez-vous toujours que cela ne donne des informations que sur le comportement asymptotique de quelque chose. Cela signifie que si votre n est très élevé, O(1) sera toujours plus rapide - en théorie. En pratique, cependant, n doit souvent être beaucoup plus grand que votre ensemble de données habituel.

Les ensembles ne sont donc pas plus rapides que les listes en soi, mais seulement si vous devez manipuler un grand nombre d'éléments.

Answer 5

list : Imaginez que vous cherchez votre stylo, mais que vous ne savez pas dans quel tiroir se trouve votre stylo, vous devez donc chercher tiroir par tiroir jusqu'à ce que vous le trouviez (ou peut-être que vous ne le trouvez jamais). C'est ce qu'on appelle O(n), car dans le pire des cas, vous allez chercher dans tous vos tiroirs (où n est le nombre de tiroirs).

set : Maintenant, imaginez que vous cherchez toujours votre stylo, mais que vous savez maintenant dans quel tiroir se trouve votre stylo, disons dans le 8ème tiroir. Donc, vous allez juste chercher dans le 8ème tiroir, au lieu de chercher dans tous les tiroirs. C'est ce que nous appelons O(1), car dans le pire des cas, vous ne chercherez que dans un seul tiroir.

Fondamentalement, Python listes sont mises en œuvre comme dynamic arrays et fixe sont mises en œuvre en tant que hash tables .