sortieren nach Attributen, so dass generator herauskommt

[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

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

[CM]

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