Seite 1 von 1
Bestimmte Dictionaries in Listen finden...
Verfasst: Samstag 9. Dezember 2006, 22:51
von oliver1974
Guten Abend zusammen:
Mal eine Frage:
Angenommen, ich habe eine Liste, die lauter dictionaries enthält...
>>> print mylist
[{'code': '123123123', 'time': '12:55:01'}, {'code': '444777888', 'time': '13:01:02'}]
'code' sei für mich ein eindeutiger Identifier..
Wie könnte ich möglichst effizient prüfen, ob mylist ein Dictionary enthält
wo ein bestimmter 'code' vorkommt?
Bisher mache ich das primitiv so:
Code: Alles auswählen
def check_for_code(mylist, code):
for d in mylist:
if d["code"] == code:
return True
return False
Geht das auch eleganter/schneller?
Danke im voraus!
Verfasst: Sonntag 10. Dezember 2006, 00:01
von EyDu
Bist du unbeding auf Listen angewiesen? Wenn "code" eh' ein Schlüssel ist, könnte man gut folgendes machen:
Code: Alles auswählen
def check_for_code(data, code):
return code in data.keys()
#Mit dem Beispielaufruf (code sind hier 234 und 123)
x={234:{"time":9999}, 123:{"time":8888}}
c=234
print check_for_code(x, c)
Ist ungetestet, aber mein Gedanke wird hoffentlich klar.
Sebastian
EDIT: Häßliche Leerzeichen entfernt
Verfasst: Sonntag 10. Dezember 2006, 00:07
von oliver1974
Hmmm, also geschachtelte Dicts...
Ich glaube, die Variante hatte ich auch schon probiert, ich muss nur noch mal rausfinden, warum ich davon wieder abgekommen bin...
Danke erstmal!
Verfasst: Sonntag 10. Dezember 2006, 20:39
von oliver1974
Jetzt weiß ich wieder, warum ich die Geschichte mit den geschachtelten Dicts nicht machen wollte.
Dicts sind ja nicht sortiert, Listen dagegen schon... (In der Reihe
des Hinzufügens, meine ich jetzt).
Das Feature brauche ich aber, deswegen kam für mich ein Dict als "oberste Ebene" nicht in Frage..
Hmm, neue Ideen?
Verfasst: Sonntag 10. Dezember 2006, 20:53
von Leonidas
oliver1974 hat geschrieben:Dicts sind ja nicht sortiert, Listen dagegen schon... (In der Reihe des Hinzufügens, meine ich jetzt).
Wie wärs, du nimmst einfach ein [wiki]sortiertes Dictionary[/wiki]?
Verfasst: Sonntag 10. Dezember 2006, 21:19
von oliver1974
Ahhh, ich seh schon.... Die Sache muss man natürlich erstmal kennen, danke!
Ob sich das in meinem konkreten Fall lohnt, ist natürlich noch eine andere Frage... Aber dann hatte ich soweit richtig vermutet, dass es so "fertig" in Python nichts gibt.
Re: Bestimmte Dictionaries in Listen finden...
Verfasst: Montag 11. Dezember 2006, 13:06
von keppla
oliver1974 hat geschrieben:Geht das auch eleganter/schneller? Danke im voraus!
ob das eleganter ist, ist geschmacksfrage, ob es schneller ist, kann nicht sonderlich wichtig sein, wenn du es eh nicht merkst (premature optimisation, und so), aber mal als Anregung:
Code: Alles auswählen
def check_for_code(mylist, code):
used_codes = [ d['code'] for d in mylist ]
return code in used_codes
ist kürzer (was nicht immer ein Vorteil sein muss), erschliesst sich einem aber imho recht einfach.
Ein Hinweis
Verfasst: Montag 11. Dezember 2006, 13:18
von sunmountain
Dicts können als Key alles beinhalten, was "hashable" ist.
Folgendes ist denk- und machbar:
Code: Alles auswählen
import sets
d = {}
d[1,'code'] = '123123123'
d[1,'time'] = '12:55:01'
d[2,'code'] = '444777888'
d[2,'time'] = '13:01:02'
keys = d.keys()
keys.sort()
nums = [n[0] for n in keys]
nums = sets.Set(nums) # Erzeugt 'echte' Menge, keine Dubletten
for n in nums:
print n,d[n,'code']
print n,d[n,'time']
Da der Key hier eine Liste ist, bleibt diese "sortiert".
Sortiert in dem Sinne, das die Zahl das 1. Element bleibt.
Beim Sortieren wird also immer das das 1. Element zuerst verglichen.
Man muss nur beim Erstellen des Dicts daran denken, einen Zähler
mitzuführen ...
Verfasst: Montag 11. Dezember 2006, 13:43
von BlackJack
Was soll das an Vorteilen bringen? Vor allem gegenüber der Liste mit den Dictionaries und der Operation die oliver1974 wollte. Und der schöne direkte Zusammenhang von 'code' und 'time' in *einem* Objekt ist auch dahin.
Über die Liste kann man in O(n) Zeit laufen und suchen, bei Deiner Konstruktion kommt da nochmal O(log n) zum sortieren oben drauf.
Keppla's Lösung kann man noch ein wenig kürzen:
Code: Alles auswählen
def check_for_code(mylist, code):
return code in (d['code'] for d in mylist)
Hat den zusätzlichen Vorteil, dass abgebrochen wird, sobald der `code` gefunden wurde.
Verfasst: Montag 11. Dezember 2006, 13:52
von sunmountain
Verfasst: Dienstag 12. Dezember 2006, 08:10
von oliver1974
Wow!
Ich hätte nicht gedacht, dass sich in dem Thread noch was tut...
Ich hatte das Thema schon fast wieder gedanklich abgehakt.
Danke erst mal an alle, super!
@keppla:
Witzig, eigentlich hatte ich genau das gesucht, wollte das auch
als list-comprehension schreiben, aber irgendwie
habe ich da die Kurve mit dem "return" nicht gekriegt, das
war der Zusammenhang, der mir fehlte.
Ich hatte hier nebenbei aber nochmal ganz grobe Tests laufen, wie
"langsam" denn nun mein primitiver Ansatz ist
(von wegen premature optimization und so..), und musste
überrascht feststellen, dass das ganze immer noch so schnell ist,
dass selbst ein "hit" (also Treffer) auch am Ende einer Liste mit
100000 Einträgen so schnell gefunden wird, dass man eigentlich
nicht mal mit den Augen zwinkern kann, also mehr als ausreichend.
Da die Liste aber wohl nie so lang werden wird (dürfte nach
bisherigen Kenntnisstand täglich zurückgesetzt werden,
und dürfte wohl nie mehr als 100 Einträge haben) sind
wohl alle weiteren "optimizations" fast ohne tieferen Sinn.
Da dürfe ich wohl eher aus Eleganz-Gründen kepplas Code
(bzw. Blackjacks gekürzte Variante)
implementieren...
Übrigens: Stimmt, der Zusammhalt des Dictionaries wäre
schon wichtig, ist ja auch praktisch, trotzdem natürlich
auch Dank an sunmountain!
(Zum Thema "Speed": ich bin generell zur Zeit sowieso platt,
wie hoch doch zumindest die "gefühlte" Geschwindigkeit
von Python ist...).
Verfasst: Dienstag 12. Dezember 2006, 12:59
von keppla
oliver1974 hat geschrieben:
Da dürfe ich wohl eher aus Eleganz-Gründen kepplas Code
(bzw. Blackjacks gekürzte Variante)
implementieren...
Nimm blackjacks, sie ist nicht nur kürzer, sie hat (wie er schon sagte) einen Unterschied: sie ist speicher- und geschwindigkeitseffizienter.
Der unterschied ist etwas subtil:
gibt eine Liste zurück, das heist, dass alle d['codes'] nochmal in den speicher geschrieben werden.
gibt einen Iterator zurück, was bedeutet, dass erstmal nix passiert.
Die Anweisung
iteriert nun über used_codes, und bricht mit ja ab, wenn sie einen findet*, also bei beiden der gleiche Aufwand.
*) kann ich nicht beschwören, aber sowohl für listen ohne bekannte struktur, als auch für iteratoren fallen mit keine effizienteren mechanismen ein.
(Zum Thema "Speed": ich bin generell zur Zeit sowieso platt,
wie hoch doch zumindest die "gefühlte" Geschwindigkeit
von Python ist...).
Meiner Meinung nach hängt Geschwindigkeit meist mehr vom Programmierer als vom Framework ab. Ein Bubblesort ist auch in C++ extrem lahm.
[/code]
Verfasst: Dienstag 12. Dezember 2006, 23:13
von oliver1974
Na, das waren ja nochmal gute Tipps, danke!
In der Tat ist die list-comprehension Variante etwas schneller
als mein primitiver Ansatz, es hat sich aber erst bei SEHR
grossen Listen merkbar ausgewirkt (weit über 500.000 Einträge).
