WICHTIG: Der Betrieb von goMatlab.de wird privat finanziert fortgesetzt. - Mehr Infos...

Mein MATLAB Forum - goMatlab.de

Mein MATLAB Forum

  
Gast > Registrieren       Autologin?   

Partner:




Forum
      Option
[Erweitert]
  • Diese Seite per Mail weiterempfehlen
     


Gehe zu:  
Neues Thema eröffnen Neue Antwort erstellen

Sieb des Eratosthenes-wie weiter optimieren?
 

Moondryl
Forum-Newbie

Forum-Newbie

Beiträge: 9
Anmeldedatum: 29.10.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 11.11.2009, 20:50     Titel: Sieb des Eratosthenes-wie weiter optimieren?
  Antworten mit Zitat      
Hi,
habe mal das Sieb des Eratosthenes versucht zu programmieren und wollte jetzt mal fragen, wie ich es weiter optimieren könnte?

Code:

function [ primzahlvektor ] = prim( N )

x = 1:N;                            

for i =2:fix(sqrt(N))                        
    for k = (i*i):N
        if (x(k) ~= 0)            
            if (mod(x(k),i) == 0)  
                x(k) = 0;        
            end
        end
    end
end

primzahlvektor = x(x(1:length(x))~=0);
 


schön wäre es ja, wenn man die for-schleifen verschwinden lassen könnte.
wo ich mich aber besonders ärgere ist, dass wenn man in der ersten schleife nur die ungeraden zahlen durchlaufen würde (also in 2er-schritten) man doch ziemlich viel rechenzeit eingespart werden könnte.

freue mich schon auf eure ideen Smile

grüße
Private Nachricht senden Benutzer-Profile anzeigen


Andreas Goser
Forum-Meister

Forum-Meister

Beiträge: 3.654
Anmeldedatum: 04.12.08
Wohnort: Ismaning
Version: 1.0
     Beitrag Verfasst am: 12.11.2009, 11:44     Titel:
  Antworten mit Zitat      
Code:

n=10000; tic, prim(n); toc, tic, primes(n); toc
Elapsed time is 0.022154 seconds.
Elapsed time is 0.000201 seconds.
 


Die MATLAB Implementation für Primzahlen ist in der Tat einiges schneller. Einhach
Code:
Code:

eingeben um zu sehen wie es funktioniert.

Andreas
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
Moondryl
Themenstarter

 Forum-Newbie

Forum-Newbie

Beiträge: 9
Anmeldedatum: 29.10.09
Wohnort: ---
Version: ---
     Beitrag Verfasst am: 14.11.2009, 19:40     Titel:
  Antworten mit Zitat      
Hi, tut mir leid, dass ich erst so spät wieder schreibe; war etwas stressig an der uni.
hatte aber mittlerweile den code auch noch verbessert Smile
und siehe da, er ist schneller als matlabs primes Smile

Code:

x = 1:N;
                         
x(1) = 0;

for i = 2:fix(sqrt(N))    
    if (x(i) ~= 0)
        NotAPrime = x(i) * 2;
        while NotAPrime <= N
           x(NotAPrime) = 0;
           NotAPrime = NotAPrime + i;            
        end      
    end
end

primzahlvektor = x(x(1:length(x))~=0);
                 
end
 


Ergebnis:

Code:

n=10000; tic, prim(n); toc, tic, primes(n); toc
Elapsed time is 0.005276 seconds.
Elapsed time is 0.030115 seconds.
 


Grüße
Moondryl Smile

Edit: schade war wohl nur glück; wenn ich es jetzt öfters durchlaufen lassen, ist primes immer schneller.
aber immerhin noch näher rangekommen Smile
Private Nachricht senden Benutzer-Profile anzeigen
 
Andreas Goser
Forum-Meister

Forum-Meister

Beiträge: 3.654
Anmeldedatum: 04.12.08
Wohnort: Ismaning
Version: 1.0
     Beitrag Verfasst am: 16.11.2009, 18:40     Titel:
  Antworten mit Zitat      
Das liegt daran, dass MATLAB Code auch cachtund daher mehrfach hintereinander ausgeführter Code ab dem 2. Mal schneller ist.

Eine vernünftige Bewertung von Codeperformance gelingt übrigens erst mit höheren n.

Wo bei es auch Fälle gibt wo MathWorks Code langsamer ist als der von Kunden. In den Fällen ist es meistens so, dass der Kundencode Spezialfälle schneller löst.

Andreas
Private Nachricht senden Benutzer-Profile anzeigen E-Mail senden
 
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
.





 Impressum  | Nutzungsbedingungen  | Datenschutz | FAQ | goMatlab RSS Button RSS

Hosted by:


Copyright © 2007 - 2025 goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks

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.