Grösster Wert in einem Array

[mirage228]

Hallo,

wir hatten heute in Informatik aufgekriegt den grössten Wert aus einem Array zu suchen.

Ich hab mir dazu was gebastelt und wollte nun wissen, ob und wie man was an dem Algo (soweit man das Algo nennen kann) verbessern könnte:

P.S.: Das Programm ist in Turbo Pascal 7!

Delphi-Quellcode:

CONST
  MAX_ARRAY_SIZE = 5;

TYPE
  TMyArray = Array[1..MAX_ARRAY_SIZE] of Real;

{ ... }

FUNCTION Max(x,y: Real): Real;
BEGIN
  IF x > y THEN Max := x ELSE Max := y;
END;

FUNCTION GetMaxArrayValue(VAR MyArray: TMyArray): Real;
VAR
  i: integer;
  lastMax: Real;
BEGIN
  lastMax := MyArray[low(MyArray)];
  FOR i := low(MyArray) TO high(MyArray)-1 DO
  BEGIN
    GetMaxArrayValue := Max(lastMax, MyArray[i+1]);
    lastMax := Max(lastMax, MyArray[i+1]);
  END;
END;

{ ... }

mfG
mirage228

[Delphianer]

Eine kleine Verbesserung:

Delphi-Quellcode:

CONST 
  MAX_ARRAY_SIZE = 5; 

TYPE 
  TMyArray = Array[1..MAX_ARRAY_SIZE] of Real; 

{ ... } 

FUNCTION Max(x,y: Real): Real; 
BEGIN 
  IF x > y THEN Max := x ELSE Max := y; 
END; 

FUNCTION GetMaxArrayValue(VAR MyArray: TMyArray): Real; 
VAR 
  i: integer; 
  lastMax: Real; 
BEGIN 
  lastMax := MyArray[low(MyArray)]; 
  FOR i := low(MyArray)+1 TO high(MyArray) DO 
  BEGIN 
    lastMax := Max(lastMax, MyArray[i]); 
  END; 
  GetMaxArrayValue := lastMax; 
END; 

{ ... }

Den Wert mußt Du nur zuletzt an die Funktion zuweisen, und es ist ein kleines bißchen schneller, wenn Du die Berechnung i+1 aus der Schleife herausnimmst. Noch schneller wirst Du, wenn Du Max nicht als Funktion schreibst:

Delphi-Quellcode:

  BEGIN 
    if lastMax > MyArray[i] then
      lastMax := MyArray[i]; 
  END;

Viele Grüße

[sakura]

Hier mein Vorschlag (ungetestet!):

Teste Deine und meine Lösung mal mit dem höchsten Wert im ersten, mittleren, bzw. letzten Element

Delphi-Quellcode:

FUNCTION GetMaxArrayValue(VAR MyArray: TMyArray): Real;
VAR
  i: integer;
  lastMax: Real;
BEGIN
  lastMax := MyArray[low(MyArray)];
  FOR i := low(MyArray)+1 TO high(MyArray) DO
    if MyArray[i] > lastMax then
      lastMax := MyArray[i];
  GetMaxArrayValue := lastMax;
END;

...:cat:...

[choose]

Wenn Du den generellen Algorithmus, also die Aufgabe, das größte Element in einer sequenziellen geordneten (ich meine nicht sortiert!) Struktur zu finden, meinst, ist die Komplexität O(n)=n. Hier kannst Du nichts verbessern.

Falls Du performateren Code beim Durchsuchen Deines Arrays mit bisher 5 Einträgen haben möchtest, gibt es ein paar Punkte, an denen Du ansetzen könntest.

1. Du überschreibst den Rückgabewert der Funktion in jeder Iteration. Weise das Zwischenergnis einfach nur lastMax zu und kopiere nach der Schliefe den Werte von lastMax nach GetMaxArrayValue.
2. Du liest das erste Element doppelt aus und vergleichst es mit sich selbst
3. Die Funktionsaufrufe von max sind "teuer", obwohl sie sehr zur guten Struktur beitragen. Wenn es wirklich wichtig ist, mache nur einen Vergleich und überschreibe das bisherige Maximum nur, wenn er positiv ausfällt.
4. Lass Dein Array nicht mit einem Index ungleich null beginnen.

Ich habe die Punkte nach Relevanz hinsichtlich Performancesteigerung sortiert.

EDIT: Hi Sakura, das ist ja fast genau das Code-Beispiel dazu!

[mirage228]

Hallo,

vielen Dank für eure Vorschläge, sie funktionieren einwandfrei.

mfG
mirage228