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;

[SirThornberry]

so was hier würde ich übrigens als Schiedsrichter nicht durchgehen lassen:

Delphi-Quellcode:

Prim[1] := 2; 
Prim[2] := 3; 
Prim[3] := 5; 
anz_Prim := 3;

Denn sonst kommt der nächste und knotet gleich alle Primzahlen fest ins Programm. Entweder wird alles ermittelt oder alles fest rein geknotet. Oder warum hast du nur die ersten 3 Primzahlen fest rein geknotet und nicht die ersten 4?

@uwe:
folgendes sollte noch schneller sein:

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 
  for I := 2 to anz_Prim do begin        // gerade Zahlen hatten wir ausgeschlossen, daher ab 2 
    test := Prim[I]; 
    if test > maxTest then Break; 
    if not Boolean(D mod test) then
      Break; 
  end;
  if (i < anz_Prim) then
    Continue; 
  Inc(anz_Prim); 
  Prim[anz_Prim] := D; 
end;

[Blup]

Nach dem Schleifendurchlauf ist i undefiniert, insbesondere da der Compiler For-Schleifen optimiert (z.B. abwärts zählen bis 0).

Im Prinzip hab ich nichts neues hinzuzufügen, aber da ich mir schon die Mühe gemacht hab:

Delphi-Quellcode:

For D := Prim[anz_Prim] + 1 To max_Prim do 
begin 
  if Odd(D) then
  begin
    Pmax := Trunc(Sqrt(D));

    flg_Prim := True;
    for I := 1 to anz_Prim do
    begin
      P := Prim[I];
      flg_Prim := ((D mod P) <> 0);
      if not flg_Prim then
        Break;
      if P >= PMax then
        Break;
    end;
      

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

[sirius]

Zitat:

Zitat von Thornberry

// gerade Zahlen hatten wir ausgeschlossen, daher ab 2

Dann doch ab 3 :gruebel:

Zitat:

Delphi-Quellcode:

if not Boolean(D mod test)

Wenn dann schon "LongBool(D mod test)", ansonsten testest du ja nur das letzte Byte.

[SirThornberry]

Auf was für einem Rechner läuft eigentlich der finale Testlauf? Wenn es einer mit mehreren Kernen ist kann man einiges an Zeit raus holen wenn man mit mehreren Threads arbeitet.

[sirius]

Ein riesen ZEitsprung entsteht, wenn man die Division mit einer Schleifenvariable, anstatt mit dem Inhalt einer lokalen Variable (=bisherige Primzahlen) macht.
Mit der verbesserten Variante von Sir komme ich unter 2 Sekunden.

[R2009]

Hallo Blup,

ich hab deinen Code reinkopiert.
Ergebnis:
Bei Delphi ist der Zeitaufwand für 1000000 nicht mehr messbar, bei VB nach wie vor 22 Sekunden.
Ich hab natürlich jetzt die Lacher auf meiner Seite.
Natürlich hab ich mich geweigert den Code rauszurücken, du hast ja doch schon gewaltig am Algorithmus gedreht.
Aber Hauptsache ich hab die VB Jünger hier im Hause etwas geärgert. Ein Freund von mir wird das Ganze
genauso in VB realisieren, dann sehen wir weiter.
Die Wette hab ich damit noch nicht gewonnen aber du hast (ihr habt) mir sehr geholfen.

Vielen herzlichen dank für eure Mühe!
Grüsse
rainer

[MaBuSE]

[edit]
Mist, hätte doch noch mal vor dem posten refresh drücken sollen,
hab das neben der Arbeit gecoded. Deswegen hat etwas gedauert ;-)
Uwe hat ja schon "meine" Lösung geposted.
[/edit]

Zitat:

Zitat von R2009

Am Algorithmus kann ich nur bedingt etwas ändern.

Die meiste Zeit geht durch unnötige Berechnungen drauf.
Da z.B. 2*3 = 3*2 ist, musst Du nur bis zur abgerundeten Wurzel prüfen.

Delphi-Quellcode:

...
{$A8,B-,C-,D-,E-,F-,G+,H-,I-,J-,K-,L-,M-,N+,O+,P-,Q-,R-,S-,T-,U-,V-,W-,X-,Y-,Z1}
procedure TForm1.Button1Click(Sender: TObject);
const
  max_prim = 1000000;
var
  prim: array of cardinal;
  anz_prim: cardinal;
  d, i, w: cardinal;
  Anfg_Zeit: TDateTime;
begin
  // Arraygröße
  setlength(prim,80000); // reicht bei bis zu 1000000

  // Zeitmessung
  Anfg_Zeit := Now;

  // Berechnung
  Prim[1] := 2;
  Prim[2] := 3;
  Prim[3] := 5;
  anz_Prim := 3;
  d := 7;
  repeat
    w := Trunc(Sqrt(D)); // nur bis zur Wurzel testen, da sonst doppelt getestet wird. 2*3 = 3*2
    i := 2; // div 2 ist unnötig, da inc(d,2)
    while (D mod Prim[I] > 0) and  (Prim[i] < w) and (i < anz_Prim) do inc(i);

    If D mod Prim[I] > 0 then
    begin
      inc(anz_Prim);
      Prim[anz_Prim] := D;
    end;

    inc(D,2);
  until (D >= max_Prim);

  // Zeitmessung
  Caption := TimeToStr(now - anfg_zeit);

  // Ausgabe
  lst_ausgabe.Items.BeginUpdate;
  for i := 1 to anz_prim do
  begin
    lst_Ausgabe.Items.Add(IntToStr(Prim[i]) + ' ist eine Primzahl!');
  end;
  lst_ausgabe.Items.EndUpdate;

  // Zeitmessung
  Caption := TimeToStr(now - anfg_zeit);
end;
...

[R2009]

Hihi,

hab gewonnen. Kollege hat mit VB das Ganze nachgeproggt.
Ich bin bei 10 000 000 bei 2 Sekunden er bei ca 4 (bisschen drüber)
Ein Dutzend Leute haben überprüft, dass das auch ja das Gleiche ist.

Was micht etwas wundert ist dass VB so schnell ist. Bisher (zumindest die Versionen die ich kenne)
war da (zur Laufzeit) immer ein Interpreter beteiligt.
Erzeugt das Teil jetzt wirklich Maschinencode?

Grüsse
Rainer

[uoeb7gp]

Hi, also wenns soschnell wie möglich gehen soll, sieh dier mal die hochoptimierten Fastcode routienen an.

Dann bist je nach Prozessor im msec Bereich!

lg.

[rwachtel]

Zitat:

Zitat von R2009

[...] Was micht etwas wundert ist dass VB so schnell ist. Bisher (zumindest die Versionen die ich kenne)
war da (zur Laufzeit) immer ein Interpreter beteiligt. [...]

...das ist schon ein paar Jährchen her...

Reden wir denn jetzt eigentlich von VB oder von VB.NET?

[Wolfgang Mix]

Habe gerade 'mal UBasic (32bit) unter DOS aus den 80ern ausgegraben.
Das zerlegt 111111111111111111 in Primfaktoren im Millisekundenbereich
inklusive Bildschirmausgabe. Viel großere Zahlen sind natürlich auch
kein Problem.

Zitat:

UBASIC is a freeware BASIC interpreter written by Yuji Kida at Rikkyo University in Japan, specialized on mathematical computing.

Wen es interessiert, findet hier nen Downlink.

Gruß

Wolfgang