Bestimmte Dictionaries in Listen finden...

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
oliver1974
User
Beiträge: 97
Registriert: Donnerstag 26. Oktober 2006, 15:01

Bestimmte Dictionaries in Listen finden...

Beitragvon oliver1974 » Samstag 9. Dezember 2006, 22:51

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
User
Beiträge: 4866
Registriert: Donnerstag 20. Juli 2006, 23:06
Wohnort: Berlin

Beitragvon EyDu » Sonntag 10. Dezember 2006, 00:01

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
User
Beiträge: 97
Registriert: Donnerstag 26. Oktober 2006, 15:01

Beitragvon oliver1974 » Sonntag 10. Dezember 2006, 00:07

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
User
Beiträge: 97
Registriert: Donnerstag 26. Oktober 2006, 15:01

Beitragvon oliver1974 » Sonntag 10. Dezember 2006, 20:39

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?
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Sonntag 10. Dezember 2006, 20:53

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]?
My god, it's full of CARs! | Leonidasvoice vs Modvoice
oliver1974
User
Beiträge: 97
Registriert: Donnerstag 26. Oktober 2006, 15:01

Beitragvon oliver1974 » Sonntag 10. Dezember 2006, 21:19

Ahhh, ich seh schon.... Die Sache muss man natürlich erstmal kennen, danke! :-D

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.
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Re: Bestimmte Dictionaries in Listen finden...

Beitragvon keppla » Montag 11. Dezember 2006, 13:06

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.
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Ein Hinweis

Beitragvon sunmountain » Montag 11. Dezember 2006, 13:18

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

Beitragvon BlackJack » Montag 11. Dezember 2006, 13:43

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.
Benutzeravatar
sunmountain
User
Beiträge: 89
Registriert: Montag 13. März 2006, 17:18

Beitragvon sunmountain » Montag 11. Dezember 2006, 13:52

:oops:
oliver1974
User
Beiträge: 97
Registriert: Donnerstag 26. Oktober 2006, 15:01

Beitragvon oliver1974 » Dienstag 12. Dezember 2006, 08:10

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...).
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Beitragvon keppla » Dienstag 12. Dezember 2006, 12:59

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:

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
User
Beiträge: 97
Registriert: Donnerstag 26. Oktober 2006, 15:01

Beitragvon oliver1974 » Dienstag 12. Dezember 2006, 23:13

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

Wer ist online?

Mitglieder in diesem Forum: Bing [Bot]