Ich habe ungefähr 10 Millionen Werte, die ich in eine Art Nachschlagetabelle einfügen muss, also habe ich mich gefragt, welche Liste oder Diktat effizienter wäre .

Ich weiß, dass Sie so etwas für beide tun können:

if something in dict_of_stuff:
    pass

und

if something in list_of_stuff:
    pass

Mein Gedanke ist, dass das Diktat schneller und effizienter sein wird.

Danke für Ihre Hilfe.

BEARBEITEN 1
Wenig mehr Informationen darüber, was ich versuche zu tun. Euler Problem 92 . Ich mache eine Nachschlagetabelle, um zu sehen, ob ein berechneter Wert fertig berechnet wurde.

EDIT 2
Effizienz zum Nachschlagen.

EDIT 3
Es gibt keine Werte, die mit dem Wert verknüpft sind. Wäre eine Menge also besser?

Geschwindigkeit

Suchvorgänge in Listen sind O (n), Suchvorgänge in Wörterbüchern werden in Bezug auf die Anzahl der Elemente in der Datenstruktur mit O (1) abgeschrieben. Wenn Sie keine Werte zuordnen müssen, verwenden Sie Mengen.

Erinnerung

Sowohl Wörterbücher als auch Mengen verwenden Hashing und viel mehr Speicher als nur zur Objektspeicherung. Laut AM Kuchling in Beautiful Code versucht die Implementierung, den Hash 2/3 voll zu halten, sodass Sie möglicherweise viel Speicherplatz verschwenden.

Wenn Sie keine neuen Einträge im laufenden Betrieb hinzufügen (was Sie basierend auf Ihrer aktualisierten Frage tun), kann es sich lohnen, die Liste zu sortieren und die binäre Suche zu verwenden. Dies ist O (log n) und ist wahrscheinlich langsamer für Zeichenfolgen, unmöglich für Objekte, die keine natürliche Reihenfolge haben.

Ein Diktat ist eine Hash-Tabelle, daher ist es sehr schnell, die Schlüssel zu finden. Zwischen Diktat und Liste wäre Diktat also schneller. Wenn Sie jedoch keinen zu verknüpfenden Wert haben, ist es noch besser, einen Satz zu verwenden. Es ist eine Hash-Tabelle ohne den Teil "Tabelle".

EDIT: Für Ihre neue Frage, JA, wäre ein Satz besser. Erstellen Sie einfach 2 Sätze, einen für Sequenzen, die mit 1 enden, und einen für Sequenzen, die mit 89 enden. Ich habe dieses Problem mit Sätzen erfolgreich gelöst.

set()ist genau das, was Sie wollen. O (1) Lookups und kleiner als ein Diktat.

Ich habe ein Benchmarking durchgeführt und es stellte sich heraus, dass Diktat schneller ist als sowohl Liste als auch Satz für große Datenmengen, wobei Python 2.7.3 auf einer i7-CPU unter Linux ausgeführt wird:

• python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

  10 Schleifen, am besten 3: 64,2 ms pro Schleife

• python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

  10000000 Schleifen, am besten 3: 0,0759 usec pro Schleife

• python -mtimeit -s 'from sets import Set; d=Set(range(10**7))' '5*10**6 in d'

  1000000 Schleifen, am besten 3: 0,262 usec pro Schleife

Wie Sie sehen können, ist das Diktat erheblich schneller als die Liste und etwa dreimal schneller als das eingestellte. In einigen Anwendungen möchten Sie möglicherweise dennoch ein Set für die Schönheit auswählen. Und wenn die Datensätze wirklich klein sind (<1000 Elemente), funktionieren Listen ziemlich gut.

Du willst ein Diktat.

Für (unsortierte) Listen in Python benötigt die "in" -Operation O (n) Zeit - nicht gut, wenn Sie über eine große Datenmenge verfügen. Ein Diktat ist dagegen eine Hash-Tabelle, sodass Sie mit einer O (1) -Nachschlagzeit rechnen können.

Wie andere angemerkt haben, können Sie stattdessen eine Menge (eine spezielle Art von Diktat) auswählen, wenn Sie nur Schlüssel anstelle von Schlüssel / Wert-Paaren haben.

Verbunden:

• Python-Wiki : Informationen zur zeitlichen Komplexität von Python-Containeroperationen.
• SO : Betriebszeit des Python-Containers und Komplexität des Speichers

Wenn die Daten eindeutig sind, ist set () am effizientesten, aber von zwei - dikt (was auch Eindeutigkeit erfordert, oops :)

Als neue Testreihe zeigt @ EriF89 nach all den Jahren immer noch:

$ python -m timeit -s "l={k:k for k in xrange(5000)}"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.84 msec per loop
$ python -m timeit -s "l=[k for k in xrange(5000)]"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 573 msec per loop
$ python -m timeit -s "l=tuple([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
10 loops, best of 3: 587 msec per loop
$ python -m timeit -s "l=set([k for k in xrange(5000)])"    "[i for i in xrange(10000) if i in l]"
1000 loops, best of 3: 1.88 msec per loop

Hier vergleichen wir auch a tuple, von denen bekannt ist, dass sie listsin einigen Anwendungsfällen schneller als (und weniger Speicher) sind. Im Falle der Nachschlagetabelle ist die tupleVerkleidung nicht besser.

Sowohl die dictals setauch sehr gut. Dies wirft einen interessanten Punkt auf, der mit der @ SilentGhost-Antwort zur Eindeutigkeit zusammenhängt: Wenn das OP 10 Millionen Werte in einem Datensatz enthält und nicht bekannt ist, ob Duplikate darin enthalten sind, lohnt es sich, einen Satz / ein Diktat seiner Elemente parallel zu halten mit dem tatsächlichen Datensatz und Testen auf Existenz in diesem Satz / Diktat. Es ist möglich, dass die 10 Millionen Datenpunkte nur 10 eindeutige Werte haben, was einen viel kleineren Platz zum Suchen darstellt!

Der Fehler von SilentGhost in Bezug auf Diktate ist tatsächlich aufschlussreich, da man ein Diktat verwenden könnte, um doppelte Daten (in Werten) zu einem nicht duplizierten Satz (Schlüssel) zu korrelieren und somit ein Datenobjekt zu behalten, um alle Daten zu speichern, und dennoch schnell als Nachschlagetabelle zu sein. Ein Diktatschlüssel könnte beispielsweise der Wert sein, nach dem gesucht wird, und der Wert könnte eine Liste von Indizes in einer imaginären Liste sein, in der dieser Wert aufgetreten ist.

Wenn beispielsweise die zu durchsuchende Quelldatenliste war l=[1,2,3,1,2,1,4], könnte sie sowohl für die Suche als auch für den Speicher optimiert werden, indem sie durch dieses Diktat ersetzt wird:

>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> l=[1,2,3,1,2,1,4]
>>> for i, e in enumerate(l):
...     d[e].append(i)
>>> d
defaultdict(<class 'list'>, {1: [0, 3, 5], 2: [1, 4], 3: [2], 4: [6]})

Mit diesem Diktat kann man wissen:

1. Wenn sich ein Wert im Originaldatensatz befand (dh 2 in dzurückgegeben wird True)
2. Wo der Wert in dem ursprünglichen Datensatz war (dh d[2]zurückgibt Liste des Indizes , wo Daten wurden in Originaldatenliste gefunden: [1, 4])

Sie müssen nicht unbedingt 10 Millionen Werte in der Tabelle speichern, es ist also auch keine große Sache.

Tipp: Überlegen Sie, wie groß Ihr Ergebnis nach der ersten Quadratsumme sein kann. Das größtmögliche Ergebnis wird viel kleiner als 10 Millionen sein ...