Gibt es ein Schnelleres verfahren als Min?

[Hallo_Thomas]

Ich hab ein Programm in der so eine Zeile 1000 mal durchlaufen wird, da ich immer nur das Minimum brauche. Gibt es ein Verfahren welches für Variablen schneller ist als dieses?

Delphi-Quellcode:

Counter[145]:= Min(Counter[48],Min(Counter[50],Counter[52]));

edit:Weis jemand wieviel Ms dieser Durchlauf benötigt?

[simonko]

was machst du denn genau?

[leddl]

Denk mal genau nach. Was wird min denn machen? Wahrscheinlich vergleicht das die beiden Werte und gibt den kleineren zurück. Wie willst du das noch beschleunigen? Du brauchst eben für n zu vergleichende Werte genau n-1 Vergleiche.

[Pr0g]

Du scheinst ja mit Arrays zu arbeiten, dann könnte die Funktion MinIntValue() was für dich sein. Die gibt den kleinsten Wert aus einem Array of Integer zurück. Obs schneller ist weiß ich aber nicht.

MfG Pr0g

[Robert_G]

Zitat:

Zitat von leddl

Denk mal genau nach. Was wird min denn machen? Wahrscheinlich vergleicht das die beiden Werte und gibt den kleineren zurück. Wie willst du das noch beschleunigen?

es macht nix weiter als:

Delphi-Quellcode:

if left < right then
  result := left
else
  result := right;

Du könntest es inline schreiben um die Sprünge loszuwerden, sonst sehe ich da nicht viele einfache Möglichkeiten für Optimierungen.
Vielleicht ist es möglich dein Programm anders zu strukturieren wodurch so viele Vergleich unnötig werden könnten.
Das weißt aber du selbst am besten, schließlich wissen wir nicht wie dein Programm aussieht, noch was es erreichen soll... ;)

[leddl]

Zitat:

Zitat von Robert_G

es macht nix weiter als:

Delphi-Quellcode:

if left < right then
  result := left
else
  result := right;

Na ich bin doch mal davon ausgegangen, daß er sich das denken kann. ;)

Zitat:

Zitat von Robert_G

Das weißt aber du selbst am besten, schließlich wissen wir nicht wie dein Programm aussieht, noch was es erreichen soll... ;)

Doch, er hat den betreffenden Quellcode in nem anderen Thread bereits gepostet. ;)

//Edit: Tags richtig gesetzt :mrgreen:

[Hallo_Thomas]

Delphi-Quellcode:

procedure TForm1.AddMyItem(const AItem: String; const AColor: TColor); 
var 
  x,y,i           : Integer; 
  Counter            : array[0..200] of Integer; 
begin 
  DoubleBuffered := True; 
  Anzeige.Items.InsertObject(0, AItem, Pointer(AColor)); 
for i := 0 to 200 do 
  for y := 0 to 144 do 
  begin 
    Counter[i] := 0; 
    Feld[i] := 0; 
  end; 
  // Hier beginnen die Berechnungen 
  for x := meineListe.count - 1 downto 0 do 
  for y := 0 to 144 do  // Mit jedem SetOfByte vergleichen 
  begin 
    if (StrToInt(meineListe.Strings[x]) in werte[y]) then 
    begin 
        Counter[y] := 0 
    end 
    else 
    begin 
      Inc(Counter[y]); 
    end; 
  end; 
  ////////Hier beginnt Sortierverfahren 
  begin 
      Counter[145]:= Min(Counter[48],Min(Counter[50],Counter[52])); 
  end;///.... Berechnungen gehen hier Weiter.....

[Hallo_Thomas]

Weis jemand wie schnell dieser Befehl ganz oben dauert in Ms?



Mein Hauptproblem liegt darin, dass ich dieses Procedur für Tchart brauche, da sollen dann wür jeden Counter(es kommen einige dazu)dieser Quellcode durchlaufen, und zwar dann pro Item 1 .mal. Er sollte schon mind. im 5.Stelligen bereich arbeiten.

[leddl]

Zitat:

Zitat von Hallo_Thomas

Weis jemand wie schnell dieser Befehl ganz oben dauert in Ms?

Das hängt vom PC ab (wobei bei dem bißchen eigentlich keine großen Unterschiede rauskommen sollten). Aber was hindert dich daran, es selbst auszuprobieren? :gruebel:

[Sharky]

Hai "Hallo_Thomas",

unabhängig von deiner Frage:

Delphi-Quellcode:

  
...
for x := meineListe.count - 1 downto 0 do 
  for y := 0 to 144 do  // Mit jedem SetOfByte vergleichen 
  begin 
    if (StrToInt(meineListe.Strings[x]) in werte[y]) then 
    begin 
...

Du wandelst hier bei für jeden X-Durchlauf 144 mal meineListe.Strings[x] in einen Integer um. Arbeite doch lieber mit einer Hilfsvariablen und mache die Umwandlung nur einmal.

[Hallo_Thomas]

@Leddl

Nach meiner Theorie müsste man es vielleicht mit Quicksort schneller gehen, aber meinen Wissen was so was angeht ist noch sehr gering! Ich habe da zwar schon Sdie Sortiertverfahren endecht, aber diese Sortierten immer nur ganze Arrays. Und ich benötige ja nur den kleinsten Wert aus 3 Variablen.

[Khabarakh]

In MinIntValue wird jedes Arrayelement einmal mit Result verglichen. Wie soll das denn (abgesehen von Assembler-Verbesserungen o.Ä.) schneller gehen?

[Hallo_Thomas]

@Khabarakh. Vieleicht hab ich mich verlesen, hab jetzt leider das eine Büchlein schon zurück zur Bibo geschafft!
Ich Dem was ich jetzt da hab, hab ich nichts gefunbden!

@ Sharky


wie meinst Du das mit der Hilfsvariablen?

[r2c2]

Zitat:

Zitat von Hallo_Thomas

@Leddl

Nach meiner Theorie müsste man es vielleicht mit Quicksort schneller gehen, aber meinen Wissen was so was angeht ist noch sehr gering! Ich habe da zwar schon Sdie Sortiertverfahren endecht, aber diese Sortierten immer nur ganze Arrays. Und ich benötige ja nur den kleinsten Wert aus 3 Variablen.

Jein. Zum sortieren vieler Werte ist QuickSort schneller. Ja. Aber bei 3(in Worten: DREI)? :gruebel: Nee. Qucksort hat ne "Geschwindigkeit" von O(n ld n), wenn ich mich nicht irre. Dein Sortieralgorithmis(Min-Sort(ja so heißt das)) hat eine von O(n²). Nur bei derart neidrigen ns, hällt sich der Unterschied in Grenzen. Der Aufwand, der bei einen komplizierteren Sortierverfahren(z.B. Quicksort) betrieben würde, macht das ganze höchstens langsamer.

Optimiere deinen Alg lieber auf andere Weise(Sharky hat dazu ja schon was gepostet).

mfg

Christian

[r2c2]

Zitat:

Zitat von Hallo_Thomas

@ Sharky
wie meinst Du das mit der Hilfsvariablen?

Ich heiß zwar nicht Sharky, kanns dir aber trotzdem erklären:

Delphi-Quellcode:

for i:=0 to 999 do
begin
  DoSomething(StrToInt(x));
end;

besser:

Delphi-Quellcode:

y :=StrToInt(x); // y is die Hilfsvariable
for i:=0 to 999 do
begin
  DoSomething(y);
end;

So sparst du dir 1000 aufrufe von StrToInt und diese Funktion is nicht ohne!

mfg

Christian

[Khabarakh]

@Hallo_Thomas: Angenommen, der Inhalt des Arrays ist vor der Minimum-Bestimmung jedes Mal unsortiert.
MinArrayValue vergleicht nun jedes Element genau einmal. Wie soll es denn einen schnelleren Algorithmus geben, wenn er ja wohl jedes Element mindestens einmal vergleichen muss?

[Hallo_Thomas]

@Khabarakh
Ganz so wissend bin ich hier auch nicht, aber deswegen poste ich ja!



ahha, Ich schaus mir glei mal an!Danke!

[r2c2]

MinArrayValue ist auch deshalb besser, weil ein Funktionsaufruf gespart wird. Statt Min 2x aufzurufen verwendet MinArrayValue (hoffentlich) eine Iterative Methode(ansonsten is MinArrayValue IMHO schlecht programmiert).

mfg

Christian

[Khabarakh]

Das sollte sich aber per inline; aber wieder relativieren, oder?

[SirThornberry]

@Khabarakh: Gibts inline schon bei Versionen kleiner Delphi 2005? (also jetzt mal abgesehen von asm)? Wenn ja - wie nutzt man das? Wenn Nein - dann hat sich die Frage erübrigt weil ich dann weiß das ich nicht zu dumm war es zu verwenden...

[Hallo_Thomas]

Wie wird für MinArrayValue der Befehl richtig geschrieben?

Delphi-Quellcode:

Counter[145]:= MinArrayValue(Counter[48],(Counter[50],Counter[52]);

Fehlermeldung, undefinierter bezeichner 'MinArrayValue'

[Khabarakh]

Delphi-Quellcode:

Counter[145] := MinIntValue([Counter[48], Counter[50], Counter[52]]);

@SirThornberry: Stimmt, daran hatte ich gar nicht gedacht. Aber bei so wenig Code kann man die Funktion ja auch selbst "inlinen" .

[r2c2]

Zitat:

Zitat von Khabarakh

Das sollte sich aber per inline; aber wieder relativieren, oder?

Inline?
a) dachte ich das gibts erst ab D2005 und
b) glaube ich nicht, dass Borland Min inline deklariert hat, oder hab ich inline falsch verstanden und man kann das direkt mit dem Funktionsaufruf verbinden? :gruebel: Eigentlich unlogisch!
Man könnte sich auch selbst ne Min funktion schreiben, dann kan man die aber auch 1. direkt in den Code einbauen und 2. die iterative Methode verwenden(also möglichtst Rekusion vermeiden, wenns um Gerschwindigkeit geht).

mfg

Christian

[Khabarakh]

Zu a): Siehe oben
Zu b): Das Thema heißt ja "Gibt es ein Schnelleres verfahren als Min?", also sollten neue Funktionen nicht verboten sein :wink: . Die Möglichkeit zum "Per-Hand-Inline" habe ich auch schon genannt, ich denke auch, dass zwischen iterativer und rekursiver Methode fast kein Unterschied bestehen wird (der Compiler wird vielleicht eine Variable mehr benutzen).

[Nicolai1234]

Hallo,
ich habe gerade mal (spaßeshalber) einen Test gemacht, von dem ich mir nicht viel erhoffte... Aber jetzt bin ich doch sehr überrascht:

Delphi-Quellcode:

//i1, i2, e1, e2 sind Integer
//Version 1
if i1-i2 < 0 then e1 := i1 else e1 := i2;

//Version 2
e2 := min(i1,i2);

Ich habe die beiden Möglichkeiten jeweils eine Milliarde mal durchlaufen lassen und Version 1 war doppelt so schnell :!:
(Compileroptimierung in der Schleife sind ausgeschlossen!)

Mit 3 Variablen müsste man eben beides doppelt durchlaufen lassen, was den Zeitunterschied nochmals vedoppeln würde...

Woran kann das liegen? Das hieße ja, dass Min extrem langsam ist...

[Pr0g]

Kannst auch direkt den Code aus Min() nehmen

Delphi-Quellcode:

if i1 < i2 then e1 := i1 else e1 := i2;

Ist genauso schnell, wie deiner, obwohl Min() selber ja nichts anderes macht

Delphi-Quellcode:

function Min(const A, B: Integer): Integer;
begin
  if A < B then
    Result := A
  else
    Result := B;
end;

:gruebel:

[dizzy]

Alleine der Call dürfte hier durchaus mit 50% Geschwindigkeit zu Buche schlagen, da 2 Parameter gepushed/gemoved werden müssen, und der Call selbst. Viel mehr dürfte der asm-Code der eigentlichen Funktion auch nicht sein, so dass der Call sich anteilig sehr deutlich bemerkbar machen dürfte.
Inline ist schon das richtige Stichwort. Nur gibt es Inlining tatsächlich erst für Delphi .NET, weshalb man von Hand "inlinen" muss, d.h. einfach nicht die Funktion aufrufen, sondern ihren Quelltext dahin kopieren wo sonst der Call stünde (und Variablennamen anpassen ;)).

[Khabarakh]

Jetzt natürlich noch der Vergleichstest mit inline :wink: :

Delphi-Quellcode:

function Min(const A, B: Integer): Integer; inline;
begin
  if A < B then
    Result := A
  else
    Result := B;
end;

procedure TForm1.FormCreate(Sender: TObject);
var
  Start, Stop, i, a, b, Outcome: Integer;
begin
  Start := GetTickCount;
  for i := 0 to 1000000000 do
  begin
    a := Random(245);
    b := Random(245);
    Outcome := Min(a, b);
  end;
  Stop := GetTickCount;
  ShowMessage(Format('Min inline: %f s',[(Stop - Start) / 1000]));
  Start := GetTickCount;
  for i := 0 to 1000000000 do
  begin
    a := Random(245);
    b := Random(245);
    if a < b then
      Outcome := a
    else
      Outcome := b;
  end;
  Stop := GetTickCount;
  ShowMessage(Format('Selfmade: %f s',[(Stop - Start) / 1000]));
end;

Zitat:

---------------------------
Project1
---------------------------
Min inline: 48,77 s
---------------------------
OK
---------------------------

Zitat:

---------------------------
Project1
---------------------------
Selfmade: 51,84 s
---------------------------
OK
---------------------------

Das hat mich jetzt doch etwas überrascht :stupid: .
Obwohl die Testzeiten ziemlich unterschiedlich ausfielen (Inline: 38 - 50 s), war die Inline Methode doch immer 3 - 7 Sekunden schneller.

[r2c2]

Ich würde so n Test nicht in FormCreate reinschreiben, nimm lieber n Button. Da beim Programmstart die CPU noch am Arbeiten sein kann, könnte das zu Messfehlern führen. Beeser in ButtonClick schreiben.

mfg

Christian

[r2c2]

Zitat:

Zitat von Khabarakh

Das hat mich jetzt doch etwas überrascht :stupid: .
Obwohl die Testzeiten ziemlich unterschiedlich ausfielen (Inline: 38 - 50 s), war die Inline Methode doch immer 3 - 7 Sekunden schneller.

Jetzt fragt sich nur, warum? :gruebel: Was kann den Delphi da noch optimieren?

mfg

Christian