Algorithmus zum "Umdrehen" von etwas

Es gibt 15 Antworten in diesem Thema. Der letzte Beitrag () ist von Selbi.

    Algorithmus zum "Umdrehen" von etwas

    Ich war mir nicht sicher, wie ich dieses Thema sonst betiteln hätte sollen.

    Jedenfalls, ich verstehe nicht so ganz, wie man (zum Beispiel) einen mehrdimensionalen Array einer beliebigen Sprache "umdrehen" kann, also wie das vom Gedanken her aussehen muss.

    Als Beispiel:

    Quellcode

    1. 00 01 02 03 04 05 06 07
    2. 08 09 10 11 12 13 14 15
    3. ...
    5. zu
    7. 07 06 05 04 03 02 01 00
    8. 15 14 13 12 11 10 09 08
    9. ...


    Die Länge pro Zeile weiß man (8 Einheiten), aber wie ergibt sich daraus nun der Algorithmus, um diese Zeile umzudrehen?

    Quellcode

    1. for i = 0 to 3
    2. tmp = arr[i]
    3. arr[i] = arr[7 - i]
    4. arr[7 - i] = tmp


    Edit: Python-Beispiel:

    Quellcode

    1. >>> x = [0, 1, 2, 3, 4, 5, 6, 7]
    2. >>> def reverse(data):
    3. length = len(data)
    4. i = 0
    5. while i <= int(length / 2) - 1:
    6. tmp = data[i]
    7. data[i] = data[length - 1 - i]
    8. data[length - 1 - i] = tmp
    9. i += 1
    10. return data
    12. >>> reverse(x)
    13. [7, 6, 5, 4, 3, 2, 1, 0]
    14. >>>
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Chrisber“ ()

    Chrisber schrieb:

    Quellcode

    1. for i = 0 to 3
    2. tmp = arr[i]
    3. arr[i] = arr[7 - i]
    4. arr[7 - i] = tmp

    Also quasi jeden einzelnen Wert temporär sichern, berechnen, welcher Wert an die gesicherte Stelle hinkommt und dann das ganze Tauschen?

    Ich weiß nicht... es klingt zwar plausibel, jedoch hört sich dies wie ein prozessorlastigen Aufwand an (dies ist für eine sehr alte Spielekonsole, und eigentlich sind die Daten im Format 16x16, hab ich vergessen zu sagen, sorry).

    Ist dies wirklich der "schnellste" Weg?

    Nein, das ist mit Sicherheit nicht der schnellste Weg, aber der einfachste. Es wird dafür bestimmt spezialisierte Algorithmen geben.
    Wenn es darum geht, Arrays zu sortieren, schau dir mal Quicksort an.

    Es hat sich für mich so angehört, als ob du nur verstehen wolltest, wie das Umdrehen funktioniert ;)

    Edit: Wenn ich recht überlege. Eigentlich sollte das doch die schnellste Methode sein. Mir fällt spontan kein anderer Weg ein. Mögliche Optimierung würde das umkopieren auf einen neuen Speicherbereich bringen. Ich weiß aber nicht was die Speicherallokierung auf der Konsole an Zeit kostet?

    So:

    Quellcode

    1. old[8] = (0, 1, 2, 3, 4, 5, 6, 7)
    2. new[8] = (0, 0, 0, 0, 0, 0, 0, 0)
    3. length = len(old)
    5. for i = 0 to length:
    6. new[i] = old[length - 1 - i]
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Chrisber“ ()

    Chrisber schrieb:

    Ich weiß aber nicht was die Speicherallokierung auf der Konsole an Zeit kostet?

    Das kann ich dir spontan auch nicht sagen, ich weiß aber aus Erfahrung, dass dies die Konsole ins laggen bringen wird.

    Naja, ein versuch ist es Wert. Ich werd einfach mal versuchen, die Theorie in die Praxis umzusetzen. Falls es doch einigermaßen funktioniert, sollte es nichts zu bedauern geben.

    Habe meinen Beitrag noch mal editiert.
    Um welche Konsole handelt es sich denn?

    Meinst du mit 16x16 eine an einem Stück zusammenhänge Matrix, die sich in einem Speicherbereich befindet?
    Wenn ja, wie wäre es damit, die Daten sofort im Speicher auszutauschen? Oder hast du darauf keinen Zugriff?

    Edit: In der Theorie sollte meine erste Variante eigentlich schneller sein, da die for-Schleife nur die Hälfte der Iterationen benötigt.
    Du müsstest halt mal einen Profiler anwerfen.

    Gruß
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Sega Mega Drive (Sprache: Motorola ASM 68000)

    Und wenn ich mir deinen Edit nochmal angucke, fällt mir ein, dass ich die Daten ja nur einmal verdrehen muss. Und anstatt erstmal den Kram in den Speicher zu laden und ihn dann umdrehen, könnte ich ihn direkt verdreht reinladen.

    So dürfte sich vielleicht die Ladezeit verlängern, aber dafür ist sie ja schließlich da. Danke. :)

    Darf ich fragen, was du mit der Kiste anstellen willst? Kann ja nur interessant werden :D

    Edit: Nach ein bisschen Suche im Internet habe ich einen Hinweis darauf gefunden, dass es mit xor-Methoden schneller ist. Und siehe da: In Python fast 2x schneller:

    Quellcode

    1. # meine Methode
    2. # 100.000 Durchgänge = 5.613832156579605
    3. def reverse(data):
    4. length = len(data)
    5. i = 0
    6. while i <= int(length / 2) - 1:
    7. tmp = data[i]
    8. data[i] = data[length - 1 - i]
    9. data[length - 1 - i] = tmp
    10. i += 1
    11. return data
    13. # xor-Methode
    14. # 100.000 Durchgänge = 3.5247015627933997 Sekunden
    15. def xor_reverse(data):
    16. length = len(data) - 1
    17. i = 0
    18. while i < length:
    19. data[i] ^= data[length]
    20. data[length] ^= data[i]
    21. data[i] ^= data[length]
    22. i += 1
    23. length -= 1
    24. return data


    Vielleicht hilft's ;)
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „Chrisber“ ()

    Ein Spiel spiegeln, also quasi von Rechts nach Links laufen, und nicht andersrum. Falls automatische Programmierung nicht geklappt hätte, hätte ich die Grunddateien mit irgendnem Programm verdreht, aber dann wäre es ja sicher keine Herausforderung mehr. :D

    Nebenbei, falls es dich interessiert, der Code würde am Ende etwa so aussehen (die Umkehrung ist da aber noch nicht drin):

    Quellcode

    1. lea (Daten).l,a1 ; lade Daten in a1
    2. lea ($FFFFD000).w,a2 ; Zieladresse in a2 laden
    3. moveq #15,d1 ; 15+1 mal
    5. Loop:
    6. move.l (a1)+,(a2)+ ; erste 4 Bytes kopieren
    7. move.l (a1)+,(a2)+ ; zweite 4 Bytes kopieren
    8. dbf d1,Loop ; Schleife ausführuen

    Habe meinen Beitrag schon wieder geupdatet ;)
    Mich würde jetzt ein Profiling auf deiner Kiste auch mal interessieren :>

    Edit: Euphorie-Fail - ich habe die Berechnung der while-Schleife optimiert. Nun ist meine Variante wieder schneller:

    Quellcode

    1. # meine Variante
    2. # 100.000 Durchgänge = 3.0967334765085184
    4. def reverse(data):
    5. length = len(data)
    6. i = 0
    7. l = int(length / 2) - 1
    8. while i <= l:
    9. tmp = data[i]
    10. data[i] = data[length - 1 - i]
    11. data[length - 1 - i] = tmp
    12. i += 1
    13. return data
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    So, ich hab mal versucht deine Methode in ASM umzuwandeln, getestet hab ich sie noch nicht, sieht aber sehr vielversprechend aus:

    Quellcode

    1. lea (Daten).l,a1 ; lade Daten in a1
    2. lea ($FFFFD000).w,a2 ; Zieladresse in a2 laden
    3. moveq #15,d1 ; 15+1 mal
    5. Loop1:
    6. moveq #7,d2 ; 7+1 Einheiten pro Zeile
    8. Loop2:
    9. move.b (a1,d2.w),d0 ; a1,d2 heißt soviel wie "a1 + d2"
    10. move.b (a1,d3.w),(a2,d2.w) ; Bsp: 0 -> 7
    11. move.b d0,(a2,d2.w) ; Bsp: 7 (gesichert) -> 0
    12. addq.b #1,d3 ; d3 um 1 erhöhen
    13. dbf d2,Loop2 ; Sub-Schleife ausführen
    15. dbf d1,Loop1 ; Schleife ausführuen


    Das Problem mit meiner Sprache ist, dass man hier kaum möglichkeiten hat Schleifen zu benutzen. Sowas wie eine einfache While i Schleife, hab ich leider nicht, weshalb ich mit Tricks arbeiten muss.

    Chrisber schrieb:

    Quellcode

    1. for i = 0 to 3
    2. tmp = arr[i]
    3. arr[i] = arr[7 - i]
    4. arr[7 - i] = tmp

    Es geht natürlich auch ohne tmp-Variable.

    Quellcode

    1. for i = 0 to 3
    2. arr[i] = arr[i] + arr[7 - i]
    3. arr[7 - i] = arr[i] - arr[7 - i]
    4. arr[i] = arr[i] - arr[7 - i]

    Skybird schrieb:

    Das sind ja Ubisoftmethoden hier !

    Quellcode

    1. # vb-checker Variante
    2. # 100.000 Durchgänge = 5.077815878925323
    3. def reverse(data):
    4. length = len(data)
    5. i = 0
    6. l = int(length / 2) - 1
    7. while i <= l:
    8. data[i] = data[i] + data[length - 1 - i]
    9. data[length - 1 - i] = data[i] - data[length - 1 - i]
    10. data[i] = data[i] - data[length - 1 - i]
    11. i += 1
    12. return data

    Auf Grund der vielen Array-Zugriffe unbrauchbar. Funktioniert außerdem nur mit Zahlen. Trotzdem nette Idee ^^

    Edit: Oh man. Wie ich solche Themen liebe. Bin schon die ganze Zeit am überlegen wie man das optimieren kann...
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Saublödes Problem: Mir ist grad aufgefallen, dass ich nicht nur die Bytes umdrehen muss, sondern auch die Nibbels. Dass heißt, es müsste eigentlich so sein:

    Quellcode

    1. 00 01 02 03 04 05 06 07
    2. 08 09 10 11 12 13 14 15
    3. ...
    5. zu
    7. 70 60 50 40 30 20 10 00
    8. 51 41 31 12 11 01 90 80
    9. ...


    Oh man, das ist jetz peinlich... :|

    Dann musst du wohl mit einzelnen Bytes arbeiten. Sollte in deiner ASM-ähnlichen Sprache kein Problem darstellen.
    To make foobar2000 a real random music player, I figured out the only way to achieve this is to use Windows Media Player.

    “At some point in time, you recognize that knowing more does not necessarily make you more happy.”

    Quellcode

    1. lea ($FF0000).l,a1
    2. move.w #$51F,d4
    4. Loop1:
    5. moveq #7,d5
    6. moveq #0,d2
    7. moveq #$1E,d3
    9. Loop2: move.w (a1,d2.w),d0
    10. move.w (a1,d3.w),(a1,d2.w)
    11. move.w d0,(a1,d3.w)
    12. addq.b #2,d2
    13. subq.b #2,d3
    14. dbf d5,Loop2
    15. adda.w #$20,a1
    16. dbf d4,Loop1


    Der entgültige, getestete und funktionierende Code, basierend auf deinen Algo. Tausend Dank! :thumbsup:

Facebook
Telefonspende