Array transformieren... wie?

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
Antworten
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Montag 11. September 2006, 15:20

Hi all.

Angenommen wir haben ein 4-dimensionales Array,
dass je nach Index locker mehr als 1000 Elemente aufnehmen kann.
Momentan fülle ich die Werte aus einer Datei mit einer hässlichen 4-fach for-Schleife.
Da hab ich mir überlegt ich das nicht beschleunigen kann, indem ich aus vier
for-Schleifen eine mach. Und tatsächlich das Teil ist 2x schneller.

Hier der Beweis:

Code: Alles auswählen

#benchmark_01.py
#!/usr/bin/python -OO
 2 
 3 for w in range(320):
 4     for h in range(240):
 5         for f in range(100):
 6             for c in range(3):
 7                 pass

Code: Alles auswählen

#benchmark_02.py
#!/usr/bin/python -OO
 2 
 3 for i in range(320*240*100*3):
 4     pass

Code: Alles auswählen

#console output, zur Sicherheit 2x ausgeführt...
> time ./benchmark_01.py 

real	0m13.208s
user	0m12.975s
sys	0m0.007s
> time ./benchmark_02.py 

real	0m6.888s
user	0m5.415s
sys	0m0.841s
> time ./benchmark_01.py 

real	0m13.725s
user	0m13.119s
sys	0m0.012s
> time ./benchmark_02.py 

real	0m6.246s
user	0m5.340s
sys	0m0.828s
>
Mein Problem ist folgendes:

Mit der 4-fach for-Methode werden meine Daten langsam, aber in der korrekten Reihenfolge gefüllt:
array[w][h][f][c], wobei zuerst w von 0 - width komplett durchläuft, bevor die anderen laufvars angefasst werden.
Umgekehrt bei der schnellen 1-fach Methode fülle ich das Array nach dem Prinzip:
i=w*h*f*c
array[i%w][i%h][i%f][i%c]

Funktioniert auch, nur die Reihenfolge ist nicht die erwünschte.

Es hat nicht zufällig ein Mathe-genie ne Idee wie man mit einer for-Schleife alles 2x schneller machen kann UND die Reihenfolge erhällt?

Theoretisch müsste es genau eine bijektive Transformation geben, die genau das bewerkstelligt. Oder?
murph
User
Beiträge: 622
Registriert: Freitag 14. April 2006, 19:23
Kontaktdaten:

Montag 11. September 2006, 16:33

deine 4fach-for-schleife funktioniert bestimmt nicht richtig.

Code: Alles auswählen

for i in range(320*240*100*3):
sollte gleichbedeutend sein mit

Code: Alles auswählen

for i in range(23040000)
was nämlich deine zuerst ausgeführte multiplikationsaufgabe ergibt.
dein problem sollte eher mit zip lösbar sein,
habe damit aber lieder keine erfahrung.
http://www.cs.unm.edu/~dlchao/flake/doom/
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Montag 11. September 2006, 16:40

hä?

ich habe keinen einzigen Satz verstanden sorry.

Bis auf die Reihenfolge wird das Array mit denselben Daten befüllt.

Und was Zip damit zu tun hat? ... :roll:
BlackJack

Montag 11. September 2006, 16:42

Oh mann, komm mal von Deinem Optimierungstrip runter. Ich habe in "freier Wildbahn" noch nie gesehen das jemand die ``-OO`` Option verwendet. Dann ist die verschachtelte Schleife viel deutlicher als diese rum-modulo-riererei von dem einen Index.

Was hast Du denn da gemessen? Nur die Schleifen mit dem ``pass``? Dann hasst Du die Schleifen gemessen ohne die Arbeit die eigentlich anstelle von ``pass`` stehen würde. Da wäre es interessant wie gross oder eben auch wie klein der Anteil vom Schleifenoverhead real ist. Eine Verdopplung der Geschwindigkeit wird das dann nicht mehr sein.

Was für Daten liesst Du da eigentlich ein? vielleicht lassen sich mit dem `array` Modul oder `numarray`/`numpy` wesentlich bessere Resultate erzielen, sowohl was Laufzeit als auch Speicherverbrauch angeht.
rayo
User
Beiträge: 773
Registriert: Mittwoch 5. November 2003, 18:06
Wohnort: Schweiz
Kontaktdaten:

Montag 11. September 2006, 16:46

Hi

Also eine For-Schleife mit i als Index geht so:

Code: Alles auswählen

for i in xrange(320*240*100*3):
    w = i/(240*100*3)
    h = (i%(240*100*3))/(100*3)
    f = (i%(100*3))/3
    c = i%3
    print w,h,f,c
Sollte die gleiche Reihenfolge wie die 4 For-Schleifen sein (habs nicht getestet)

Die Daten kannst du (falls es Binärdaten sind) besser mit dem Modul array einlesen oder wie BlackJack erwähnt hat mit numarray/numpy:

Code: Alles auswählen

import array

f = open(filename,'rb')
data = f.read()
f.close()
arr = array.array('I') #TypeCode
#The following type codes are defined:
#    
#        Type code   C Type             Minimum size in bytes 
#        'c'         character          1 
#        'b'         signed integer     1 
#        'B'         unsigned integer   1 
#        'u'         Unicode character  2 
#        'h'         signed integer     2 
#        'H'         unsigned integer   2 
#        'i'         signed integer     2 
#        'I'         unsigned integer   2 
#        'l'         signed integer     4 
#        'L'         unsigned integer   4 
#        'f'         floating point     4 
#        'd'         floating point     8 
arr.fromString(data)

def index_to_whfc(index):
    return i/(240*100*3),(i%(240*100*3))/(100*3),(i%(100*3))/3,i%3
def whfc_to_index(w,h,f,c):
    return c+f*3+h*100*3+w*240*100*3

#Zugriff mit w,h,f,c
arr[whfc_to_index(10,20,5,0)]
#direkt mit index
arr[200] # rufe index_to_whfc(200) und du weisst wo du bist

Ist alles nicht wirklich getestet aber etwa so würde ich es lösen wenn es binäre Daten, die sich nicht ändern, sind.

Gruss
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

Montag 11. September 2006, 16:47

Na ja, 1000 Elemente sind nicht so furchtbar viel. Aber um welches array geht es denn? Python array oder numpy array? Und was gehört in das array hinein? Sind die Schleifen wirklich kritisch (wie häufig legst Du denn dieses oder ähnliche arrays in Deinem Programm an?)?

Gruß,
Christian

edit: PS Hatte die drei Posts vor mir gar nicht gesehen, die womöglich auch schon die Lage relativieren. Aber vielleicht lohnt es sich dennoch mal etwas mehr als "pass" zu posten ...
Zuletzt geändert von CM am Montag 11. September 2006, 16:58, insgesamt 1-mal geändert.
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Montag 11. September 2006, 16:51

ok jungs, langsam:

ich werde erst testen und dann nochmal nen konkreten fall schildern.
erstmal feierabend machen...


@rayo

hey was geht.
ich hab mir den kopf zerbrochen...
das ist genau das was ich suchte!

und das ding ist _nach_wie_vor_ doppelt so schnell! :wink:

Tausend Dank!

EDIT:

den code bzw die beziehung zw. mehreren indizies und einem einzigen solltet ihr euch merken!
in zukunft verwende ich immer dieses verfahren statt verschachtelten fors und geb noch als doku/kommentar an "same as..." damits nicht zu kompliziert wirkt...

aber erstmal die ganzen alten progrs nochmal umstellen und gucken wie sie laufen (hab auch ein paar nicht-python progs mit der konstellation...).

Danke nochmals! :D :D :D
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Montag 11. September 2006, 19:30

Statt range übrigens besser xrange nehmen.

range erzeugt jedesmal eine Liste mit n Elementen
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Montag 11. September 2006, 19:33

BlackJack hat geschrieben:Oh mann, komm mal von Deinem Optimierungstrip runter. Ich habe in "freier Wildbahn" noch nie gesehen das jemand die ``-OO`` Option verwendet. Dann ist die verschachtelte Schleife viel deutlicher als diese rum-modulo-riererei von dem einen Index.
Ganz meine Meinung.
-OO ist vollkommen sinnlos. Vielleicht wäre Psyco was für dich. Im Gegensatz zu -OO bringt es nämlich etwas
Benutzeravatar
akis.kapo
User
Beiträge: 127
Registriert: Freitag 1. September 2006, 12:58

Dienstag 12. September 2006, 22:54

@rayo

hier mal ne verallgemeinerte index zu 4d array methode:
(ich wollte mir auch ne ganz allgemeine einfallen lassen, war aber etwas kompliziert.)

Code: Alles auswählen

#!/usr/bin/python -OOO -fomit-frame-pointer -ffast-math -funroll-loops -fvery-aggressive-flag -fgreetings-to-BlackJack
def index_to_whfc(i,h,f,c):
    return i/(h*f*c),(i%(h*f*c))/(f*c),(i%(f*c))/c,i%c

def whfc_to_index(w,h,f,c,h_max,f_max,c_max):
    return c+f*c_max+h*f_max*c_max+w*h_max*f_max*c_max
Antworten