Hallo
Ich schreibe ein Programm wo eine 2-dimensionale Liste* rekursiv als Parameter übergeben wird, als Kopie.
(*) Beispiel: a = [[1,1,1],[2,2,2],[3,3,3]]
Mit copy.deepcopy funktioniert das auch gut, allerdings ist es zu langsam wenn die Schleife zigtausende mal läuft.
Eine 1-dimensionale Liste könnte man mit a=b[:] kopieren...
Frage: Gibt es eine schnellere Alternative zu deepcopy oder ein a=b[:] für mehrdimensionale Arrays?
Danke für jede Hilfe...
Alternative für copy.deepcopy
- gerold
- Python-Forum Veteran
- Beiträge: 5555
- Registriert: Samstag 28. Februar 2004, 22:04
- Wohnort: Oberhofen im Inntal (Tirol)
- Kontaktdaten:
Hi salznase!salznase hat geschrieben:Frage: Gibt es eine schnellere Alternative zu deepcopy oder ein a=b[:] für mehrdimensionale Arrays?
Ich glaube, dass deepcopy ziemlich viele Fälle abdeckt, die für dich nicht interessant sind, da du die Struktur deiner Liste kennst.
Folgende Varianten könntest du mal ausprobieren. Vielleicht sind sie ja schneller:
Code: Alles auswählen
new_list = []
for item in old_list:
new_list.append(item[:])
Code: Alles auswählen
new_list = [ item[:] for item in old_list ]
Gerold
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
- gerold
- Python-Forum Veteran
- Beiträge: 5555
- Registriert: Samstag 28. Februar 2004, 22:04
- Wohnort: Oberhofen im Inntal (Tirol)
- Kontaktdaten:
Hi salznase!salznase hat geschrieben:...wenn die Schleife zigtausende mal läuft.
Bei vielen Wiederholungen hilft oft auch der zusätzliche Einsatz von Psyco. Das musst du allerdings selbst ausprobieren, weil das von Fall zu Fall verschieden ist.
Pyrex könnte eventuell auch helfen, aber das habe ich noch nie ausprobiert.
mfg
Gerold
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
- gerold
- Python-Forum Veteran
- Beiträge: 5555
- Registriert: Samstag 28. Februar 2004, 22:04
- Wohnort: Oberhofen im Inntal (Tirol)
- Kontaktdaten:
Hi salznase!salznase hat geschrieben:Ich frage mich jetzt nur: wieso ist deepcopy soviel langsamer...?
Wie ich schon bemerkte: deepcopy weiß nicht, dass es nur eine Liste mit weiteren Listen in der zweiten Ebene ist. Es muss erst die Struktur deiner Liste ermitteln und bei jedem Element wieder prüfen um was für ein Objekt es sich handelt und ob es wieder Unterobjekte hat. Das fällt alles weg, wenn du dich selber darum kümmerst. Du musst nicht erst prüfen was du umwandeln willst. Du weißt es schon.
Allerdings ist das jetzt nur Spekulation, da ich mir den Quellcode nicht angesehen habe.
mfg
Gerold
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Habe mal einen Test laufen lassen:
deepcopy braucht bei mir 23x so lange
Code: Alles auswählen
import time,copy
v=[[0,0,0,0,0,0,0],
[0,0,2,2,0,0,0],
[0,0,2,1,0,0,0],
[0,0,1,1,0,0,0],
[0,1,2,2,0,0,0],
[0,1,2,1,0,0,0]]
Tests = 10000
t1 = time.time()
for i in range(Tests):
x = []
for items in v:
x.append(items[:])
t1 = time.time() - t1
print "Zeit selbst kopieren: " + str(t1)
t2 = time.time()
for i in range(Tests):
x = copy.deepcopy(v)
t2 = time.time() - t2
print "Zeit mit deepcopy: " + str(t2)
- gerold
- Python-Forum Veteran
- Beiträge: 5555
- Registriert: Samstag 28. Februar 2004, 22:04
- Wohnort: Oberhofen im Inntal (Tirol)
- Kontaktdaten:
List-Comprehension ist noch eine Spur schneller, wie ich soeben getestet habe.salznase hat geschrieben:deepcopy braucht bei mir 23x so lange
Code: Alles auswählen
x = [ item[:] for item in v ]
Gerold
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Danke für eure Hilfe...
Mein "Problem" habe ich *imho* nur weil es in Python keine statischen Variablen gibt, alles ein Pointer ist(eines der Dinge die ich manchmal grausam finde).
In Pascal würde ich es z.B. so machen:
rekursiv(m) würde in Python einen Zeiger weitergeben, keine "Kopie", die muß ich eben selbst machen.
Mein "Problem" habe ich *imho* nur weil es in Python keine statischen Variablen gibt, alles ein Pointer ist(eines der Dinge die ich manchmal grausam finde).
In Pascal würde ich es z.B. so machen:
Code: Alles auswählen
type tmein_array = array[1..8,1..16] of integer;
Procedure rekursiv(m:tmein_array);
begin
m[x,y] := ...
rekursiv(m);
end;
Nein, je nachdem wieviele Möglichkeiten es in dem Array gibt weiterzuberechnen gebe ich eine Kopie rekursiv weiter die an einem anderen Punkt weitermacht: eine Baumstruktur. Im Prinzip wie das suchen einer Datei auf der Festplatte, jede Möglichkeit des Arrays ist wie ein Unterordner.Dein spezielles Beispiel ist allerdings besser als Schleife zu lösen...
Ich hatte mal einen Pascal-Code eines Sudoku-Lösungssuche gesehen, der brauchte auf meiner alten Kiste ca 0.1Sek(?). In diesem Forum hat auch jemand mit Python so ein Lösungs-Tool geschrieben(LINK) welches wohl denselben Weg ging, braucht aber etwa 10x so lange. Was finde ich in dem Code? > copy.deepcopy, wegen Rekursion. In dem Beispielprogramm mehr als 2200 aufgerufen, deshalb wohl die längere Zeit.
ciao
Meine Lösung in dem Thread ist ebenfalls rekursiv. Ich ändere aber die Originaldatenstruktur vor dem Aufruf und mache diese Änderung danach wieder rückgängig. Das ist wesentlich "billiger", sowohl was Zeit als auch Speicher angeht, als jedesmal die gesamte Datenstruktur zu kopieren. Eine Kopie wird nur von gefundenen Lösungen gemacht.salznase hat geschrieben:Ich hatte mal einen Pascal-Code eines Sudoku-Lösungssuche gesehen, der brauchte auf meiner alten Kiste ca 0.1Sek(?). In diesem Forum hat auch jemand mit Python so ein Lösungs-Tool geschrieben(LINK) welches wohl denselben Weg ging, braucht aber etwa 10x so lange. Was finde ich in dem Code? > copy.deepcopy, wegen Rekursion. In dem Beispielprogramm mehr als 2200 aufgerufen, deshalb wohl die längere Zeit.
Das es nur "Zeiger" gibt, finde ich eigentlich sehr schön, weil man auf diese Weise nicht immer überlegen muss, ob bei einem Funktions- oder Methodenaufruf nun eine Kopie angelegt wird, und wie tief die eigentlich ist, oder nicht. Das dachten sich wohl auch die Entwickler von Java, da ist's ja genau so.