In einem unsortierten array min. und max. herausfinden.

[bl4ckb1rd]

Wie kann ich in einem Array, der nur aus Zahlen besteht, ganz schnell die kleinste und größte Zahl herausfinden?

Meine Lösung wäre:

Delphi-Quellcode:

min:= array[1];
max := array[1];
for i:= 2 to lenght(array) do begin
if array[i] < min then min := array[i];
if array [i] > max then max := array[i];
end;

Kann man das noch optimieren? Schneller machen?

[himitsu]

sehr viel wirst'e da wohl nimmer optimieren können.
da es ja unsortiert ist, wirst du wohl oder übel wirklich jeden Wert einzeln mit Min/Max vergleichen müssen.

ok, wenn der Wert kleiner als der kleinse Wert ist, dann kann er nicht mehr größer sein, so daß man dieses dann übergehen könnte ... macht aber auch nocht sooooo viele aus

Delphi-Quellcode:

min := array[0];
max := array[0];
for i:= 1 to high(array) do
  if array[i] < min then min := array[i]
  else if array[i] > max then max := array[i];

und wenn du nicht weißt, ob das Array nicht eventuell leer sein könnte, dann entweder vorher dieses per IF abfangen
oder alle Arrayzugriffe in die Schleife verlegen

Delphi-Quellcode:

min := MaxValue;  // z.B. MaxInt
max := MinValue;  // z.B. MinInt
for i:= 0 to high(array) do
  if array[i] < min then min := array[i]
  else if array[i] > max then max := array[i];

statt 0 (meißt beginnt ja fast alles mit 0) könnte man auch zur Sicherheit einfach Low(array) nehmen

[Satty67]

Wie messt Ihr das?

Ich hab' auch mit einem knapp 2 GByte großen dyn. Array versucht. Da kamen Ergebnisse um 500ms raus... alles was nicht "dumm" geändert wurde, zeigte bei mir Werte innerhalb der Messtoleranz. (Also nicht messbar)

[R2009]

Hi,

dafür gibts in der Unit math spezielle Funktionen.

Viele Grüsse

[himitsu]

jupp, und diese machen es genauso, sind also etwa gleich schnell.

hier gibt es einfach nicht viel zum Optimieren, da die größte Bremse (das Kopieren der Werte, in die CPU) immer erhalten bleibt.

Delphi-Quellcode:

uses Math;

procedure TForm1.Button1Click(Sender: TObject);
const MinInt = Low(Integer);
var a: Array of Integer;
  i, min, max: Integer;
  p: PInteger;
  q1, q2, f: Int64;
  s: String;
begin
  SetLength(a, $10ffffff);
  // $1ffffffc dürfte etwa das Maximum von rund 2 GB sein.
  // Hab hier das Programm allerdings nur im 2 GB-Mode laufen, weswegen 
  // ich nicht an 2 GB rankomm, da die DLLs + EXE + MemoryManager ja
  // einen Teil schon belegt haben.
  For i := 0 to High(a) do a[i] := Random(MaxInt);

  QueryPerformanceFrequency(f);
  s := '';

  QueryPerformanceCounter(q1);
  min := MinIntValue(a);
  max := MaxIntValue(a);
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 1: %f ms', [s, (q2 - q1) * 1000 / f]);

  QueryPerformanceCounter(q1);
  min := a[0];
  max := a[0];
  For i := 1 to High(a) do Begin
    If a[i] < min Then min := a[i];
    If a[i] > max Then max := a[i];
  End;
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 2: %f ms', [s, (q2 - q1) * 1000 / f]);

  QueryPerformanceCounter(q1);
  min := MaxInt;
  max := MinInt;
  For i := 0 to High(a) do
    If a[i] < min Then min := a[i]
    Else If a[i] > max Then max := a[i];
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 3: %f ms', [s, (q2 - q1) * 1000 / f]);

  QueryPerformanceCounter(q1);
  min := MaxInt;
  max := MinInt;
  P   := Pointer(a);
  For i := High(a) downto 0 do Begin
    If P^ < min Then min := P^
    Else If P^ > max Then max := P^;
    Inc(P);
  End;
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 4: %f ms', [s, (q2 - q1) * 1000 / f]);

  QueryPerformanceCounter(q1);
  min := MaxInt;
  max := MinInt;
  P   := Pointer(a);
  For i := High(a) downto 0 do Begin
    If P^ < min Then min := P^;
    Inc(P);
  End;
  P   := Pointer(a);
  For i := High(a) downto 0 do Begin
    If P^ > max Then max := P^;
    Inc(P);
  End;
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 5: %f ms', [s, (q2 - q1) * 1000 / f]);

  QueryPerformanceCounter(q1);
  min := MaxInt;
  max := MinInt;
  P   := Pointer(a);
  For i := High(a) downto 0 do Begin
    If P^ < min Then Begin
      min := P^;
      If min = MinInt Then Break;
    End;
    Inc(P);
  End;
  P   := Pointer(a);
  For i := High(a) downto 0 do Begin
    If P^ > max Then Begin
      max := P^;
      If max = MaxInt Then Break;
    End;
    Inc(P);
  End;
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 6: %f ms', [s, (q2 - q1) * 1000 / f]);

  QueryPerformanceCounter(q1);
  ASM
    PUSH EDI
    PUSH EBX

    MOV  EAX, &MinInt
    MOV  EDX, &MaxInt
    MOV  EDI, &a
    TEST EDI, EDI
    JZ   @@none
    MOV  ECX, [EDI - 4]
    @@loop:
    MOV  EBX, [EDI + ECX * 4]

    CMP  EAX, EBX
    JGE  @@greater
    MOV  EAX, EBX
    @@greater:

    CMP  EDX, EBX
    JLE  @@lower
    MOV  EDX, EBX
    @@lower:

    LOOP @@loop

    @@none:
    MOV  &min, EAX
    MOV  &max, EDX

    POP  EBX
    POP  EDI
  End;
  QueryPerformanceCounter(q2);
  If min = max Then ;
  s := Format('%s - 7: %f ms', [s, (q2 - q1) * 1000 / f]);

  ShowMessageFmt('%d : %d MB %s', [Length(a), (Length(a) * SizeOf(Integer)) shr 20, s]);
end;

Zitat von Satty67:

Wie messt Ihr das?

wie messen wir was?


PS:

Zitat von Unit Math:

Delphi-Quellcode:

function MinIntValue(const Data: array of Integer): Integer;
var
  I: Integer;
begin
  Result := Data[Low(Data)];
  for I := Low(Data) + 1 to High(Data) do
    if Result > Data[I] then
      Result := Data[I];
end;

[Satty67]

Zitat von himitsu:

wie messen wir was?

Die Unterschiede von minimal abweichender Code-Laufzeit... QueryPerformanceCounter schwankt bei mir bei gleichem Code so weit auseinander, dass ich bei minimal unterschiedlichem Code die Laufzeit nicht genau genug messen kann.

Dachte Ihr berechnet irgendwie die Laufzeit anhand des ASM Codes.

[himitsu]

das Problem ist ja, das Windows nicht nur den zu messenden Code ausführt, also zwischendurch auch mal das Programm anhält und schnell mal ein paar andere Programme bearbeitet.
außerdem funkt z.B. die Cache, und andere Hardware dazwischen und bremst etwas.

einzige Lösung:
mehrere Meßdurchgänge und den Durchschnitt berechnen.

PS: hier war's jetzt nicht nötig, daß das Füllen des arrays mit Zufallszahlen schon genug die CPU auslaßtet, aber z.B. hier hab ich am Anfang extra noch eine "sinnlose" Berechnung durchführen lassen (also 'ne "nutzlose" Schleife), da meine CPU dynamisch getaktet ist und ich sie erstmal auf Touren bringen muß, damit die nachfolgenden Berechnungen alle etwa die gleiche CPU-Geschwindigkeit bekommen.

[mr_emre_d]

Hab mal vor Ewigkeiten etwas geschrieben .. weiß nicht mehr, ob das so optimal ist, aber egal, vlt hilfts dir

Delphi-Quellcode:

type TIntArr = Array of Integer;
// --
procedure FindMinMax( const IntArr: TIntArr; var Min, Max: Integer );
asm
  // eax -> arr
  // ecx -> min -> ebx -(xchg)> ecx = length
  // edx -> max
  // edi -> vergleichs-buffer
  push edi
  xchg ebx,  ecx
  mov  ecx,  [eax-4]
  dec  ecx
  @Search:
    mov  edi,  [eax+ecx*4]
    cmp  edi,  [ebx]
    jg   @SetMin
    cmp  edi,  [edx]
    jl   @SetMax
    jmp  @Next
    @SetMin:
      mov [ebx],  edi
      jmp @Next
    @SetMax:
      mov [edx],  edi
    @Next:
      loop @Search
  pop  edi
end;

MfG