Performanceproblem

[calo]

Hallo,

folgendes Performanceproblem: Ich habe ein Dictionary mit Elementen (keys) und Knoten (values):

Code: Alles auswählen

element_to_nodes= {1: (1, 2, 3),
    2: (1, 3, 7),
    4: (2, 4, 5, 3),
    9: (3, 5, 6, 7)}

Dieses Dict. möchte ich nun "umdrehen". D. h. jetzt sollen die Knoten zu keys werden und die Elemente zu values:

Code: Alles auswählen

node_to_elements= {1: (1, 2),
    2: (1, 4),
    3: (1, 2, 4, 9),
    4: (4, ),
    5: (4, 9),
    6: (9, ),
    7: (2, 9)}

Ich habe auch schon ein Code das funktioniert:

Code: Alles auswählen

t0 = time()
node_to_elements= {}

for elem_label, node_list in element_to_nodes.iteritems():
    for node in node_list:
        if node not in node_to_elements.keys():
            node_to_elements[node] = []
        node_to_elements[node].append(elem_label)

print "Knotenliste erstellt: ", time()-t0

Allerdings ist dieser ziemlich langsam. In meinem Testfall mit 7000 Elementen benötigt es bereits 12 s. Später sollen es aber mehrere Mio. Elemente werden. Was kann ich tun um die Sortierung zu beschleunigen?

Vielen Dank im Voraus
Gruß, cc

PS: Hier noch das Beispiel mit den 7000 Elementen: http://pastebin.de/9628

[BlackJack]

@calo: Also ein Hammerfehler ist der Test ob etwas in `node_to_elements.keys()` enthalten ist. Da wird jedesmal eine Liste mit den Schlüsseln erstellt und darin dann *linear* nach dem Element gesucht, statt den O(1)-Test direkt mit ``in`` auf dem Dictionary zu machen.

Ansonsten könnte man hier ein `collections.defaultdict` verwenden, um sich den Test ganz zu sparen.

[calo]

Ich staune

Ich habe das dict mit defaultdict ersetzt:

Code: Alles auswählen

import collections
from time import time

t0 = time()
node_to_elements= collections.defaultdict(list)

for elem_label, node_list in element_to_nodes.iteritems():
    for node in node_list:
        node_to_elements[node].append(elem_label)

print "Knotenliste erstellt: ", time()-t0

Was vorher 12s gebraucht hat, läuft jetzt in 0.062s

Vielen Dank Blackjack