Optimierung eines Stück Codes für eine Wette!

[R2009]

Hi DP'ler,
ich habe mich dazu verleiten lassen zu behaupten, dass ich dieses Programmstück mindestens doppelt so schnell bekomme wie
ein vergleichbares Stück Code in VB.
Seht ihr noch Optimierungsmöglichkeiten?
Das Ganze ist recht primitiv und berechnet Primzahlen. Die Vorgehensweise ist vorgegeben. Am Algorithmus kann ich nur bedingt etwas ändern.
Das ganze Programm hängt an. Für 1000000 benötigt VB 22 Sekunden und das Teil hier 19.

Delphi-Quellcode:

procedure Tfrm_Hauptform.btn_RechneClick(Sender: TObject);

{ ################################################################################################################################## }

var
D               : cardinal;
flg_NoPrim      : Boolean;

Anfg_Zeit       : TDateTime;
Ende_Zeit       : TDateTime;
Diff_Zeit       : TDateTime;

I               : cardinal;
r               : cardinal;
{ ################################################################################################################################## }

begin

max_Prim := StrToInt(txt_MaxZahl.Text);
setlength(prim,1000000);
Prim[1] := 2;
Prim[2] := 3;
Prim[3] := 5;
anz_Prim := 3;

lst_Ausgabe.Clear;
lst_Ausgabe.Items.Add('Suche Primzahlen ..');
lst_Ausgabe.Items.Add('Start:     ' + DateTimeToStr(Now));
lst_Ausgabe.Refresh;

Anfg_Zeit := Now;

For D := 6 To max_Prim do
  begin

    flg_NoPrim := FALSE;
    I := 1;

    repeat
      begin
        r:=D mod Prim[I];
        If r = 0 Then flg_NoPrim := TRUE;
        inc(i);
      end;
    until (flg_NoPrim OR (I = anz_Prim));

    If   flg_NoPrim=false then
         begin
           anz_Prim       := anz_Prim + 1;
           Prim[anz_Prim] := D;
         {lst_Ausgabe.Items.Add(IntToStr(D) + ' ist eine Primzahl!'); }
         end;
end;

Grüsse
Rainer

[SirThornberry]

Ich sag mal so - diese Wette wirst du verlieren. Wenn man den VB-Code ebenfalls schon im Quelltext optimiert wird der Delphicode niemals doppelt so schnell sein.

[IIIMADDINIII]

hast du es schonmal in ein thread mit der hösten priorität(timecritical) ausprobiert?

[sx2008]

Delphi-Quellcode:

For D := 6 To max_Prim do

Nur ungerade Zahlen können Primzahlen sein.
Wenn du die Schleife so änderst, dass nur ungerade Zahlen getestet werden, spart das Zeit.

[SirThornberry]

aber wäre vb auch langsamer wenn der dazugehörige vb code ebenfalls nur die ungeraden zahlen testet und der Thread mit höherer Priorität läuft?!
Das füllen der Listbox könnte man durch Verwendung von BeginUpdate und EndUpdate beschleunigen (sofern eine Liveausgabe nicht benötigt wird)

[nahpets]

Hallo,

soviel schneller nicht mit meinen Änderungen, aber eventuell 1 oder 2 Millisekunden? ;-)

Delphi-Quellcode:

procedure Tfrm_Hauptform.btn_RechneClick(Sender: TObject);

{ ################################################################################################################################## }

var
D               : cardinal;
flg_NoPrim      : Boolean;

Anfg_Zeit       : TDateTime;
Ende_Zeit       : TDateTime;
Diff_Zeit       : TDateTime;

I               : cardinal;
r               : cardinal;
{ ################################################################################################################################## }

begin

max_Prim := StrToInt(txt_MaxZahl.Text);
setlength(prim,1000000);
Prim[1] := 2;
Prim[2] := 3;
Prim[3] := 5;
anz_Prim := 3;

lst_Ausgabe.Clear;
lst_Ausgabe.Items.Add('Suche Primzahlen ..');
lst_Ausgabe.Items.Add('Start:     ' + DateTimeToStr(Now));
lst_Ausgabe.Refresh;

Anfg_Zeit := Now;

// For D := 6 To max_Prim do
  d := 6;
  Repeat
    begin

    // flg_NoPrim := FALSE; // <- ist diese Zuweisung erforderlich,
                            //    wird doch im Repeat Until überschrieben.
    I := 1;

    repeat
      // begin
        // r := D mod Prim[I];
        // If r = 0 Then flg_NoPrim := TRUE;
        // flg_NoPrim := r = 0;
        flg_NoPrim = D mod Prim[I];
        inc(i);
      // end;
    until (flg_NoPrim OR (I = anz_Prim));

    // If   flg_NoPrim=false then
    // If Not flg_NoPrim then
    case flg_NoPrim of
      false : begin
                // wo ist denn anz_Prim definiert?
                // anz_Prim       := anz_Prim + 1;
                Inc(anz_Prim);
                Prim[anz_Prim] := D;
                {lst_Ausgabe.Items.Add(IntToStr(D) + ' ist eine Primzahl!'); }
              end;
    end;
    Inc(d,2);
  Until d >= max_Prim;
end;

Achso, nur hingedaddelt, nicht getestet.

[Bernhard Geyer]

VB oder VB.NET?

Mit VB.NET wird es schwierig. Bei gleichen Code eigentlich unmöglich doppelt so schnell zu werden. Auch du verwendest hochoptimierten Assemblercode in der Routine.

[SirThornberry]

ich könnte mir vorstellen das dieser Abschnitt

Delphi-Quellcode:

repeat 
  flg_NoPrim = D mod Prim[I]; 
  inc(i); 
until (flg_NoPrim OR (I = anz_Prim));

schneller wäre wenn man nicht bei jedem Schleifendurchlauf flg_noPrim prüft.

Aber auch das hat nichts mit Delphi vs VB zu tun. Denn wenn du den Quelltext fertig hast und dieser so nach VB übernommen wird ist dieser auch dort schneller.

[Corpsman]

Also wenn du nichts am Algorithmus machen kannst ist das natürlich blöd.

Im Prinzip berechnest du ja alle Primzahlen unter 1000000 und zählst diese.

Ich hab mal nen alten Algo von meinen Project Euler Aufgaben rausgekramt, und den das Berechnen lassen. Der lag unter 1 sec. hat also immer 00:00:00 ausgegeben.

Wenn du allerdings wirklich den vorgegebenen Code nehmen musst, dann siehts schlecht aus für dich. Wirklich Zeit sparen kannst du nur wenn du schneller = anders auf dein Ziel kommst, und das wäre ja wieder eine Algorithmische Änderung.

[Uwe Raabe]

Wenn du am Algorithmus nichts ändern darfst, wird es schwierig werden...

Aber trotzdem hier der Code mit ein paar Boostern:

Delphi-Quellcode:

For D := 7 To max_Prim do begin          // 6 ist keine Primzahl, daher ab 7  
  if not Odd(D) then Continue;           // schließe alle geraden Zahlen aus
  maxTest := Trunc(Sqrt(D));             // prüfe nur bis max. Quadratwurzel des Kandidaten
  flg_NoPrim := false;
  for I := 2 to anz_Prim do begin        // gerade Zahlen hatten wir ausgeschlossen, daher ab 2
    test := Prim[I];
    if test > maxTest then Break;
    flg_NoPrim := ((D mod test) = 0);
    if flg_NoPrim then Break;
  end;
  if flg_NoPrim then Continue;
  Inc(anz_Prim);
  Prim[anz_Prim] := D;
end;