Alternative für copy.deepcopy

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
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Samstag 15. April 2006, 18:20

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...
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Samstag 15. April 2006, 18:37

salznase hat geschrieben:Frage: Gibt es eine schnellere Alternative zu deepcopy oder ein a=b[:] für mehrdimensionale Arrays?
Hi salznase!

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 ]
mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Samstag 15. April 2006, 18:42

salznase hat geschrieben:...wenn die Schleife zigtausende mal läuft.
Hi salznase!

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.
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Samstag 15. April 2006, 19:06

@gerold

Habe gleich deinen ersten Vorschlag getestet...
Ergebnis: vorher Berechnung 81Sekunden, jetzt 25 - hammerhart :D

(Ich frage mich jetzt nur: wieso ist deepcopy soviel langsamer...?)

Besten Dank
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Samstag 15. April 2006, 19:40

salznase hat geschrieben:Ich frage mich jetzt nur: wieso ist deepcopy soviel langsamer...?
Hi salznase!

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.
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Samstag 15. April 2006, 19:55

Habe mal einen Test laufen lassen:

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)
deepcopy braucht bei mir 23x so lange
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5555
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Oberhofen im Inntal (Tirol)
Kontaktdaten:

Samstag 15. April 2006, 20:04

salznase hat geschrieben:deepcopy braucht bei mir 23x so lange
List-Comprehension ist noch eine Spur schneller, wie ich soeben getestet habe.

Code: Alles auswählen

    x = [ item[:] for item in v ]
mfg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Sonntag 16. April 2006, 14:23

Für den Fall, dass du die 2D Liste als Matrix gebrauchst, solltest du dir mal NumPy, Numeric Python anschauen.
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Sonntag 16. April 2006, 17:35

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:

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;
rekursiv(m) würde in Python einen Zeiger weitergeben, keine "Kopie", die muß ich eben selbst machen.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Sonntag 16. April 2006, 18:18

Dein spezielles Beispiel ist allerdings besser als Schleife zu lösen...
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Sonntag 16. April 2006, 18:19

Abgesehen davon, was genau willst du machen? Wahrscheinlich gibt ein einen "pythonic way" für das, was du vorhast.

Es scheint mir nämlich, dass du Programmkonstrukte aus Pascal/C 1:1 nach Python übernehmen willst.
salznase
User
Beiträge: 18
Registriert: Montag 6. Juni 2005, 22:58

Sonntag 16. April 2006, 19:46

Dein spezielles Beispiel ist allerdings besser als Schleife zu lösen...
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.

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
BlackJack

Montag 17. April 2006, 07:12

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.
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.

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.
Antworten