Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

 
Gast > Registrieren       Autologin?   

Bücher:

Das Abenteuer modellbasierter Softwareentwicklung

Studierende:
weitere Angebote

Partner:


Vermarktungspartner


Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Code beschleuingen

 

ThoRie
Forum-Anfänger

Forum-Anfänger


Beiträge: 34
Anmeldedatum: 22.05.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 03.08.2019, 12:26     Titel: Code beschleuingen
  Antworten mit Zitat      
Hallo Smile

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;
  while any(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
   
  endwhile
  figure
    mesh(c);
    view([45 45]);
endfunction
 


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? :/
Private Nachricht senden Benutzer-Profile anzeigen


Jan S
Moderator

Moderator


Beiträge: 10.973
Anmeldedatum: 08.07.10
Wohnort: Heidelberg
Version: 2009a, 2016b
     Beitrag Verfasst am: 04.08.2019, 15:30     Titel: Re: Code beschleuingen
  Antworten mit Zitat      
Hallo ThoRie,

Welche Inputs verwendest du denn für a und b?
Ist c per Pre-Allocation auf die endgültige Größe allociert oder wächst es in jeder Iteration?

Gruß, Jan
Private Nachricht senden Benutzer-Profile anzeigen
 
ThoRie
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 34
Anmeldedatum: 22.05.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 04.08.2019, 17:47     Titel:
  Antworten mit Zitat      
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 :/
Private Nachricht senden Benutzer-Profile anzeigen
 
sijuherm
Forum-Anfänger

Forum-Anfänger


Beiträge: 29
Anmeldedatum: 01.08.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 08.08.2019, 10:34     Titel:
  Antworten mit 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.

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.
Private Nachricht senden Benutzer-Profile anzeigen
 
ThoRie
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 34
Anmeldedatum: 22.05.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 08.08.2019, 12:09     Titel:
  Antworten mit Zitat      
Also, ich habe jetzt erst einmal den Code folgendermaßen angepasst:

Code:
function c=sandhaufen(a,b)
  c=a+b;
  while any(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([45 45]);
  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 Smile
Private Nachricht senden Benutzer-Profile anzeigen
 
sijuherm
Forum-Anfänger

Forum-Anfänger


Beiträge: 29
Anmeldedatum: 01.08.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 08.08.2019, 13:31     Titel:
  Antworten mit Zitat      
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

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.
Private Nachricht senden Benutzer-Profile anzeigen
 
ThoRie
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 34
Anmeldedatum: 22.05.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 08.08.2019, 21:16     Titel:
  Antworten mit Zitat      
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 Smile
Private Nachricht senden Benutzer-Profile anzeigen
 
sijuherm
Forum-Anfänger

Forum-Anfänger


Beiträge: 29
Anmeldedatum: 01.08.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 09.08.2019, 08:56     Titel:
  Antworten mit Zitat      
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.
Private Nachricht senden Benutzer-Profile anzeigen
 
ThoRie
Themenstarter

Forum-Anfänger

Forum-Anfänger


Beiträge: 34
Anmeldedatum: 22.05.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.08.2019, 07:26     Titel:
  Antworten mit Zitat      
Zitat:
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.

Aber das ist, wie gesagt nur eine Vermutung.
Private Nachricht senden Benutzer-Profile anzeigen
 
sijuherm
Forum-Anfänger

Forum-Anfänger


Beiträge: 29
Anmeldedatum: 01.08.19
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 12.08.2019, 08:34     Titel:
  Antworten mit Zitat      
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
Code:
a = randi(2^14,101)
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.
Private Nachricht senden Benutzer-Profile anzeigen
 
Neues Thema eröffnen Neue Antwort erstellen



Einstellungen und Berechtigungen
Beiträge der letzten Zeit anzeigen:

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
.


goMatlab ist ein Teil des goForen-Labels
goForen.de goMATLAB.de goLaTeX.de


 Impressum  | Nutzungsbedingungen  | Datenschutz  | Werbung/Mediadaten | Studentenversion | FAQ | goMatlab RSS Button RSS


Copyright © 2007 - 2021 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
Partner: LabVIEWforum.de

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.