Python-Sets vs Listen

Question

In Python, welche Datenstruktur ist effizienter/schneller? Angenommen, diese Reihenfolge ist für mich nicht wichtig und ich würde trotzdem nach Duplikaten suchen, ist ein Python langsamer als eine Python-Liste?

Answer 1

Es hängt davon ab, was Sie damit machen wollen.

Sets sind wesentlich schneller, wenn es darum geht zu bestimmen, ob ein Objekt in der Menge vorhanden ist (wie in x in s), aber langsamer als Listen, wenn es um deren Inhalt geht.

Sie können die timeit module verwenden, um zu sehen, welche für Ihre Situation schneller ist.

Answer 2

Wenn Sie einige Werte speichern möchten, über die Sie iterieren, sind die Listenkonstrukte von Python etwas schneller. Wenn Sie jedoch (eindeutige) Werte speichern, um deren Existenz zu überprüfen, sind die Sätze wesentlich schneller.

Es stellt sich heraus, dass Tupel fast genauso funktionieren wie Listen, aber sie benötigen weniger Speicher, da sie nach der Erstellung nicht mehr geändert werden können (unveränderlich).

Iterieren

>>> def iter_test(iterable): 
...  for i in iterable: 
...   pass 
... 
>>> from timeit import timeit 
>>> timeit(
...  "iter_test(iterable)", 
...  setup="from __main__ import iter_test; iterable = set(range(10000))", 
...  number=100000) 
12.666952133178711 
>>> timeit(
...  "iter_test(iterable)", 
...  setup="from __main__ import iter_test; iterable = list(range(10000))", 
...  number=100000) 
9.917098999023438 
>>> timeit(
...  "iter_test(iterable)", 
...  setup="from __main__ import iter_test; iterable = tuple(range(10000))", 
...  number=100000) 
9.865639209747314 

fest, ob ein Objekt vorhanden ist

>>> def in_test(iterable): 
...  for i in range(1000): 
...   if i in iterable: 
...    pass 
... 
>>> from timeit import timeit 
>>> timeit(
...  "in_test(iterable)", 
...  setup="from __main__ import in_test; iterable = set(range(1000))", 
...  number=10000) 
0.5591847896575928 
>>> timeit(
...  "in_test(iterable)", 
...  setup="from __main__ import in_test; iterable = list(range(1000))", 
...  number=10000) 
50.18339991569519 
>>> timeit(
...  "in_test(iterable)", 
...  setup="from __main__ import in_test; iterable = tuple(range(1000))", 
...  number=10000) 
51.597304821014404 

Answer 3

Liste Leistung:

>>> import timeit 
>>> timeit.timeit(stmt='10**6 in a', setup='a = range(10**6)', number=100000) 
0.008128150348026608 

Set Leistung:

>>> timeit.timeit(stmt='10**6 in a', setup='a = set(range(10**6))', number=100000) 
0.005674857488571661 

Sie möchten Tupeln betrachten wie sie auf Listen ähnlich sind, aber nicht verändert werden. Sie benötigen etwas weniger Speicherplatz und sind schneller zugänglich. Sie sind nicht so flexibel, aber effizienter als Listen. Ihre normale Verwendung besteht darin, als Wörterbuchschlüssel zu dienen.

Sets sind auch Sequenzstrukturen, aber mit zwei Unterschieden zu Listen und Tupeln. Obwohl Mengen eine Reihenfolge haben, ist diese Reihenfolge willkürlich und nicht unter der Kontrolle des Programmierers. Der zweite Unterschied besteht darin, dass die Elemente in einer Menge eindeutig sein müssen.

set per definitionem. [python | wiki].

>>> x = set([1, 1, 2, 2, 3, 3]) 
>>> x 
{1, 2, 3} 

Answer 4

Set gewinnt aufgrund der Nähe von Instant 'enthält Checks: https://en.wikipedia.org/wiki/Hash_table

Liste Implementierung: in der Regel ein Array, niedriges Niveau nahe das Metall, gut für die Iteration und Direktzugriff durch Elementindex.

Set Umsetzung: https://en.wikipedia.org/wiki/Hash_table, es nicht auf einer Liste durchlaufen, findet aber das Element durch Berechnen eines Hash- aus dem Schlüssel, so dass es hängt von der Art der wichtigsten Elemente und die Hash-Funktion. Ähnlich wie bei dict.Ich vermute, list könnte schneller sein, wenn Sie sehr wenige Elemente haben (< 5), je größer Element zählen, desto besser die set wird für eine Prüfung durchführen. Es ist auch schnell für das Hinzufügen und Entfernen von Elementen.

HINWEIS: Wenn die list bereits sortiert ist, könnte die list Suche recht schnell sein, aber für den üblichen Fällen ein set ist schneller und einfacher für die Kontrolle enthält.