[gelöst] Schnelles Vergleichen/Suchen von Listeneinträgen

[Scotty]

Ich habe in etwa folgende Datenstruktur:

Code: Alles auswählen

TData=class
  property A:integer;
  property B:array[0..3] of byte;
  property C:char;
end;
 
TOneData=record
  Sum : integer;
  Text : string;
  Data : TList; //of TData
end;
 
FAllData : TList; //of TOneData

Nun kommt es vor, dass Einträge zur Liste hinzugefügt werden sollen, die schon drin sind. Das versuche ich zu vermeiden, indem ich alle Items vergleiche:

Code: Alles auswählen

function CompareData(aData,bData:TOneData):boolean;
begin
  Result:=false;
  if aData.Sum=bData.Sum and
     aData.Text=bData.Text and
     aData.Data.Count=bData.Data.Count then
  begin
    for i:=0 to aData.Data.Count-1 do 
     if TData(aData.Data[i]).A=TData(bData.Data[i]).A and //die Reihenfolge ist festgelegt
    ... then 
       Result:=true;
  end; 
end;

Das dauert allerdings eine Ewigkeit bei 100000 Einträgen. Mit CompareMem() habe ich immer gleich als Ergebnis bekommen und bin mir gar nicht sicher, ob das hier benutzt werden kann. Wie macht man so etwas schneller?

[af0815]

Hash bilden und Liste sortieren. Anhand vom Hash sieht man ob es unterschiedliche Einträge sind, ohne jedes Teilelement vergleichen zu müssen. Wenn du auch noch nach den Hash sortierst, so kann du sehr rasch suchen.

[Scotty]

Kannst du mal bitte ein Beispiel für Hash zeigen? Ich vermute integer*Konstante+ord(char)*Konstante etc.

[theo]

Bin kein Experte, aber vllt. hilft das:
http://www.freepascal.org/docs-html/fcl ... table.html" onclick="window.open(this.href);return false;

[af0815]

Ein Anregung als Code hier http://dada.perl.it/shootout/fpascal_allsrc.html oder auch hier http://home.netsurf.de/wolfgang.ehrhard ... sh_en.html

[Hitman]

Man braucht nicht unbedingt Hashes. Wenn man die Objekte der Liste eindeutig Sortieren kann, hat man im Prinzip schon einen Binärbaum den man also mit einer Komplexität von O(log n) durchsuchen kann.
Da die Daten in deinem Fall sehr schön vergleichbar und damit sortierbar sind, dürfte das eigentlich ideal sein.

[Scotty]

Auf die (viel einfachere) Lösung hat mich Andreas' Link gebracht. Ich sortiere jetzt die Liste zuerst und vergleiche dann von 1..Count-1 mit dem Vorgänger. Das dauert etwa eine halbe Sekunde (n Vergleiche) gegenüber 2min vorher (n*m Vergleiche). Warum der Unterschied so erheblich ist, verstehe ich allerdings nicht. Danke für alle Antworten!