AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren
Zurück Delphi-PRAXiS Programmierung allgemein Algorithmen, Datenstrukturen und Klassendesign Delphi Objekte sortieren mit TArray<T>.BinarySearch

Objekte sortieren mit TArray<T>.BinarySearch

Ein Thema von Zacherl · begonnen am 13. Mär 2018 · letzter Beitrag vom 13. Mär 2018
Antwort Antwort
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.529 Beiträge
 
Delphi 10.1 Berlin Starter
 
#1

Objekte sortieren mit TArray<T>.BinarySearch

  Alt 13. Mär 2018, 17:01
Hallo zusammen,

ich habe eine Liste von Objekten und möchte diese per 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;
C ist hierbei die Anzahl der Items im Array und 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). 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 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;
FAccess ist hierbei ein Enum und FFlags ein array[0..N] of Enum .

Beobachtung: Nachdem ich von einem "normalen" EqualityComparer zum Eliminieren der Duplikate auf die Methode mit 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
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
5.961 Beiträge
 
Delphi 10.2 Tokyo Architect
 
#2

AW: Objekte sortieren mit TArray<T>.BinarySearch

  Alt 13. Mär 2018, 17:37
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.
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.529 Beiträge
 
Delphi 10.1 Berlin Starter
 
#3

AW: Objekte sortieren mit TArray<T>.BinarySearch

  Alt 13. Mär 2018, 20:10
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 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

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]
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)

Geändert von Zacherl (13. Mär 2018 um 21:09 Uhr)
  Mit Zitat antworten Zitat
Benutzerbild von Uwe Raabe
Uwe Raabe

Registriert seit: 20. Jan 2006
Ort: Lübbecke
5.961 Beiträge
 
Delphi 10.2 Tokyo Architect
 
#4

AW: Objekte sortieren mit TArray<T>.BinarySearch

  Alt 13. Mär 2018, 20:59
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;
Uwe Raabe
Certified Delphi Master Developer
Embarcadero MVP
Blog: The Art of Delphi Programming
  Mit Zitat antworten Zitat
Benutzerbild von Zacherl
Zacherl

Registriert seit: 3. Sep 2004
4.529 Beiträge
 
Delphi 10.1 Berlin Starter
 
#5

AW: Objekte sortieren mit TArray<T>.BinarySearch

  Alt 13. Mär 2018, 21:12
Danke Uwe, so funktioniert es

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 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
Projekte:
- GitHub (Profil, zyantific)
- zYan Disassembler Engine ( Zydis Online, Zydis GitHub)

Geändert von Zacherl (13. Mär 2018 um 21:17 Uhr)
  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 06:36 Uhr.
Powered by vBulletin® Copyright ©2000 - 2018, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2018 by Daniel R. Wolf