AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Sprachen und Entwicklungsumgebungen Sonstige Fragen zu Delphi Delphi In einem unsortierten array min. und max. herausfinden.

In einem unsortierten array min. und max. herausfinden.

Ein Thema von bl4ckb1rd · begonnen am 16. Mai 2009 · letzter Beitrag vom 16. Mai 2009
Antwort Antwort
bl4ckb1rd

Registriert seit: 3. Okt 2008
53 Beiträge
 
#1

In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 15:14
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?
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.116 Beiträge
 
Delphi 12 Athens
 
#2

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 15:25
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
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PoSex im Delphi viel seltener praktiziert.
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#3

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 16:05
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)
  Mit Zitat antworten Zitat
R2009

Registriert seit: 9. Mär 2009
Ort: Heidelberg
440 Beiträge
 
Delphi 2007 Professional
 
#4

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 16:52
Hi,

dafür gibts in der Unit math spezielle Funktionen.

Viele Grüsse
Rainer Unger
Mein Profil:
Studium Allgemeine Elektrotechnik TH Darmstadt
Entwicklung von Tools für die Rundsteuer und Zählertechnik.
uP's Atmel Prozessoren (ATmega16,32,88...) in C und Assembler.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.116 Beiträge
 
Delphi 12 Athens
 
#5

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 17:04
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;
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PoSex im Delphi viel seltener praktiziert.
  Mit Zitat antworten Zitat
Satty67

Registriert seit: 24. Feb 2007
Ort: Baden
1.566 Beiträge
 
Delphi 2007 Professional
 
#6

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 18:21
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.
  Mit Zitat antworten Zitat
Benutzerbild von himitsu
himitsu

Registriert seit: 11. Okt 2003
Ort: Elbflorenz
44.116 Beiträge
 
Delphi 12 Athens
 
#7

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 18:58
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.
Neuste Erkenntnis:
Seit Pos einen dritten Parameter hat,
wird PoSex im Delphi viel seltener praktiziert.
  Mit Zitat antworten Zitat
mr_emre_d
(Gast)

n/a Beiträge
 
#8

Re: In einem unsortierten array min. und max. herausfinden.

  Alt 16. Mai 2009, 19:18
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
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 05:58 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz