Python: Liste vs Dict für Nachschautabelle

Question

Ich habe über 10 Millionen Werte, die ich brauche von Nachschlagtabelle in irgendeiner Art zu setzen, so dass ich frage mich, was effizienter eine Liste oder dict sein würde?

Ich weiß, dass Sie so etwas wie dies für beides kann:

if something in dict_of_stuff: 
    pass 

und

if something in list_of_stuff: 
    pass 

Mein Gedanke ist, die dict wird schneller sein und effizienter zu gestalten.

Danke für Ihre Hilfe.

EDIT 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 bereits berechnet wurde.

EDIT 2
Effizienz zum Nachschlagen.

EDIT 3
Es sind keine Werte mit dem Wert assosiated ... so wäre ein Satz besser sein?

Answer 1

Geschwindigkeit

Lookups in Listen O (n), Lookups in der Wörterbuch amortisieren O (1), in Bezug auf die Anzahl der Elemente in die Datenstruktur. Wenn Sie keine Werte zuordnen müssen, verwenden Sie Sets.

Speicher

Beide Wörterbücher und Sätze benutzen Hashing und sie verwenden viel mehr Speicher als nur für Objektspeicher. Laut A.M. Kuchling in Beautiful Code, die Implementierung versucht, den Hash zu 2/3 voll zu halten, so dass Sie ziemlich viel Speicher verschwenden könnten.

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

Answer 2

wenn Daten sind einzigartig set() wird das effizienteste, aber zwei - dict (die auch Einzigartigkeit erfordert, oops :)

Answer 3

A dict ist eine Hash-Tabelle, so dass es wirklich schnell das finden Schlüssel. Also zwischen Diktat und Liste wäre das Diktat schneller. Aber wenn Sie keinen assoziativen Wert haben, ist es sogar 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 andere für die mit 89 beendeten Sequenzen. Ich habe dieses Problem mit Sets erfolgreich gelöst.

Answer 4

Sie wollen ein Diktat.

Für (unsortierte) Listen in Python, die Operation "in" benötigt O (n) Zeit --- nicht gut, wenn Sie eine große Menge an Daten haben. Ein dict hingegen ist eine Hash-Tabelle, so dass Sie O (1) Lookup-Zeit erwarten können.

Wie andere bemerkt haben, könnten Sie stattdessen einen Satz (einen speziellen Diktattyp) wählen, wenn Sie nur Schlüssel statt Schlüssel/Wert-Paare haben.

Verwandte:

• Python wiki: Informationen über die Zeitkomplexität von Python Container-Operationen.
• SO: Python Behälter Betriebszeit und Speicher Komplexitäten

Answer 5

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

Hinweis: Denken Sie daran, wie groß Ihr Ergebnis nach der ersten Quadratsummenoperation sein kann. Das größtmögliche Ergebnis wird viel kleiner als 10 Millionen sein ...

Answer 6

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

Answer 7

habe ich einige Benchmarking und es stellt sich heraus, dass dict schneller als beide Liste ist und für große Datenmengen eingestellt, läuft Python 2.7.3 auf einem i7 CPU auf Linux:

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

  10 Schleifen, am besten von 3: 64,2 msec pro Schleife

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

  10000000 Schleifen, am besten von 3: 0,075 9 usec pro Schleife

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

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

Wie Sie sehen können, dict ist wesentlich schneller als Liste und etwa 3-mal schneller als Set . In einigen Anwendungen möchten Sie vielleicht dennoch für die Schönheit der Umgebung wählen. Und wenn die Datensätze wirklich klein sind (< 1000 Elemente), funktionieren die Listen ziemlich gut.