Seite 1 von 1
sortieren nach Attributen, so dass generator herauskommt
Verfasst: Mittwoch 25. November 2009, 11:40
von CM
Hoi,
ich habe ein riesiges dict - Resultat vorhergender Arbeit und darin stecken Instanzen einer Klasse. In Etwa so:
Code: Alles auswählen
class Foo(object):
def __item__(self, value):
self.value = value # ein Integer
d = {'a': Foo(1), 'b': Foo(2)}
jetzt sortiere ich mit
Code: Alles auswählen
import operator
sorted(d.itervalues(), key=operator.attrgetter('value'))
Gibt natürlich eine Liste. Gut, die enthaltenen Objekte, sind nicht furchtbar groß, aber die Liste lang - mehrere Millionen Einträge.
Gibt es hier eine Möglichkeit - ohne Geschwindigkeit einzubüssen - weniger Speicher zu brauchen, über Verwendung eines Generators beispielsweise?
Gruß,
Christian
Verfasst: Mittwoch 25. November 2009, 12:30
von Defnull
Nicht, das ich wüsste.
Dicts sind nicht geordnet, d.h. du musst früher oder später eine Liste daraus machen, damit ein Sortieralgorithmus damit arbeiten kann. Dabei ist es egal, ob du inplace (list().sort()) oder in eine Kopie hinein sortierst (sorted()), da du auf jeden Fall eine Liste brauchst, aber ein dict hast, musst du mindestens eine Kopie an legen.
Deine Idee, das ganze als Generator zu implementieren, funktioniert nur in O(n²) statt O(n*log(n)) da dir das Gedächtnis fehlt. Du musst für jede Iteration wieder den kompletten dict durchlaufen, um den nächst größeren Wert zu finden. Du kannst dich nie darauf verlassen, das bestimmte Teile bereits sortiert sind, wenn du sie nicht irgendwo speicherst.
Du könntest natürlich, statt den kompletten Datenbestand in eine Liste zu kopieren, nur die Schlüssel sortieren.
Code: Alles auswählen
d = {'a': Foo(1), 'b': Foo(2)}
sorted_keys = sorted(d.iterkeys(), key=lambda k: d[k].value)
(ungetestet)
Verfasst: Mittwoch 25. November 2009, 12:55
von CM
Defnull hat geschrieben:Deine Idee, das ganze als Generator zu implementieren, funktioniert nur in O(n²) statt O(n*log(n)) da dir das Gedächtnis fehlt.
Kennen wir uns?
Aber die Idee, nur auf die keys zurückzufallen, ist gut. Das läuft zwar nicht schneller - spart aber wesentlich Speicher.
Danke.
Gruß,
Christian