Lesegeschwindigkeit: Dict vs. List

[Krauzi]

Hihohallo,

ich habe ein dict angelegt, das etwa 52*(8+6) = 728 einträge hat.
Wenn ich jetzt eine abfrage mache:

Code: Alles auswählen

for eintrag in dict:
       myfunction( eintrag )

ist das jetzt genauso schnell, wie wenn ich nur die 52 einträge in einer liste hätte (ohne die zusätlichen bezeichnungen der einträge in dem dict)?

Ich vermute, dass die nichts zur sachen tun, denn schließlich werden die ja nicht bearbeitet. Aber sicher bin ich mir nicht, deshalb frage ich hier nochmal nach.

MfG Krauzi

[BlackJack]

@Krauzi: Ich bin mir nicht ganz sicher, ob ich verstehe was Du da an Daten hast. Eine Schleife über ~700 Objekte ist aller Wahrscheinlichkeit langsamer als eine über nur ~50 Objekte. Die Schleife wird ja 14× öfter durchlaufen.

Wenn es gleich viele Durchläufe sind, dann würde ich mich nicht damit aufhalten `dict`\s mit `list`\en zu vergleichen, weil da höchstwahrscheinlich sowieso die Laufzeit der Operation in der Schleife dominieren wird, bzw. ein Laufzeitunterschied des reinen Iterierens sehr stark von der Implementierung von `dict` und `list` abhängen dürfte. Wenn man da Laufzeitmessungen macht, muss man also immer dazu sagen, welche Implementierung man gemessen hat.

[Krauzi]

das dict is so aufgebaut:
dict = { 'bla' : { 'irgendwas' : ['x', 'x1', 'x2', 'x3'], 'nochwas' : [1,2,3,4], 'nocheinletztes etwas' : "bla" }, '51 weiter solche einträge' : 'etc...'}

ich brauche aber nur das 'bla' und die '51 weiter einträge'.
also :
for element in dict: print dict #(zum beispiel)

und die frag ist, ob das schneller is als list = ["bla", "51 weitere..."]; for element in list: print list

[/me]

das dict is so aufgebaut:
dict = { 'bla' : { 'irgendwas' : ['x', 'x1', 'x2', 'x3'], 'nochwas' : [1,2,3,4], 'nocheinletztes etwas' : "bla" }, '51 weiter solche einträge' : 'etc...'}

ich brauche aber nur das 'bla' und die '51 weiter einträge'.
also :
for element in dict: print dict #(zum beispiel)

und die frag ist, ob das schneller is als list = ["bla", "51 weitere..."]; for element in list: print list

Bei der Größenordnung ist ein möglicher Unterschied Kinderkram.

Wenn du es aber genau wissen möchtest, dann hilft nur selber messen - und zwar auf der Maschine auf der es laufen soll.

[jbs]

Code: Alles auswählen

import time
l = range(50000)
d = {}
for i in l:
    d[i] = i

t = time.time()
for i in l: pass
print time.time()-t

t = time.time()
for e in d: pass
print time.time()-t

Code: Alles auswählen

0.007000207901
0.00600004196167

0.0090000629425
0.0090000629425

0.00699996948242
0.00800013542175

0.00699996948242
0.00699996948242

Ist zwar nicht statistisch aussagekräftig, aber zeigt, dass da keine großen Unterschiede sein sollten.

Außerdem sind 50 Einträge nichts.

[gkuhl]

Schneller als Listen sind Dictionaries, wenn es darum geht ein bestimmtes Element in der Menge zu finden.

Code: Alles auswählen

In [39]: d = dict()

In [40]: for i in l:
    d[i] = i
   ....:     
   ....:     

In [42]: l = range(50000)

In [43]: %timeit d.has_key(42)
1000000 loops, best of 3: 185 ns per loop

In [44]: %timeit d.has_key(42000)
1000000 loops, best of 3: 221 ns per loop

In [45]: %timeit 42 in l
1000000 loops, best of 3: 1.11 µs per loop

In [46]: %timeit 42000 in l
1000 loops, best of 3: 1.23 ms per loop

Grüße
Gerrit

[CM]

das dict is so aufgebaut:
dict = { 'bla' : { 'irgendwas' : ['x', 'x1', 'x2', 'x3'], 'nochwas' : [1,2,3,4], 'nocheinletztes etwas' : "bla" }, '51 weiter solche einträge' : 'etc...'}

ich brauche aber nur das 'bla' und die '51 weiter einträge'.
also :
for element in dict: print dict #(zum beispiel)

und die frag ist, ob das schneller is als list = ["bla", "51 weitere..."]; for element in list: print list

Krauzi, das ist etwas wirr. Vielleicht bekommst Du so zwar interessante Info - aber nicht unbedingt, die, die Du benötigst.

Einige Hinweise, warum Deine Frage nicht eindeutig ist:
- Von welchem 'bla' sprichst Du? Dein Beispiel enthält 2. Sprichst Du von Schlüssel oder vom Wert?
-

Code: Alles auswählen

for element in my_dict

iteriert nicht über die enthaltenen Werte, sondern über die Schlüssel - die Werte müsstest Du erst über

Code: Alles auswählen

my_dict[element]

auslesen. Du kannst aber auf versch. Weise über dicts iterieren, z. B.:

Code: Alles auswählen

for key, value in my_dict.iteritems():

, womit Du sowohl Schlüssel als auch den zugehörigen Wert hast. Wenn Du nur die Werte und nicht die Schlüssel benötigst: my_dict.itervalues(). Mehr dazu in der Doku zu dicts.

Code: Alles auswählen

for element in my_list:

iteriert zwar über direkt über die Einträge in der Liste, aber um ggf. die Datenstruktur eines dicts abzubilden, mußt Du so wieder Aufwand treiben, der ggf. diesen Vorteil wieder zunichte macht.
- Nochmal: Das reine Iterieren zu messen ist ziemlich sinnlos. Es kommt darauf an, was Du machen willst. Brauchst Du beispielsweise die Daten in einer best. Reihenfolge?

Also vielleicht magst Du uns erzählen, was Du machen möchtest - und nicht wie das Problem abstrahiert aussieht.

HTH
Christian

PS Ein dict and den Namen 'dict' zu binden ist gar keine gute Idee ...

[Krauzi]

jbs hat mich genau richtig verstanden.
Und mit seiner antwort meine frage auch beantwortet

[Defnull]

Schneller als Listen sind Dictionaries, wenn es darum geht ein bestimmtes Element in der Menge zu finden.

Das ist Irreführend. Bei einem Key-Lookup sind Beide gleich schnell, listen vielleicht sogar schneller, da bei Listen die Position jedes Objektzeigers im Speicher fest definiert ist. Bei einem Search-By-Value sind ebenfalls beide gleich schnell, da beide jedes einzelne Element durchsuchen müssen.

Dicts lohnen sich genau dann, wenn man
a) nach Schlüsseln sucht, die keine Integer sind
b) oder großen Lücken in seinen Integer-Schlüsseln hat

Das ein Search-By-Key in einem dict schneller ist als ein Search-By-Value in einer Liste (wie in deinem Beispiel) sollte klar sein.