deepcopy zu langsam?
Verfasst: Montag 26. Juni 2006, 16:05
Hallo 
ich habe für Minesweeper einen Algorithmus programmiert, der jede erdenkliche Möglichkeit von Minen in der näheren Umgebung konstruiert und die Realisierungen, die nicht konform mit den Bedingungen sind, streicht.
Bei sehr großen Feldern braucht der Algorithmus ca. 30 sekunden, wovon deepcopy aus dem modul copy 20 sekunden also 2/3 der zeit verschlingt. Auf das deepcopy bin ich, denke ich, angewiesen, da ich die alten "maps" kopieren muss und die neue info aus der aktuellen iteration hinzufüge...
Eine Map ist dabei als Hash/Dictionary aufgebaut, in das ich die Koordinaten als key hineingebe. Als value erhalte ich dann eine Liste mit drei Elementen, wobei alle Elemente Integer sind. Das erste bezeichnet den Zustand des Feldes (markierte Bombe, versteckt oder Zahl), das nächste die Anzahl der angrenzenden markierten Bomben und der letzte Eintrag enthält die Zahl der anliegenden versteckten Felder (schien mir lohnenswert diese zu speichern, da ich sie sehr oft brauchte)
Gibt es nun eine Möglichkeit dieses lästige deepcopy zu beschleunigen?
Wahrscheinlich, wenn ich mein Feld anders kodieren würde, anstatt ein Dictionary zu verwenden. Vielleicht einfach nur eine lineare liste, bei der ich den "Zeilenumbruch" selbst herausrechne und so meine Koordinaten (x,y) transformiere? also anstelle von dict[(x,y)] schreib ich dann list[ x+y*felderprozeile ] ?
Würde das helfen? Gibt's noch eine andere Möglichkeit?
Danke für eure Zeit und Mühe
ich habe für Minesweeper einen Algorithmus programmiert, der jede erdenkliche Möglichkeit von Minen in der näheren Umgebung konstruiert und die Realisierungen, die nicht konform mit den Bedingungen sind, streicht.
Bei sehr großen Feldern braucht der Algorithmus ca. 30 sekunden, wovon deepcopy aus dem modul copy 20 sekunden also 2/3 der zeit verschlingt. Auf das deepcopy bin ich, denke ich, angewiesen, da ich die alten "maps" kopieren muss und die neue info aus der aktuellen iteration hinzufüge...
Eine Map ist dabei als Hash/Dictionary aufgebaut, in das ich die Koordinaten als key hineingebe. Als value erhalte ich dann eine Liste mit drei Elementen, wobei alle Elemente Integer sind. Das erste bezeichnet den Zustand des Feldes (markierte Bombe, versteckt oder Zahl), das nächste die Anzahl der angrenzenden markierten Bomben und der letzte Eintrag enthält die Zahl der anliegenden versteckten Felder (schien mir lohnenswert diese zu speichern, da ich sie sehr oft brauchte)
Gibt es nun eine Möglichkeit dieses lästige deepcopy zu beschleunigen?
Wahrscheinlich, wenn ich mein Feld anders kodieren würde, anstatt ein Dictionary zu verwenden. Vielleicht einfach nur eine lineare liste, bei der ich den "Zeilenumbruch" selbst herausrechne und so meine Koordinaten (x,y) transformiere? also anstelle von dict[(x,y)] schreib ich dann list[ x+y*felderprozeile ] ?
Würde das helfen? Gibt's noch eine andere Möglichkeit?
Danke für eure Zeit und Mühe
