Python-Sets gegen Listen

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?

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.

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

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}

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.

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.

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.

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.

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

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 :-)