Bestimmte Dictionaries in Listen finden...

[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!

[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

[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!

[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?

[Leonidas]

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]?

[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.

[keppla]

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.

[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 ...

[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.

[sunmountain]

[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...).

[keppla]

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:

Code: Alles auswählen

used_codes = [d['code'] for d in mylist]

gibt eine Liste zurück, das heist, dass alle d['codes'] nochmal in den speicher geschrieben werden.

Code: Alles auswählen

used_codes = (d['code'] for d in mylist)

gibt einen Iterator zurück, was bedeutet, dass erstmal nix passiert.

Die Anweisung

Code: Alles auswählen

code in use_codes

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]

[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).