Mehrere Variablen vergleichen

[Wolfgang Mix]

Wobei mir himitsus Lösung besser gefällt, weil sie
plattformunabhängig ist, aber das ist wohl Geschmacksache.

[daywalker9]

Zitat:

Zitat von mkinzler

Lieber eine Liste mit Integern oder Extendedwerten

Ist wie ich finde - auch einfacher zu verstehen. Auch für die Delphi - Anfänger

[himitsu]

Zitat:

Zitat von Wolfgang Mix

Wobei mir himitsus Lösung besser gefällt, weil sie
plattformunabhängig ist, aber das ist wohl Geschmacksache.

Nja, 'ne platformunabhängigkeit seh ich so oder so eh nicht.

PS: noch eine weitere Variable erzeugt gleich nochmal 1,5 weitere solcher Vergleichszeilen.

Wärend die Schleifen gleichlang bleiben.
Außerdem kann man sich bei den vielen Vergleichen schonmal verschreiben.
(nicht jeder läßt sich derartige Codes automatisch generieren :angel2: )

Delphi-Quellcode:

for i := 0 to High(arr) - 1 do
  for j := i + 1 to High(arr) do
    if arr[i] = arr[j] then
      >>doppelt<<

Delphi-Quellcode:

doppelt := False;
for i := 0 to High(arr) - 1 do
  for j := i + 1 to High(arr) do
    if arr[i] = arr[j] then begin
      doppelt := True;
      Break;
    end;
if doppelt then ...

Einzig und alleine die Geschwindigkeit könnte (unter gewissen Umständen) bei den direkten Vergleichen ein paar millionstel Sekunden schneller sein.

[Delphi-Narr]

#13

Ja, so hatte ich das jetzt auch gemacht.
Danke!

[gammatester]

Zitat:

Zitat von himitsu

Einzig und alleine die Geschwindigkeit könnte (unter gewissen Umständen) bei den direkten Vergleichen ein paar millionstel Sekunden schneller sein.

Aber nur, wenn Du es vernünftig programmiert hättest! Um Deinen Fehler zu sehen, teste mal Deinen Code mit folgenden Vorgaben:

Delphi-Quellcode:

setlength(arr, 10000000);
for i:=0 to high(arr) do arr[i] := i;
arr[0] := 1;

In der Zwischenzeit hier die Erklärung: Dein angeblich fast optimaler Code verläßt via break verläßt nämlich nur die innere for-Schleife, und die äußere Schleif wird immer wieder durchlaufen, auch wenn schon doppelte Einträge erkannt wurden. Wenn kein Goto oder exit aus einer separaten Funktion verwendet werden sollen, könnte ein verbesserter Vorschlag etwa so aussehen:

Delphi-Quellcode:

  doppelt := false;
  for i:=0 to High(arr)-1 do begin

    if not doppelt then begin
      for j:=i+1 to High(arr) do begin
        if arr[i]=arr[j] then begin
          doppelt := true;
          break;
        end;
      end;
    end;
  end;
  if doppelt then ...;

[daywalker9]

Das kann man noch weiter optimieren. So braucht man nicht immer wieder die erste for Schleife komplett durchlaufen

Delphi-Quellcode:

doppelt := false; 
  for i:=0 to High(arr)-1 do 
    begin 
      for j:=i+1 to High(arr) do 
        begin 
           if arr[i]=arr[j] then 
             begin 
                doppelt := true; 
                 break; 
             end; 
        end; 
      if doppelt then
       break;
    end; 
  end;

[himitsu]

Ach menno, das vergeß ich manchmal.

ich wünsche mir eh schon lange ein Break(2); für sowas. :cry:

[gammatester]

Zitat:

Zitat von daywalker9

Das kann man noch weiter optimieren. So braucht man nicht immer wieder die erste for Schleife komplett durchlaufen

Schon klar. Wie schon gesagt, wäre eine separate Funktion mit einem exit oder ein goto noch schneller.

Allerdings ist wohl selbst dann im schlimmsten Fall immer noch eine quadratische Laufzeit erforderlich. Mit einem n*log(n) Sortierverfahren mit anschließendem linearen Vergleich oder eine Hashliste hätte man eine bessere Worst-case-Laufzeit.

[himitsu]

Diese Schleife (inkl. richtiger Abruchbedingung) sollte im Worst-Case bei n*(n-1)/2 liegen. :gruebel:

PS: Aha, du willst also alles mehrfach durchgehn? @gammatester
- sortieren mit n*log(n)
- und prüfen mit n-1
wird bestimmt länger dauern.

[gammatester]

Zitat:

Zitat von himitsu

Diese Schleife (inkl. richtiger Abruchbedingung) sollte im Worst-Case bei n*(n-1)/2 liegen. :gruebel:

PS: Aha, du willst also alles mehrfach durchgehn? @gammatester
- sortieren mit n*log(n)
- und prüfen mit n-1
wird bestimmt länger dauern.

Da wird nix länger dauern (außer für sehr kleine Arrays). Mit der folgenden Initialisierung (beachte umgekehrte Sortierung)

Delphi-Quellcode:

setlength(arr, NMAX);
j := high(arr);
for i:=0 to j-1 do arr[i] := -i;
arr[j] := arr[j-1];

erhalte ich für NMAX:

Code:

20000 mit 'optimierter' Schleife 721 ms
20000 mit Quicksort 0 ms
1000000 mit Quicksort 220 ms

Den Wert für 1000000 mit 'optimierter' Schleife kannst Du ja mal bestimmen. Dabei ist der Ablauf mit Quicksort wie folgt:

Delphi-Quellcode:

Quicksort(...);
for i:=0 to high(arr)-1 do begin
  if arr[i]=arr[i+1] then begin
    doppelt := true;
    break;
  end;
end;