Reihenfolge bei dict.keys() und dict.values()

[Fabian Steiner]

Hallo!

Ich bin gerade dabei, mir eine eigene kleine SQL-Query-Klasse zu
schreiben, die mir beispielsweise aus einem übergebenem Dictionary
einen INSERT-Query zusammenbaut. Dabei durchlaufe ich das Dictionary
z.B. folgendermaßen:

for column in data.keys():
if column == data.keys()[-1]:
self._query += ("'%s'" + ')') % (column)
else:
self._query += ("'%s'" + ', ') % (column)

An anderer Stelle geschieht beinahe das gleiche noch einmal mit
data.values(). Im Python Tutorial
(http://docs.python.org/tut/node7.html#SECTION007500000000000000000)
findet man dazu z.B. nur folgendes:
"The keys() method of a dictionary object returns a list of all the
keys used in the dictionary, in arbitrary order (if you want it sorted,
just apply the sort() method to the list of keys). "

Unter http://docs.python.org/lib/typesmapping.html findet man dann aber
auch noch folgende Aussage:
"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

Zusammengefasst heißt das also, dass die Reihefolge beliebig ist [1],
aber nicht zufällig. Meine Frage ist nun, kann ich mich darauf
verlassen, dass die Reihenfolge von dict.keys() und dict.values()
gleich ist und dann nicht etwas die Zuordnung Key-Value überhaupt
nicht mehr stimmt. Gibt es denn eine bessere Lösungsmöglichkeit.

Vielen Dank für eure Hilfe!
Grüße,
Fabian

[1] Was heißt in diesem Fall beliebig?

[Georg Brandl]

Post by Fabian Steiner
Hallo!
Ich bin gerade dabei, mir eine eigene kleine SQL-Query-Klasse zu
schreiben, die mir beispielsweise aus einem übergebenem Dictionary
einen INSERT-Query zusammenbaut. Dabei durchlaufe ich das Dictionary
self._query += ("'%s'" + ')') % (column)
self._query += ("'%s'" + ', ') % (column)

Ganz unabhängig von dem anderen Problem ist das mit einem Einzeiler schöner
zu lösen:

self._query += ', '.join("'%s'" % column for column in data.iterkeys()) + ')'

Das ".iterkeys()" kann man auch weglassen in dem Fall.

Post by Fabian Steiner
An anderer Stelle geschieht beinahe das gleiche noch einmal mit
data.values(). Im Python Tutorial
(http://docs.python.org/tut/node7.html#SECTION007500000000000000000)
"The keys() method of a dictionary object returns a list of all the
keys used in the dictionary, in arbitrary order (if you want it sorted,
just apply the sort() method to the list of keys). "
Unter http://docs.python.org/lib/typesmapping.html findet man dann aber
"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

Gleich danach kommt doch:
"""If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are
called with no intervening modifications to the dictionary, the lists will
directly correspond."""

Post by Fabian Steiner
Zusammengefasst heißt das also, dass die Reihefolge beliebig ist [1],
aber nicht zufällig. Meine Frage ist nun, kann ich mich darauf
verlassen, dass die Reihenfolge von dict.keys() und dict.values()
gleich ist

Steht oben.

Georg

[Fabian Steiner]

Hallo!

Post by Georg Brandl

Post by Fabian Steiner
self._query += ("'%s'" + ')') % (column)
self._query += ("'%s'" + ', ') % (column)

Ganz unabhängig von dem anderen Problem ist das mit einem Einzeiler schöner
self._query += ', '.join("'%s'" % column for column in data.iterkeys()) + ')'

Vielen Dank dafür :-) Da merkt man mal wieder, wie schön man gewisse
Sachen mit Python kürzer ausdrücken kann, als in anderen Sprachen.

Post by Georg Brandl

Post by Fabian Steiner
Unter http://docs.python.org/lib/typesmapping.html findet man dann aber
"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

"""If items(), keys(), values(), iteritems(), iterkeys(), and
itervalues() are called with no intervening modifications to the
dictionary, the lists will directly correspond."""

Hm, das muss ich wohl überlesen haben *schäm* Also kann ich mir sicher
sein, dass wenn ich am Dictionary selbst nichts verändere, die
Reihenfolge bei keys() und values() gleich ist.

Könnte mir jemand jedoch noch verraten, wie die Reihenfolge von keys()
und values() zustande kommt?

Grüße,
Fabian

[Georg Brandl]

Post by Fabian Steiner

Post by Georg Brandl

Post by Fabian Steiner
Unter http://docs.python.org/lib/typesmapping.html findet man dann aber
"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

"""If items(), keys(), values(), iteritems(), iterkeys(), and
itervalues() are called with no intervening modifications to the
dictionary, the lists will directly correspond."""

Hm, das muss ich wohl überlesen haben *schäm* Also kann ich mir sicher
sein, dass wenn ich am Dictionary selbst nichts verändere, die
Reihenfolge bei keys() und values() gleich ist.

Jep.

Post by Fabian Steiner
Könnte mir jemand jedoch noch verraten, wie die Reihenfolge von keys()
und values() zustande kommt?

Das hängt daran, wie Python neue Elemente in seine interne Datenstruktur
einfügt (dicts sind ja Hashtables) und ist je nach Objekten total
verschieden.

Georg

[Andreas Jung]

Post by Fabian Steiner
Hm, das muss ich wohl überlesen haben *schäm* Also kann ich mir sicher
sein, dass wenn ich am Dictionary selbst nichts verändere, die
Reihenfolge bei keys() und values() gleich ist.

Nein! Ein assoziativer Speicher hat eben per Definition kein Konzept von
"Reihenfolge". Was Du siehst ist eine Implementierungsinvariante, auf
die Du Dich nicht verlassen sollst/darfst. Wenn Dein Code unter Jython
oder IronPython laufen sollte, dann könnte das Verhalten komplett anders
sein. Wenn Du einen assoziativen Speicher _mit_ festgelegter Sortierung
willst, dann muss Du die Sortierung explizit irgendwo speichern. Für
Python gibt es aber da wohl schon eine Reihe von Modulen, die das
machen. Google mal nach "ordered dict".

Post by Fabian Steiner
Könnte mir jemand jedoch noch verraten, wie die Reihenfolge von keys()
und values() zustande kommt?

Da mußt Du schon selber in den Python Sourcen wühlen :-)

[Georg Brandl]

Post by Andreas Jung

Post by Fabian Steiner
Hm, das muss ich wohl überlesen haben *schäm* Also kann ich mir sicher
sein, dass wenn ich am Dictionary selbst nichts verändere, die
Reihenfolge bei keys() und values() gleich ist.

Nein! Ein assoziativer Speicher hat eben per Definition kein Konzept von
"Reihenfolge". Was Du siehst ist eine Implementierungsinvariante, auf
die Du Dich nicht verlassen sollst/darfst. Wenn Dein Code unter Jython
oder IronPython laufen sollte, dann könnte das Verhalten komplett anders
sein. Wenn Du einen assoziativen Speicher _mit_ festgelegter Sortierung
willst, dann muss Du die Sortierung explizit irgendwo speichern. Für
Python gibt es aber da wohl schon eine Reihe von Modulen, die das
machen. Google mal nach "ordered dict".

Nein. Was da in der Library Reference steht, ist keine "Implementation
Note", d.h. muss auch in Jython so sein.

Georg

[Andreas Jung]

Post by Georg Brandl
Nein. Was da in der Library Reference steht, ist keine "Implementation
Note", d.h. muss auch in Jython so sein.

Offenbar liest Du anders als ich.

Post by Georg Brandl

Post by Fabian Steiner
"Keys and values are listed in an arbitrary order which is non-random,
varies across Python implementations, and depends on the dictionary's
history of insertions and deletions."

"arbitrary order" = beliebige Sortierung
"varies across Python implementation" = ...unterschiedlich zwischen
verschiedenen Python Implementierungen

Wieso muß das in Jython genauso sein?

Post by Georg Brandl
"""If items(), keys(), values(), iteritems(), iterkeys(), and
itervalues() are called with no intervening modifications to the
dictionary, the lists will directly correspond."""

Das besagt nichts anderes als das die Reihenfolge bei einer Iteration
über einem nicht modifizierten Mapping identisch ist. Das steht aber in
keinem Bezug zur Reihenfolge beim Einfügen...oder sehe ich da etwas falsch?

-aj

[Georg Brandl]

Post by Andreas Jung

Post by Georg Brandl
"""If items(), keys(), values(), iteritems(), iterkeys(), and
itervalues() are called with no intervening modifications to the
dictionary, the lists will directly correspond."""

Das besagt nichts anderes als das die Reihenfolge bei einer Iteration
über einem nicht modifizierten Mapping identisch ist. Das steht aber in
keinem Bezug zur Reihenfolge beim Einfügen...oder sehe ich da etwas falsch?

Post by Georg Brandl
Hm, das muss ich wohl überlesen haben *schäm* Also kann ich mir sicher
sein, dass wenn ich am Dictionary selbst nichts verändere, die
Reihenfolge bei keys() und values() gleich ist.

Nein! Ein assoziativer Speicher hat eben per Definition kein Konzept von
"Reihenfolge". Was Du siehst ist eine Implementierungsinvariante, auf
die Du Dich nicht verlassen sollst/darfst. Wenn Dein Code unter Jython
oder IronPython laufen sollte, dann könnte das Verhalten komplett anders
sein. Wenn Du einen assoziativen Speicher _mit_ festgelegter Sortierung
willst, dann muss Du die Sortierung explizit irgendwo speichern. Für
Python gibt es aber da wohl schon eine Reihe von Modulen, die das
machen. Google mal nach "ordered dict".

Das ist doch genau die Situation, die oben beschrieben wird.

Georg

[Volker Grabsch]

Post by Fabian Steiner

Post by Georg Brandl
"""If items(), keys(), values(), iteritems(), iterkeys(), and
itervalues() are called with no intervening modifications to the
dictionary, the lists will directly correspond."""

Hm, das muss ich wohl überlesen haben *schäm* Also kann ich mir sicher
sein, dass wenn ich am Dictionary selbst nichts verändere, die
Reihenfolge bei keys() und values() gleich ist.

Egal, ob dem so sein muss oder nicht: Wen kümmert's?

Wenn du über die Schüssel *und* Werte iterieren musst, nimmst du

for key, value in d.iteritems():
...

und fertig. Da hast du garantiert die "gleiche Reihenfolge" der
Schlüssel und der Werte, schließlich bekommst du stets ein
zusammenhängendes Paar. :-)

Willst du nicht iterieren, sondern brauchst das aus irgendeinem Grund
als Liste, kippst du den Iterator einfach in eine Liste ab:

meine_liste = list(d.iteritems())

Allgemein sind mehrere gleichartig indizierte Listen keine gute Idee.
Dann hast du sofort Probleme, die immer syncron zu halten.
Nimm lieber eine große Liste von Tupeln (oder Liste von Dictionaries,
oder Liste von eigenen Objekten). Das heißt:

#
# so nicht!
#
name = ["Susan", "Sven", "John"]
alter = [20, 43, 35]

for i in xrange(len(name)):
print "%s (%i)" % (name[i], alter[i])


#
# sondern so:
#
personen = [ ("Susan", 20), ("Sven", 43), ("John", 35) ]

for name, alter in personen:
print "%s (%i)" % (name, alter)



Via "zip()" kannst du die eine Variante auch in die andere umwandeln, was
man IMHO gleich zu Anfang tun sollte. Erstmal vernünftige Datenstrukturen
aufbauen, und dann erst damit arbeiten.

Deshalb auch grundsätzlich: Nicht d.keys() und d.values() extra holen
und dann mühevoll zusammendurchlaufen, sondern gleich d.iteritems() nehmen!

Post by Fabian Steiner
Könnte mir jemand jedoch noch verraten, wie die Reihenfolge von keys()
und values() zustande kommt?

Der Witz bei Hashtabellen (also Dictionaries) ist doch der, dass die
Reihenfolge (genauer: die Baumstruktur) möglichst so geschickt gewählt
wird, dass man anhand des Schlüssels möglichst schnell den passenden
Wert findet. Eine Variante wäre z.B., dass man eine nach den Schlüsseln
sortierte Liste nehmen, neue Elemente immer sortiert einfügt, und dann
mit einer Binärsuche relativ schnell einen Schlüssel mitsamt Wert
wiederfindet. Würde man sie so einfügen, wie sie kommen, also ohne
Sortierung, müsste man immer *alles* durchsuchen, was extrem langsamer
wäre.

Aber es auch noch schneller, denn man kann sich die aufwändigen Schlüssel-
Vergleiche (i.d.R. String-Vergleiche) sparen, indem man stattdessen nach
ihren Hashwerten (das sind Integers) sortiert und sucht. Erst wenn man
da was gefunden hat, vergleicht man sicherheitshalber nochmal die Schlüssel
(meist nur noch ein einziger String-Vergleich).

Auch hier gibt es verschiedene Arten, welchen Hash-Algorithmus man
verwendet, um jedem String (genauer: jedem beliebigen Objekt) einen
Hashwert zuzuordnen. Die id() übrigens ist als Hash unbrauchbar,
weil ein Hash derselbe bleiben muss, wenn zwei Objekte gleich (a == b)
sind, nicht nur wenn sie identisch sind (a is b).

Und vielleicht gibt es noch viel bessere baum-ähnliche Datenstrukturen,
neue Hashverfahren, etc. Was ich damit klar machen möchte: Es gibt so
viel Spielraum in der Implementierung, dass man pauschal kein Schema
angeben kann, und auch nicht will! Man will doch gerade in Python jederzeit
die Option haben, seine Dictionary-Implementierung noch schneller, noch
besser, noch stärker zu optimieren.

Von daher ergibt deine Frage nicht sehr viel Sinn. Schau in den Python-
Quellcode, aber sei dir darüber im Klaren, dass es in der nächsten Version
wieder ganz anders aussehen kann. Ganz zu schweigen von den Unterschieden
zu Jython, PyPy, etc.

Dictionaries haben einfach keine Reihenfolge. Es wird eine für den
Datenzugriff möglichst "optimale" Reihenfolge genommen, welche auch immer
das ist. Und es ist nicht wirklich eine Reihenfolge, sondern eine
Baumstruktur. keys(), values(), etc. durchlaufen diese Baumstruktur,
auch da gibt es immer viele Möglichkeiten (preorder, inorder, postorder,
was auch immer). Aus Sicht des Benutzers (d.h. des Python-Programmierers)
haben Dictionaries keine Reihenfolge. Und das ist sehr, sehr gut so.


Viele Grüße,

Volker

[Georg Brandl]

Post by Volker Grabsch
Willst du nicht iterieren, sondern brauchst das aus irgendeinem Grund
meine_liste = list(d.iteritems())

meine_liste = d.items()

ist kürzer.


Georg