Python-Sets gegen Listen

187

Welche Datenstruktur ist in Python effizienter / schneller? Angenommen, diese Reihenfolge ist für mich nicht wichtig und ich würde sowieso nach Duplikaten suchen. Ist ein Python-Set langsamer als eine Python-Liste?

Mantas Vidutis
quelle

Antworten:

231

Es hängt davon ab, was Sie damit vorhaben.

Sätze sind erheblich schneller, wenn es darum geht, festzustellen, ob ein Objekt im Satz vorhanden ist (wie in x in s), aber langsamer als Listen, wenn es darum geht, über ihren Inhalt zu iterieren.

Mit dem timeit-Modul können Sie feststellen , welches für Ihre Situation schneller ist.

Michael Aaron Safyan
quelle
4
Für Ihren Punkt: "Sets sind deutlich schneller", was ist die zugrunde liegende Implementierung, die es schneller macht?
Überaustausch
Skriptsprachen verbergen gerne die zugrunde liegenden Implementierungen, aber diese scheinbare Einfachheit ist nicht immer gut. Sie benötigen ein gewisses Bewusstsein für die Datenstruktur, wenn Sie eine Software entwerfen.
Christophe Roussy
4
Set ist beim Iterieren nicht wesentlich langsamer als list.
Omerfarukdogan
38
Sätze und Listen haben beide eine lineare Zeititeration. Zu sagen, dass einer "langsamer" als der andere ist, ist falsch und hat neue Programmierer verwirrt, die diese Antwort lesen.
Hablabit
@habnabit, wenn Sie sagen, dass beide lineare Zeititeration haben. Bedeutet dies, dass sie dieselbe Iterationszeit haben? Was ist dann der Unterschied?
Mohammed Noureldin
152

Listen sind etwas schneller als Sätze, wenn Sie nur die Werte durchlaufen möchten.

Sets sind jedoch erheblich schneller als Listen, wenn Sie überprüfen möchten, ob ein Element darin enthalten ist. Sie können jedoch nur eindeutige Elemente enthalten.

Es stellt sich heraus, dass Tupel bis auf ihre Unveränderlichkeit fast genauso funktionieren wie Listen.

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

Stellen Sie 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
Ellis Percival
quelle
6
Ich habe festgestellt, dass (Initialisierungssatz -> 5.5300979614257812) (Initialisierungsliste -> 1.8846848011016846) (Initialisierungstupel -> 1.8730108737945557) Elemente der Größe 10.000 auf meinem Intel Core i5 Quad Core mit 12 GB RAM. Dies sollte ebenfalls berücksichtigt werden.
ThePracticalOne
4
Ich habe den Code aktualisiert, um die Objekterstellung jetzt zu entfernen. Die Setup-Phase der timeit-Schleifen wird nur einmal aufgerufen ( docs.python.org/2/library/timeit.html#timeit.Timer.timeit ).
Ellis Percival
7

Listenleistung:

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

Leistung einstellen:

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

Möglicherweise möchten Sie Tupel in Betracht ziehen, da sie Listen ähneln, aber nicht geändert werden können. Sie belegen etwas weniger Speicher 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.

Mengen sind ebenfalls Sequenzstrukturen, jedoch mit zwei Unterschieden zu Listen und Tupeln. Obwohl Sets 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.

setper Definition. [ Python | Wiki ].

>>> x = set([1, 1, 2, 2, 3, 3])
>>> x
{1, 2, 3}
user2601995
quelle
4
Zunächst sollten Sie auf den setintegrierten Typlink ( docs.python.org/2/library/stdtypes.html#set ) aktualisieren, nicht auf die veraltete setsBibliothek. Zweitens, "Mengen sind auch Sequenzstrukturen", lesen Sie Folgendes aus dem eingebauten Typ-Link: "Als ungeordnete Sammlung zeichnen Mengen weder die Elementposition noch die Einfügereihenfolge auf. Dementsprechend unterstützen Mengen keine Indizierung, Aufteilung oder andere sequenzartiges Verhalten. "
Seaux
7
rangeist nicht list. rangeist eine spezielle Klasse mit benutzerdefinierter __contains__magischer Methode.
Ryne Wang
@ RyneWang das ist wahr, aber nur für Python3. Im Python2-Bereich wird eine normale Liste zurückgegeben (deshalb gibt es schreckliche Dinge wie xrange)
Manoel Vilela
7

SetGewinne aufgrund nahezu sofortiger "enthält" Überprüfungen: https://en.wikipedia.org/wiki/Hash_table

Listenimplementierung : Normalerweise ein Array, niedrige Ebene in der Nähe des Metalls, gut für die Iteration und den wahlfreien Zugriff nach Elementindex.

Festlegen der Implementierung: https://en.wikipedia.org/wiki/Hash_table . Sie iteriert nicht in einer Liste, sondern findet das Element durch Berechnen eines Hashs aus dem Schlüssel. Dies hängt also von der Art der Schlüsselelemente und dem Hash ab Funktion. Ähnlich wie beim Diktieren. Ich vermute, es listkönnte schneller sein, wenn Sie nur sehr wenige Elemente haben (<5). Je größer die Anzahl der Elemente ist, desto besser ist die setLeistung für eine Prüfung der enthaltenen Daten. Es ist auch schnell zum Hinzufügen und Entfernen von Elementen. Denken Sie auch immer daran, dass der Bau eines Sets Kosten verursacht!

HINWEIS : Wenn das listbereits sortiert ist, kann die Suche listsehr schnell sein, aber in den üblichen Fällen setist a schneller und einfacher , wenn es Überprüfungen enthält.

Christophe Roussy
quelle
8
Nah am Metall? Was bedeutet das überhaupt im Kontext von Python? Wie ist eine Liste näher am Metall als ein Set?
Roganjosh
@roganjosh, Python läuft immer noch auf einem Computer und einige Implementierungen wie list als 'array' sind näher an dem, was die Hardware kann: stackoverflow.com/questions/176011/… , aber es hängt immer davon ab, was Sie erreichen möchten Es ist gut, ein bisschen über die Implementierungen zu wissen, nicht nur über die Abstraktionen.
Christophe Roussy
2

tl; dr

Datenstrukturen (DS) sind wichtig, da sie verwendet werden, um Operationen an Daten auszuführen, die im Wesentlichen Folgendes beinhalten: Nehmen Sie eine Eingabe , verarbeiten Sie sie und geben Sie die Ausgabe zurück .

Einige Datenstrukturen sind in bestimmten Fällen nützlicher als andere. Daher ist es ziemlich unfair zu fragen, welches (DS) effizienter / schneller ist. Es ist wie zu fragen, welches Werkzeug zwischen Messer und Gabel effizienter ist. Ich meine, alles hängt von der Situation ab.

Listen

Eine Liste ist eine veränderbare Sequenz , die normalerweise zum Speichern von Sammlungen homogener Elemente verwendet wird .

Sets

Ein festgelegtes Objekt ist eine ungeordnete Sammlung verschiedener hashbarer Objekte . Es wird häufig verwendet, um die Mitgliedschaft zu testen, Duplikate aus einer Sequenz zu entfernen und mathematische Operationen wie Schnittmenge, Vereinigung, Differenz und symmetrische Differenz zu berechnen.

Verwendung

Aus einigen Antworten geht hervor, dass eine Liste beim Durchlaufen der Werte viel schneller als eine Menge ist. Andererseits ist ein Satz schneller als eine Liste, wenn geprüft wird, ob ein Element darin enthalten ist. Daher können Sie nur sagen, dass eine Liste für bestimmte Operationen besser ist als ein Satz und umgekehrt.

lmiguelvargasf
quelle
2

Ich war an den Ergebnissen interessiert, als ich mit CPython überprüfte, ob ein Wert einer von wenigen Literalen ist. setgewinnt in Python 3 vs tuple, listund or:

from timeit import timeit

def in_test1():
  for i in range(1000):
    if i in (314, 628):
      pass

def in_test2():
  for i in range(1000):
    if i in [314, 628]:
      pass

def in_test3():
  for i in range(1000):
    if i in {314, 628}:
      pass

def in_test4():
  for i in range(1000):
    if i == 314 or i == 628:
      pass

print("tuple")
print(timeit("in_test1()", setup="from __main__ import in_test1", number=100000))
print("list")
print(timeit("in_test2()", setup="from __main__ import in_test2", number=100000))
print("set")
print(timeit("in_test3()", setup="from __main__ import in_test3", number=100000))
print("or")
print(timeit("in_test4()", setup="from __main__ import in_test4", number=100000))

Ausgabe:

tuple
4.735646052286029
list
4.7308746771886945
set
3.5755991376936436
or
4.687681658193469

Für 3 bis 5 Literale setgewinnt immer noch mit großem Abstand und orwird am langsamsten.

In Python 2 setist immer die langsamste. orist die schnellste für 2 bis 3 Literale tupleund listist mit 4 oder mehr Literalen schneller. Ich konnte die Geschwindigkeit von tuplevs nicht unterscheiden list.

Wenn die zu testenden Werte in einer globalen Variablen außerhalb der Funktion zwischengespeichert wurden, anstatt das Literal innerhalb der Schleife zu erstellen, wurde setjedes Mal gewonnen, selbst in Python 2.

Diese Ergebnisse gelten für 64-Bit-CPython auf einem Core i7.

Pedro Gimeno
quelle
0

Ich würde eine Set-Implementierung empfehlen, bei der der Anwendungsfall auf das Referenzieren oder Suchen nach Existenz beschränkt ist, und eine Tupel-Implementierung, bei der der Anwendungsfall erfordert, dass Sie eine Iteration durchführen. Eine Liste ist eine Implementierung auf niedriger Ebene und erfordert einen erheblichen Speicheraufwand.


quelle
1
In der Tat ist die richtige Unterscheidung zwischen der Verwendung von Sets und der Verwendung von Tuple von größter Bedeutung. Ich würde mir keine Sorgen über den damit verbundenen Speicheraufwand und die erforderlichen Footprints machen, es sei denn, ich skripte eine API auf niedrigerer Ebene.
0
from datetime import datetime
listA = range(10000000)
setA = set(listA)
tupA = tuple(listA)
#Source Code

def calc(data, type):
start = datetime.now()
if data in type:
print ""
end = datetime.now()
print end-start

calc(9999, listA)
calc(9999, tupA)
calc(9999, setA)

Ausgabe nach Vergleich von 10 Iterationen für alle 3: Vergleich

Harshal SG
quelle
0

Sätze sind schneller, außerdem erhalten Sie mehr Funktionen mit Sätzen, z. B. zwei Sätze:

set1 = {"Harry Potter", "James Bond", "Iron Man"}
set2 = {"Captain America", "Black Widow", "Hulk", "Harry Potter", "James Bond"}

Wir können leicht zwei Sätze verbinden:

set3 = set1.union(set2)

Finden Sie heraus, was in beiden gemeinsam ist:

set3 = set1.intersection(set2)

Finden Sie heraus, was in beiden Bereichen anders ist:

set3 = set1.difference(set2)

Und vieles mehr! Probieren Sie sie einfach aus, sie machen Spaß! Wenn Sie an den verschiedenen Werten in 2 Listen oder an gemeinsamen Werten in 2 Listen arbeiten müssen, ziehe ich es außerdem vor, Ihre Listen in Mengen umzuwandeln, und viele Programmierer tun dies auf diese Weise. Hoffe es hilft dir :-)

Shakhyar Gogoi
quelle