Objekte sortieren mit TArray<T>.BinarySearch

[Zacherl]

Hallo zusammen,

ich habe eine Liste von Objekten und möchte diese per

Delphi-Quellcode:

TArray<T>.BinarySearch

in eine absolute Ordnung bringen und dabei sämtliche Duplikate eliminieren. Soweit so gut ... hier ein Auszug aus meinem Code:

Delphi-Quellcode:

if (not TArray.BinarySearch<T>(FItems, V, J, Comparer, N, C - N)) then
begin
  for K := C downto J + 1 do
  begin
    FItems[K] := FItems[K - 1];
  end;
  FItems[J] := V;
  Inc(C);
end;

Delphi-Quellcode:

C

ist hierbei die Anzahl der Items im Array und

Delphi-Quellcode:

N

ist ein Offset für den Fall, dass meine Liste ein paar vorwegstehende Default-Elemente besitzen soll (braucht in diesem Falle nicht zu interessieren).

Delphi-Quellcode:

FItems

wird am Anfang auf die gesamte Anzahl der Objekte festgelegt - hat also garantiert genug Platz.

Zum eigentlichen Problem: Für den Vergleich implementiere ich mir eine

Delphi-Quellcode:

CompareTo

Funktion, welche ich dann im Comparer aufrufe:

Delphi-Quellcode:

function TMyClass.CompareTo(Other: TMyClass): Integer;
var
  I: Integer;
begin
  Result := (Length(FFlags) + 1) * (Ord(FAccess) - Ord(Other.FAccess));
  for I := Low(FFlags) to High(FFlags) do
  begin
    Result := Result + (I + 1) * (Ord(FFlags[I]) - Ord(Other.FFlags[I]));
  end;
end;

Delphi-Quellcode:

FAccess

ist hierbei ein Enum und

Delphi-Quellcode:

FFlags

ein

Delphi-Quellcode:

array[0..N] of Enum

.

Beobachtung: Nachdem ich von einem "normalen"

Delphi-Quellcode:

EqualityComparer

zum Eliminieren der Duplikate auf die Methode mit

Delphi-Quellcode:

BinarySearch

umgestellt habe und ins Git committen wollte, ist mir aufgefallen, dass 57 Zeilen entfernt, aber nur 53 hinzugefügt wurden (ein Objekt pro Zeile). Aus irgendeinem Grund fehlen mir demnach 4 Datensätze.

:?: Ist meine Vorgehensweise - also über die Multiplikation eine Wertung herzustellen - so überhaupt korrekt?
:?: Falls ja, gibt es da bessere Ansätze, die weniger anfällig für Integer Overflows sind?

Kann mir hier irgendjemand auf die Sprünge helfen?

Viele Grüße
Zacherl

[Uwe Raabe]

Zitat:

Zitat von Zacherl (Beitrag 1395970)

:?: Ist meine Vorgehensweise - also über die Multiplikation eine Wertung herzustellen - so überhaupt korrekt?

Vermutlich nicht.

Nehmen wir statt Enums einfach Zahlen 0..9 und N = 1. A und B seien die beiden Flags-Arrays mit den Werten A=[0,2] und B=[1,0]. Die for-Schleife geht nun für I von 0 bis 1 und ermittelt:

result = 1*(0-2) + 2*(1-0) = -2 + 2 = 0

Der Comparer hält also die beiden Flag-Arrays für gleich.

[Zacherl]

Zitat:

Zitat von Uwe Raabe (Beitrag 1395975)

Zitat:

Zitat von Zacherl (Beitrag 1395970)

:?: Ist meine Vorgehensweise - also über die Multiplikation eine Wertung herzustellen - so überhaupt korrekt?

Vermutlich nicht.
[...]
Der Comparer hält also die beiden Flag-Arrays für gleich.

Macht Sinn. Bloß wie könnte ich es korrekt machen?

Edit: Alle

Delphi-Quellcode:

CompareTo

Implementierungen, die ich gefunden habe, geben lediglich Werte im Bereich [-1, 0, 1] zurück. Habe mir nun einen Testcode gebastelt, der auch wunderbar funktioniert.

Delphi-Quellcode:

type
  TTest = record
    A, B, C: Integer;
  end;

const
  A: array[0..4] of TTest = (
    (A:0; B:4; C:5),
    (A:3; B:4; C:5),
    (A:1; B:4; C:5),
    (A:0; B:1; C:5),
    (A:0; B:5; C:5)
  );

var
  B: TArray<TTest>;
  I, J, C, K: Integer;
begin
  SetLength(B, Length(A));
  FillChar(B[0], SizeOf(B), #0);
  C := 0;
  for I := Low(A) to High(A) do
  begin
    if not TArray.BinarySearch<TTest>(B, A[I], J, TComparer<TTest>.Construct(
      function(const Left, Right: TTest): Integer
      begin
        if (Left.A < Right.A) then Exit(-1) else if (Left.A > Right.A) then Exit(1);
        if (Left.B < Right.B) then Exit(-1) else if (Left.B > Right.B) then Exit(1);
        if (Left.C < Right.C) then Exit(-1) else if (Left.C > Right.C) then Exit(1);
      end), 0, C) then
    begin
      for K := C downto J + 1 do
      begin
        B[K] := B[K - 1];
      end;
      B[J] := A[I];
      Inc(C);
    end;
  end;
end;

Wenn ich das aber im Grunde 1 zu 1 auf mein richtiges Problem übertrage, kommt wieder nur Murks raus :x

Delphi-Quellcode:

function TMyClass.CompareTo(Other: TMyClass): Integer;
var
  I: Integer;
begin
  Result := 0;
  if (Ord(FAccess) < Ord(Other.FAccess)) then Exit(-1) else
  if (Ord(FAccess) > Ord(Other.FAccess)) then Exit(1);
  for I := Low(FFlags) to High(FFlags) do
  begin
    if (Ord(FFlags[I]) < Ord(Other.FFlags[I])) then Exit(-1) else
    if (Ord(FFlags[I]) > Ord(Other.FFlags[I])) then Exit(1);
  end;
end;

Ich erhalte z.b.:

Code:

[3, 7, 3, 3, 1]
[3, 7, 2, 3, 1]
[3, 7, 3, 3, 5]

gewüscht wäre aber:

Code:

[3, 7, 2, 3, 1]
[3, 7, 3, 3, 1]
[3, 7, 3, 3, 5]

[Uwe Raabe]

Delphi-Quellcode:

  Result := CompareValue(Ord(FAccess, Ord(Other.FAccess)));
  if Result <> 0 then begin
    for I := Low(FFlags) to High(FFlags) do
    begin
      Result := CompareValue(Ord(FFlags[I]), Ord(Other.FFlags[I]));
      if Result <> 0 then Break;
    end;
  end;

[Zacherl]

Danke Uwe, so funktioniert es :thumb:

Meine reineditierte Methode mit manueller Rückgabe von [-1, 0, 1] funktioniert tatsächlich auch. Ein weiteres Problem neben der Multiplikation aus dem ersten Post war nämlich, dass

Delphi-Quellcode:

FAccess

zwar zum Objekt gehört, ich dieses Feld allerdings gar nicht als Sortierkriterium aufnehmen darf, da es keine Auswirkung auf den generierten Datensatz hat. Dadurch sahen die Werte dann beim Sichten so zufällig aus :wall: