Ich möchte gern erreichen, dass folgende Funktion auch für n=4 und höher entsprechend schnell läuft:
Code:
function c=sandhaufen(a,b,n)
c=a+b;
whileany(c(:)>3) for i=1:n
for j=1:n
if c(i,j)>3
c(i,j)=c(i,j)-4;
endif
if i-1>0
c(i-1,j)=c(i-1)+1;
endif
if i+1<=n
c(i+1,j)=c(i+1,j)+1;
endif
if j-1>0
c(i,j-1)=c(i,j-1)+1;
endif
if j+1<=n
c(i,j+1)=c(i,j+1)+1;
endif
endfor
endfor
Das Problem ist halt, dass es bis n=3 eine Sache von teils unter einer Sekunde ist. Allerdings habe ich den Test eben auch mit n=4 gemacht und da war er nach über 30 Minuten immer noch nicht fertig. Ich muss das ganze aber tatsächlich für n=101 realisieren :/
Hat jemand eine Idee, wie man das beschleunigen kann? :/
Hier mal die Grundlage, was bei der Berechnung passieren soll:
Die Einträge aus A und B werden elementweise addiert.
Da das Ergebnis jetzt aber größer als drei sein kann, wird \textbf{normalisiert} -- der Sandhaufen rutscht. Jedes Element, welches größer als drei ist, besitzt einen Überschuss. Dieser wird nun gleichmäßig an seine \textbf{vier} Nachbarn links, rechts, oben und unten verteilt, so dass der Eintrag des Elements nachher kleiner als vier ist. Sollte einer der Nachbarn nicht vorhanden sein (da das Element am Rand der Matrix ist), rutscht der Anteil über den Rand -- er verfällt. Diesen Vorgang führen alle Elemente \textbf{gleichzeitig} aus und es können wieder Elemente entstehen, die größer als drei sind. Daher wird der Normalisierungsschritt so oft wiederholt, bis alle Elemente kleiner als vier sind.
Der Input sind dabei nxn-Matrizen.
An sich macht der Code ja schon genau das, was er soll. Er ist nur für spätestens 4x4-Matrizen sehr langsam :/
Ich habe deinen Code mal in Matlab kopiert und mit magic(3) als Matrix ausführen lassen. Damit endet die Funktion nie, da du in einer Endlosschleife gefangen bist.
Weiterhin entspricht der Code auch nicht der Beschreibung: Du schiebst immer nur fest 4 Elemente zur Seite, jedoch soll der Überschuss (der auch z.B. 20 sein kann) gleichmäßig verteilt werden, so dass direkt in einem Schritt der Haufen kleiner 4 ist.
Also, ich habe jetzt erst einmal den Code folgendermaßen angepasst:
Code:
function c=sandhaufen(a,b)
c=a+b;
whileany(c(:)>3) for i=1:length(c) for j=1:length(c) if c(i,j)>3
c(i,j)=c(i,j)-4;
if i-1>0
c(i-1,j)=c(i-1,j)+1;
endif
if i+1<=length(c)
c(i+1,j)=c(i+1,j)+1;
endif
if j-1>0
c(i,j-1)=c(i,j-1)+1;
endif
if j+1<=length(c)
c(i,j+1)=c(i,j+1)+1;
endif
endif
endfor
endfor
figure mesh(c);
view([4545]);
endwhile
endfunction
Jetzt funktioniert er auf jeden Fall schon einmal deutlich schneller und vor allem, ohne, dass man die Variable n vorgeben muss.
Zitat:
Ich habe deinen Code mal in Matlab kopiert und mit magic(3) als Matrix ausführen lassen. Damit endet die Funktion nie, da du in einer Endlosschleife gefangen bist.
Das habe ich mit der angepassten Variante nochmal versucht und da hat es in unter einer Sekunde aufgehört und das Ergebnis nach wenigen Schritten angezeigt.
Zitat:
Weiterhin entspricht der Code auch nicht der Beschreibung: Du schiebst immer nur fest 4 Elemente zur Seite, jedoch soll der Überschuss (der auch z.B. 20 sein kann) gleichmäßig verteilt werden, so dass direkt in einem Schritt der Haufen kleiner 4 ist.
Dass das nicht in direkter Weise passt, ist mir auch klar, aber dieses -4 ist tatsächlich wohl überlegt. Schlagwort in der Aufgabe ist hier "gleichmäßig". Das bedeutet im Umkehrschluss, dass der Überhang auch durch 4 teilbar sein muss und im Zweifel eben mehr als der bloße Überhang abgezogen werden muss, um ihn zu verteilen.
Und da ich keine Idee hatte dem Programm zu sagen, dass es von der Zahl etwas abziehen soll, sodass sie kleiner als vier sein soll und gleichzeitig dieses Abgezogene durch 4 teilbar sein soll, habe ich mich entschieden, das so zu schreiben, dass er das eben immer in 4er-Schritten machen soll.
Wenn du also eine Möglichkeit hast, wie man das in nur einem Schritt realisieren kann, dann bin ich tatsächlich sehr offen dafür
Du musst die Zahl durch 4 teilen und abrunden, dann weißt du, was du abziehen musst.
Code:
if c(i,j)>3
d = floor(c(i,j)/4);
c(i,j)=c(i,j)-d*4;
if i-1>0
c(i-1,j)=c(i-1,j)+d;
end if i+1<=length(c)
c(i+1,j)=c(i+1,j)+d;
end if j-1>0
c(i,j-1)=c(i,j-1)+d;
end if j+1<=length(c)
c(i,j+1)=c(i,j+1)+d;
end
Damit läuft die Berechnung dann für magic(100) in wenigen Sekunden durch, kannst ja mal für deine Daten testen. Die for-Schleifen eliminieren und die Funktion auf jedes (relevante) Element anwenden, könnte(*) auch noch helfen, aber so recht fiel mir da auch nichts ein.
(*) Könnte deswegen, weil seit ein paar Releases ist die Performance von for-Schleifen drastisch verbessert worden und keine "Todsünde" mehr, wie noch vor ein paar Jahren.
Also die Lösung gefällt mir tatsächlich deutlich besser, da sie irgendwie eleganter wirkt. Zeitlich bringt sie aber leider keine Vorteile, ganz im Gegenteil.
In meinem speziellen Anwendungsfall habe ich eine 101x101-Matrix, die an der Stelle 51,51 eine 2^14 stehen hat und eine 101x101-Nullmatrix.
Bei denen brauchte mein ursprünglicher Code 1016 Sekunden und der jetzt 1196 Sekunden.
Aber wie gesagt, schöner ist er auf jeden Fall mal
Interessant, in Matlab 2018 läuft die Berechnung mit "meiner Methode" in unter 1 Sekunde bei 1863 Schleifendurchläufen durch:
Zitat:
z =
1863
Elapsed time is 0.387725 seconds.
Mit deiner Methode (ohne Berechnung von d) braucht es knapp über eine Sekunde bei 13493 durchläufen:
Zitat:
z =
13493
Elapsed time is 1.431246 seconds.
Dass es bei dir so viel langsamer läuft, liegt u.U. am Unterschied Octave <-> Matlab, dazu kann ich aber nichts sagen. Dennoch wundert es mich, dass der Code für weniger Schleifendurchläufe mehr Zeit in Anspruch nehmen soll.
Dennoch wundert es mich, dass der Code für weniger Schleifendurchläufe mehr Zeit in Anspruch nehmen soll.
Das Problem ist hier weniger die Anzahl der Durchläufe, denke ich mal. Das Problem ist eher die 2^14, die in der Mitte normalisiert werden soll. Das heißt ja dementsprechend auch, dass er entsprechend viel Rechenleistung aufwenden muss.
Die Schleifendurchläufe hängen doch u.a. direkt von den Matrixeinträgen ab. Die Zahlen oben waren konkret für deine Matrix mit einer 2^14 in der Mitte (die restlichen Stellen mal als 0 angenommen, da hierüber keine Information). Selbst für eine Matrix
läuft der Code mit Berechnung von d einigermaßen "schnell" durch.
Zitat:
z =
10584
Elapsed time is 7.638236 seconds.
Ohne d läuft die Berechnung noch, daher kann ich es nicht nachvollziehen, warum sich das bei dir anders verhält.
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
RSS