Hallo Besucher, der Thread wurde 9,5k mal aufgerufen und enthält 62 Antworten

letzter Beitrag von Tale-X am

BASIC Compo 2018: Apfelmännchen beschleunigen

    Wird den Wert von ti$ nicht groß ändern... :bgdev


    Nach gerade mal einen Tag kann ich schon sagen: :respect:


    EgonOlsen71 hat das Teil so richtig beschleunigt (mehr als ich erwartet hatte) und Enthusi und ADAC haben dass dann sogar noch etwas nachgefeilt. Bin schon gespannt, ob das jetzt das Ende der Fahnenstange ist, oder ob nicht doch noch ein Quantensprung möglich ist... :)


    oobdoo: tja, hier zählt Köpfchen statt MHz :D

    Mal so als garantiert noch verbesserbarer Denkanstoss: Ein Pixel, der das Iterationslimit erreicht bleibt selten allein, nur an den Rändern der Mandelbrotmenge muss man ein wenig aufpassen.


    1:21

    Zitat von Unseen

    Mal so als garantiert noch verbesserbarer Denkanstoss: Ein Pixel, der das Iterationslimit erreicht bleibt selten allein, nur an den Rändern der Mandelbrotmenge muss man ein wenig aufpassen.

    Das funktioniert für dieses Beispiel, aber wäre es nicht allgemein so, dass du z.B. im Falle


    32 40 32 32 32


    Stattdessen damit


    32 32 32 32 32


    rendern würdest?

    Was übrigens immer lästig ist bei diesem Apfelmännchen, das ist der Pixel an der linken Spitze. Der ist leider sehr anfällig für Gleitkommaungenauigkeiten, so dass ein im Prinzip äquivalenter Algorithmus dort u.U. eine Ungenauigkeit einführt, einfach weil sich (unvermeidbare) Fehler anders auswirken. Ich habe schon einige Umstellungen im Code nicht weiter verfolgt, weil dann dort kein Leerzeichen, sonden ) oder `rauskam. Das ist leider normal, das "Problem" habe ich mit meinem Compiler auch schon gesehen...

    Korrekt - aber so ungefähr jeder Ansatz, der Flächen anhand der berechneten Pixel erkennen will hat solche Probleme.

    Könnte man den Ansatz von Unseen nicht dahingehend abändern, dass man nicht nur in x- sondern auch in y-Richtung die benachbarten Felder berücksichtigt? Spätestens wenn alle 8 umliegenden Felder das Limit überschritten haben, sollte es doch unwahrscheinlich sein, dass der gerade betrachtete Punkt das Limit nicht erreicht.


    Ansonsten hab ich mit dem Ansatz von EgonOlsen71 herumgespielt und bin auf 1:37 gekommen. Also da geht noch was ;)

    Zitat von Tale-X

    Könnte man den Ansatz von Unseen nicht dahingehend abändern, dass man nicht nur in x- sondern auch in y-Richtung die benachbarten Felder berücksichtigt? Spätestens wenn alle 8 umliegenden Felder das Limit überschritten haben, sollte es doch unwahrscheinlich sein, dass der gerade betrachtete Punkt das Limit nicht erreicht.

    Im Prinzip schon, denn laut Wiki ist die Mandelbrotmenge zusammenhängend, d.h. es gibt
    keine Inseln/isolierte Punkte. ABER: die berechneten Punkte sind ja nur durch Sampling
    des Koordinatensystems entstanden, d.h. es können schon isolierte Pixel auftreten.
    Eine solche Suche stelle ich mir auch schwierig vor.


    Zur allgemeinen Betrachtung von Nachbarpunkten: Die Mandelbrotmenge basiert ja auf
    Chaos, d.h. benachbarte Punkte in irgendeiner Weise in Beziehung zu setzen ist iA sinnlos.

    Hier die Fassung mit 1:37 Laufzeit. Den "größten" Zeitvorsprung brachte die Umstellung auf print (sparte mehrere Variablen und Anweisungen ein), das Rumspielen mit der Reihenfolge in Zeile 8 brachte dabei nochmal 1-2 Sekunden.

    Offenbar ist tatsächlich beim exakten Apfelmännchen das Ende der Fahnenstange erreicht. Wobei eine Zeitreduzierung gleich im ersten Ansatz von 4:53 auf 1:43 (BASIC Compo 2018: Apfelmännchen beschleunigen) wirklich mehr als beachtlich sind (und das ohne die Tricks wie . statt 0 und dergleichen, sondern nur durch neu arrangieren des Codes).


    Die erste Runde geht damit definitiv an EgonOlsen71 :lol23:



    Und nun? Nun, mir hat auch Unseens Ansatz gefallen... Deshalb liegt in Runde zwei der Schwerpunkt auf Tempo:

    • Ziellaufzeit unter 1:10
    • Bild nur noch so ähnlich wie möglich
    • Ähnlichkeit wird Anzahl abweichender Buchstaben gemessen
    • Abweichende Buchstaben bei i3/i=0.0 (auf der Spiegelachse) zählen doppelt, da diese stark die Optik des Apfelmännchen prägen
    • Ansonsten gleiche Randbedingungen (nur Peeks/Pokes im Bild-/Farbram, Zeitzählzeilen bleiben unangetastet, kein sys/usr...)


    Bei gleicher Ähnlichkeit gewinnt der schnellere Algorithmus...

    Zitat von Tale-X

    Hier die Fassung mit 1:37 Laufzeit. Den "größten" Zeitvorsprung brachte die Umstellung auf print (sparte mehrere Variablen und Anweisungen ein), das Rumspielen mit der Reihenfolge in Zeile 8 brachte dabei nochmal 1-2 Sekunden.

    1min 8sek in Loco. :bgdev


    Apfel.DSK


    Programm ist apfel2.bas. Die Zeit habe ich mit Öffnen der Windows Uhr genommen.


    Aber schon interessant zu sehen, wie dicht ein optimiertes V2 BASIC an Loco rankommen kann.

    Code
    1. 1 gosub5:fori=.to22:w=1-i/11:forj=.to38:v=3*j/38-2:x=.:y=.
    2. 2 forz=.to15:m=x*x:n=y*y:y=2*x*y+w:x=m-n+v:ifm+n>4thenpoke1064+i*40+j,49-z:z=16
    3. 3 nextz,j,i:goto7
    4. 4 rem -----------
    5. 5 print chr$(147)
    6. 6 return
    7. 7 ti$="000000"
    8. 8 printchr$(17);:i=i-1:ifigoto8
    9. 10000 print"zeit: ";ti$;
    10. 10010 geta$:if a$="" then 10010
    • Keine Maschinensprache (weder sys, noch usr) √
    • Zeilen 5, 7, 10000 und 10010 bleiben unangetastet √
    • Formeln, Abläufe dürfen nach Herzenslust umgestellt/vereinfacht etc. werden √
    • aber die Grafik muss während des Programmablaufs berechnet werden √
    • Keine POKEs! Ausgenommen Bild- und Farbram √

    .. bei null angekommen √ 8)


    .. ♫ Witzischkeit kennt keine Grenzen ♪♫ .. :party2:


    atom-000000.bas.prg

    achsooo :saint:
    Ok, Nonsense beiseite.


    Ich glaube, dass wir in gewisser Hinsicht schon am Ende angelangt sind, sofern man sich nicht das Wissen über das Aussehen des vorgegebenen Bereichs zunutze machen will. Was die mathematischen Grundlagen angeht, kann man da ja nicht viel ändern, außer die rechnerische Auflösung zu reduzieren, was lediglich mit einer noch schlechteren Darstellung korreliert. Jeder Versuch, es rein algorithmisch noch weiter zu beschleunigen, würde wahrscheinlich mehr oder weniger in Richtung PRINT"..." gehen, also das Wissen über das Aussehen ausnutzen. Unseens Algorithmus kratzte ja bereits etwas an dieser Tatsache. Würde man mit i1=-1.1:i2=1.1 das AM etwas stauchen, hätten wir in der Zeile 11 die Zeichenfolge 0---++*) ... statt 0---++*) # ....


    Individuelle Beschleunigungsalgorithmen, den zähen Morast im Inneren größtenteils zu überspringen, sind möglich, aber leider ist keine davon für diese Aufgabe hier geeignet. Ich habe probiert, die 3 Zeichen jeweils über dem zu rendernden Zeichen zu prüfen und komme damit auf ca. 1:25, also nichts schneller.


    Zwei schnelle Methoden, die hier leider nicht möglich sind:


    1. Beim *Zoomen* in das Apfelmännchen den bereits berechneten Morast entsprechend für die nächste Stufe vergrößern. Beim Rendern wird der Rand der vergrößerten Innenfläche bei einer evtl. Berührung etwas "ausgeschabt". Die verbleibende Innenfläche wird übersprungen. Man kann dabei leider nur kleine Zoomschritte wählen, weil dünnes Geäst, das zum ersten Mal sichtbar wird, sonst einfach weg radiert würde.


    2. Den inneren Rand finden, daran entlang hangeln und markieren. Dann das Äußere zeilenweise rendern und die Markierung zum Überspringen nutzen. Ist für hohe Auflösungen geeignet und kann sich auch für die anderen Flächen lohnen.
    Habe ich für diese Aufgabe ausprobiert, aber da dauert das Finden der Begrenzung bereits eine Minute, sodass es im Verhältnis zur gesamten Berechnung keinen Gewinn darstellt.


    Trotzdem habe ich mal zwei Versionen gemacht, die zwar schnell sind, aber eben auch die Kenntnis übers Aussehen nutzen und somit nicht allzu qualifiziert sein dürften.


    1. Statt aus einer vorherigen Zoomstufe das Innere für eine Maske zu vergrößern, habe ich zuerst eine grobe Berechnung davon gemacht. Das klingt soweit noch ganz sportlich, wäre da nicht der Umstand, dass diese Berechnung für das gegebene AM genau angepasst ist und zudem die Schleifen für diese Berechnung gecropped wurden. Ich meine, wieso sollte man irgendwo herumlaufen, wo man nichts machen will.^^ Wäre die Form aber vorher nicht bekannt, wäre das eben nicht möglich. Von der Ausgabe her entspricht es der Aufgabenstellung 1 (von Z. 10000ff abgesehen).

    2. Die nächste Lösung ist mit 55 Sek. schneller und sogar etwas sportlicher als meine erste, reicht aber eindeutig nur für Aufgabenstellung 2, da ein Zeichen verlorengeht (zwei inkl. Spiegelung). Wie schon in meiner ersten Lösung wird die mittlere Zeile nur so weit berechnet wie nötig, also wieder die Ausnutzung der Kenntnis. Ansonsten ist hier das Grundprinzip, einfach beim Reinlatschen in den Morast sofort anzuhalten. Wäre für eine hohe Auflösung oder andere Ausschnitte des AM fatal.


    Herunterladung: apfelmus.d64


    Das Prinzip der Beschleunigung mit Hilfe des genauen Wissens über das zu erwartende Ergebnis ist ja das, was Demo-Programmierer für Effekte nutzen, die extrem rechenintensiv wären. Deswegen finde ich es problematisch, wo man bei solch einem Wettbewerb die Grenzen ziehen will.


    Man müsste es beim Apfelmännchen dann schon so machen, dass man mit seiner Lösung beliebige Ausschnitte berechnen kann, die Zeit aber mit einem ganz bestimmten Ausschnitt gemessen wird. Z.B. in dem man ein Viertel des Ausgangsbildes mit einem Rand aus invertierten Zeichen versieht und dieses Rechteck in einen der vier Viertel verschiebt, dann SPACE drückt und den Ausschnitt berechnen lässt. Gemessen werden könnte bspw. die Berechnung des oberen linken Quadrants, also der erste Zoomschritt dieser Ecke. Abgesehen davon, dass meine beiden Lösungen dafür sowieso nicht mehr geeignet wären, würde aber auch bei Unseens Lösung die Gefahr bestehen, dass unter anderem diese beiden langen Einschnürungen am Hals des AM abgeschnitten würden.


    Noch spannender fände ich das ganze in HiRes mit einer Punktwahrscheinlichkeit von 0 bis 15, also random gedithert, innerer Rand mit voller Wahrscheinlichkeit, nach außen hin weniger und innen 0, für BASIC bei vllt. 160x100 px. Das Ziel wäre vermutlich so 10 Minuten.

    Zitat von atomcode

    Was die mathematischen Grundlagen angeht, kann man da ja nicht viel ändern, außer die rechnerische Auflösung zu reduzieren, was lediglich mit einer noch schlechteren Darstellung korreliert. Jeder Versuch, es rein algorithmisch noch weiter zu beschleunigen, würde wahrscheinlich mehr oder weniger in Richtung PRINT"..." gehen, also das Wissen über das Aussehen ausnutzen.

    Na ja, es gibt recht einfache Formeln um zu berechnen, ob ein Punkt in der "Herzform" rechts oder im grossen Kreis links daneben liegt. Ob das in BASIC mehr Rechenzeit rausholt als es kostet weiss ich allerdings nicht.