schnelle Erstellung von index-item Zuweisung

mit matplotlib, NumPy, pandas, SciPy, SymPy und weiteren mathematischen Programmbibliotheken.
Antworten
schneitzmaster
User
Beiträge: 94
Registriert: Freitag 26. Oktober 2012, 15:35
Wohnort: Hamburg

Hallo Leute,

ich habe mal wieder eine Frage zur Codegeschwindigkeitsoptimierung.
Folgendes Szenario:
Ich habe eine Menge an Punkten die bestimmten Regionen zu geordnet werden sollen. Diese Zuordnung ist durch einen integer-array gegeben (pnt_region_connectivity). Hierbei ist der index eines Integers im pnt_region_connectivity der gleiche Index wie der Punkt um den es geht. Der Wert des Integers spezifiziert die Region zu welcher der Punkt zu geordnet werden soll. Nun benötige ich einen geschachtelten Array, der in erster Instanz die Regionen repräsentiert und in zweiter Instanz die jeweiligen Punkte beinhaltet.
Mein momentaner Code sieht folgendermaßen aus:

Code: Alles auswählen

import numpy as np
example_pnts            = np.random.random((7,4))
pnt_region_connectivity = np.array([0,0,1,0,2,3,3])
nb_regions              = 4
regions                 = []
#
for i in xrange(nb_regions):
    regions.append( example_pnts[pnt_region_connectivity==i] )
#
print regions
Geht das noch schneller? Hat vielleicht jemand eine Idee wie man die Schleife vermeiden kann?
Zuletzt geändert von schneitzmaster am Mittwoch 30. September 2015, 10:18, insgesamt 4-mal geändert.
BlackJack

@schneitzmaster: Geht was noch schneller? Ein `NameError`? Klar. ;-) Das ist nicht der Code den Du tatsächlich hast oder willst. Da ist ein undefinierter Name drin und auch die Programmlogik ist wirr/falsch. Es wird über das garantiert leere `regions` iteriert — also deswegen bekommt man dann doch keinen `NameError` weil der Schleifenkörper gar nicht ausgeführt wird, in der Schleife wird dann versucht etwas an die Laufvariable anzuhängen, was so wohl nicht sein sollte. Wenn man die nicht benötigt, frage ich mich aber waum überhaupt `enumerate()`‽

Poste doch mal lauffähigen Code der tatsächlich das Ergebnis liefert welches Du haben möchtest und keine leere Liste. :-P
schneitzmaster
User
Beiträge: 94
Registriert: Freitag 26. Oktober 2012, 15:35
Wohnort: Hamburg

Hi BlackJack,

ja sorry :oops: Ich muss wohl noch geschlafen haben. Keine Ahnung was da schiefgelaufen ist. Jetzt habe ich den richtigen Code reingepackt. Er sollte laufen (ich hab es gerade noch mal ausprobiert).
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@schneitzmaster: hast Du dort wirklich ein Geschwindigkeitsproblem? Was sind Deine wirklichen Dimensionen? Eine Schleife über 4 Werte sollte eigentlich keine Probleme machen.

Code: Alles auswählen

regions = [example_pnts[pnt_region_connectivity==i] for i in xrange(pnt_region_connectivity.max()+1)]
bzw:

Code: Alles auswählen

regions = {i: example_pnts[pnt_region_connectivity==i for i in set(pnt_region_connectivity)]
falls die pnt_region_connectivity sparse ist.
schneitzmaster
User
Beiträge: 94
Registriert: Freitag 26. Oktober 2012, 15:35
Wohnort: Hamburg

@Sirius3: Ja ich habe ein Geschwindigkeitsproblem, da pnt_region_connectivity bei mir im Realenprogramm eine Größe von 2Mio und aufwärts hat. Dabei gibt es dann 13500 und aufwärts Regionen.
Je größer alles wird, desto länger dauern die "==" operationen. Ist ja auch klar, da alle Einträge in pnt_region_connectivity verglichen werden müssen.
Ich dachte vielleicht kann man intelligent über indexing die Zuweisung hinbekommen.
Was meinst du mit sparse? Das ist doch ein 1-D-Array. Da ist doch nix sparse oder meinst du ob es viele Nullen gibt? Das muss ich leider verneinen. Alle Zahlen von 0 bis len(regions) kommen gleichoft vor.
Benutzeravatar
MagBen
User
Beiträge: 799
Registriert: Freitag 6. Juni 2014, 05:56
Wohnort: Bremen
Kontaktdaten:

Probier mal ob das hier schneller ist

Code: Alles auswählen

import numpy as np
example_pnts            = np.random.random((7,4))
pnt_region_connectivity = np.array([0,0,1,0,2,3,3])
nb_regions              = 4
regions                 = []
search_result = np.zeros(pnt_region_connectivity.shape, dtype=np.bool)

for i in xrange(nb_regions):
    np.equal(pnt_region_connectivity,i,search_result)
    regions.append( example_pnts[search_result] )

print regions
pnt_region_connectivity==i erzeugt jedes mal ein temporäres Bool-Array mit der gleichen Anzahl an Elementen wie pnt_region_connectivity. Mit der Funktion numpy.equal kann dagegen immer das selbe Array search_result benutzt werden.
a fool with a tool is still a fool, www.magben.de, YouTube
BlackJack

@schneitzmaster: Wenn das wirklich ein Flaschenhals ist und es keine fertige Numpy-Lösung gibt die das effizient genug hinbekommt, kann man sicher mit Cython etwas schreiben was besser macht. Das lässt sich mit je einem Durchlauf durch die beiden Arrays hinbekommen und einer zusätzlichen Schleife die dann `nb_regions` viele „views“ in das eine, grosse Ergebnisarray erstellt.
Sirius3
User
Beiträge: 17711
Registriert: Sonntag 21. Oktober 2012, 17:20

@schneitzmaster: das Problem bei Dir ist ja, dass jede Regionsergebnismatrix eine unterschiedliche Größe hat. Deshalb muß man ja erst die Anzahl der jeweiligen Elemente zählen, dann eine Matrix erzeugen und dann die Werte kopieren. Wenn Du das Ergebnis auch in Python-Listen gespeichert brauchen kannst, könnte vielleicht

Code: Alles auswählen

regions = defaultdict(list)
for region, example in zip(pnt_region_connectivity, example_pnts):
    regions[region].append(example)
schneller sein, weil da die 2Mio Spalten nur einmal durchgegangen werden und nicht kopiert werden.
schneitzmaster
User
Beiträge: 94
Registriert: Freitag 26. Oktober 2012, 15:35
Wohnort: Hamburg

Danke für die vielen Hilfestellungen.
Sirius3 antwort ist die Lösung. Ich bekomme dadurch einen wesentlichen speed up von 40 bei meiner Beispielrechnung.
Danke dafür! Damit ist mein Problem vorerst gelöst. Hätte ich nicht gedacht, da ich immer der Überzeugung war .append(...) ist langsam und suboptimal wenn man eigentlich die größe der Arrays kennt. Aber das vielfache druchlaufen von pnt_region_connectivity bei der boolschen operation muss wohl das Problem gewesen sein.
Antworten