[gelöst]tDictionary

[exc-jdbi]

Guten Tag Community

Gibt es die tDictionary nicht in Lazarus? Ich brauche eine Möglichkeit die genau diese Funktionen erfüllt.

Die tDictionary sollte bei mir im Programm während der Laufzeit erstellt werden. Es sind mehrere Tausend Einträge drin. Von Zeit zu Zeit können es aber auch mehrere Zehntausend Einträge sein. Die tDictionary sollte also sehr schnell aufgebaut werden können.

Gleichzeitig brauche ich den sehr schnellen Zugriff auf einige Key's, um die entsprechenden Values's zu ermittel. Sobald ich die ermittelten Werte besitze, wird die tDictionary wieder komplett zerstört.

Gibt es hier vielleicht eine Alternative?

Danke für die Antworten.

Freundliche Grüsse

exc-jdbi

[exc-jdbi]

Ich glaube ich hab was jetzt gefunden. Ich muess es aber zuerst testen.

Code: Alles auswählen

TFPGMap

Freundliche Grüsse

exc-jdbi

[theo]

Hier gibt's sonst einen Überblick: http://wiki.freepascal.org/Data_Structu ... ollections

[ruewa]

Ich schlage mich mit dem Zeug derzeit auch rum. Ich nehme an, Du brauchst soetwas wie eine Turbo-Stringliste? Nichts, was eine TStringList nicht auch kann, aber eben schneller und leistungsfähiger?

Soweit ich es verstanden habe, muß man da zwei Dinge auseinanderhalten: Delphis TDictionary ist eine generische Hash-Tabelle (http://delphi.about.com/od/beginners/a/ ... delphi.htm). Die Frage ist also, was Du brauchst (und ich auch): Den speziellen (typliberaleren) Umgang mit einer generischen Klasse, oder vielmehr so etwas wie eine gedopete Stringliste, also irgendeine Hash-Tabelle.

Soweit ich es sehe, war die Entwicklung generischer Klassen auf der FPC-Agenda, ist nun aber aus dem Projekt herausgebrochen (https://code.google.com/p/fpc-generics-collections/):

New and first stable version of Generics. -> http://www.freesparta.com.
Project is no longer open source.

Nicht-generische Hash-Objekte gibt es allerdings mehrere in Free Pascal, am übersichtlichsten zusammengefaßt bei ftp://ftp.freepascal.org/fpc/docs-pdf/fcl.pdf, in Kapitel 7 "Reference for unit ’contnrs’". Desweiteren gibt es die StringHashMap (http://wiki.freepascal.org/StringHashMap) und dann die von Dir erwähnte TFPGMap, die aber eben aus dem Generika-Topf stammt (http://wiki.freepascal.org/Generics#Introduction, dieses:http://stackoverflow.com/questions/1577 ... freepascal hast Du wahrscheinlich schon gesehen).

Was mir noch völlig unklar ist, das sind die speziellen Unterschiede und Grenzen der jeweiligen Hash-Klassen. Es fehlt schlicht an einer etwas ausführlicheren Dokumentation, die die Funktionsweise dieser Klassen etwas besser erklären würde!

Ich habe einfach mal drauflos experimentiert und eine TStringList durch die einfachste Hash-Klasse, eine TFPHashList ersetzt - die vormaligen TStringList.Strings als TFPHashList Keys, die Objects als TFPHashList.Items. Bis jetzt funktioniert das mit > 4000 Einträgen prima und ist beeindruckend schnell. Ich konnte noch keine Einschränkungen bzw. konzeptuellen Denkfehler erkennen, was nicht heißen muß, daß ich da nicht doch total auf dem Holzweg bin und manches komplett falsch verstehe. Aber es hilft ja nix: Es gibt halt keinen, der einen da beim Händchen nimmt...

(Ein Problem ist nun bei mir, daß ich die Strings am Ende in sortierter Reihenfolge anzeigen will und mir noch kein besserer Weg eingefallen ist, als die Suchergebnisse doch wieder in eine Stringliste zu kopieren und dort sortieren zu lassen, was im speziellen Fall der Anzeige aller Elemente dann doch wieder richtig Zeit kostet. Übrigens habe ich bei der Gelegenheit (mithilfe des DbgTimers, sh. http://www.lazarusforum.de/viewtopic.php?f=29&t=8081) herausgefunden, daß entgegen aller Lehrbuchweisheit das Einfügen in eine sortierte TStringList um ein Drittel schneller ist als das unsortierte Einfügen mit abschließendem Durchsortieren - wohlgemerkt bei jener Größenordnung von 4000+ Einträgen)

Jedenfalls bin ich sehr interessiert daran, zu erfahren, welche Erfahrungen Du mit diesen Hash-Klassen sammelst!

Gruß Rüdiger

[exc-jdbi]

Guten Tag Community

Danke euch für die Antworten.

@ruewa:
Ich habe bis jetzt noch nichs definitives getestet. Da ich einfach noch nicht dazu gekommen bin. Eventuell klappt es aber heute Abend.

In meinem Fall brauche ich Schnelligkeit, beim Aufbauen der Tabelle. Welchen Art und auf welcher Funktion die Tabelle aufgebaut ist, finde ich im Moment noch sekundär. Wichtig für mich ist, dass ich ein Key-Wort zuführen kann, und dazu den entsprechenden Valuewert bekomme. Im Prinzip wäre mir auch eine Funktion wie sie die tDictionary<string,string> erfüllt auch willkommen.

Das im sortierten Zustand schneller geAppt werden kann, habe ich irgendwo schon mal gelesen und ist mir noch vage in Errinnerung, weiss aber leider nicht mehr wo und in welchem Zusammenhang ich das gelsen habe. Aber es ging glaube ich um Stringlisten. Diese Funktion wäre sicher noch nützlich, sofern ich die Liste abspeichern würde. Beides brauche ich nicht unbedingt.

Leider ist auch mir nicht in Allem klar wo die 'speziellen Unterschiede und Grenzen' liegen. Es bleibt mir darum nur die Möglichkeit im Internet zu suchen, und zu hoffen das ich mehr darüber erfahren kann. Oder ich teste es wie ich das jetzt in meinem Fall vorhabe.

Ich hoffe das mit Deinem Beitrag andere Teilnehmer auch angeregt sind, Infos abzugeben. Wäre sicher nicht schlecht.


Freundliche Grüsse

exc-jdbi

Ps. Deine Version werde ich mir auch noch genauer anschauen.

[ruewa]

Hallo exc-jdbi,

gefühlsmäßig würde ich sagen, laß mal lieber vorerst die Finger von diesem Generics-Zeug, das scheint doch noch in einem sehr undefinierten Entwicklungszustand zu schweben (oder weiß da jemand Genaueres?). Andererseits denke ich, mit TFPHashList, TFPStringHashTable, TStringHashMap oder einem auf TFPCustomHashTable aufgesetzten Eigenkonstrukt müßtest Du auf jeden Fall weiterkommen. Wenn Du soetwas wie ein tDictionary<string,string> brauchst (also Datensätze mit zwei gekoppelten Strings), würde ich auf Anhieb erstmal an eine TFPHashList mit Key/PChar denken.

Unabhängig von dem konkreten Anwendungsfall will ich mal (ungeachtet der Gefahr, mich gewaltig zu blamieren und in der gleichen Hoffnung wie Du auf qualifizierte Kommentare, und sei es auch vernichtende/erhellende Kritik) zugespitzt darstellen, wie ich mir das bis hierher zusammengereimt habe:

Von außen betrachtet ist eine TFPHashList eigentlich nichts wesentlich anderes als eine TStringList. TStringList bietet mehr Schnickschnack, TFPHashList ist erheblich performanter. Aber mit Ausnahme der Sortierfunktion und ein paar Gimmicks wie Name-Value-Paaren, Stream und File-Unterstützung etc. erfüllen beide so ziemlich die gleichen Grundfunktionen: Beide stellen eine Liste von mit Pointern gekoppelten Strings dar. Beide bieten einen indizierten Zugriff auf die Datenpaare, beide bieten Verwaltungsfunktionen wie Clear und Count. Lassen wir mal die typbezogenen Feinheiten beiseite (da gibt es ja auch noch TFPObjectHashTable), stellt sich der Vergleich in etwa so dar:

Code: Alles auswählen

TStringList.AddObject               entspricht   TFPHashList.Add
TStringList.Strings[Index]          entspricht   TFPHashList.NameOfIndex[Index]
TStringList.Objects[Index]          entspricht   TFPHashList.Items[Index]
TStringList.IndexOfObject(TObject)  entspricht   TFPHashList.IndexOf(Pointer)
TStringList.IndexOf(String)         entspricht   TFPHashList.FindIndexOf(String)
 

usw. Etwas hakelig wird es nur, wenn man bereits vorhandene Strings ändern will:

Code: Alles auswählen

TStringList.Strings[Index] := '...' entspricht   TFPHashList.Rename(TFPHashList.NameOfIndex[Index], NewName)
 

Eine wichtige Einschränkung besteht allerdings darin, daß Hashlisten keine Duplikate (als Keys) akzeptieren, während dies bei Stringlisten grundsätzlich möglich ist (bei unsortierten Stringlisten sowieso und bei sortierten abhängig von der Property Duplicates).

Intern allerdings sind String- und Hashlisten vollkommen unterschiedlich organisiert.

Die Hemmschwelle, Hashlisten anstelle von Stringlisten, an die man sich ja längst gewöhnt hat, einzusetzen, ergibt sich m.E. vor allem daraus, daß die Terminologie ziemlich unterschiedlich ist. Aus Entwicklersicht kann ich sogar verstehen, warum man sich bemüht hat, die völlig andere interne Architektur in die Namensgebung der Schnittstellen zum Anwender einfließen zu lassen. Aber das trägt eben auch erheblich zur Verwirrung bei: Aus der Menschensprache gesehen, stellt bei einer Stringliste eben jener String den Hauptdarsteller, während das angeklebte Objekt nur als Gimmick erscheint. Bei einer Hashliste hingegen sieht der String, dort "Key" genannt, eher wie ein leider notwendiges Übel aus, ein Schlüssel, den man halt mit sich herumschleppen muß, während der Pointer als das eigentliche Ziel der Begierde erscheint. Da spielt uns aber nur unsere eigene Sprache einen Streich, denn in der Substanz beschreiben beide Listen dieselbe Grundstruktur!

Und ganz getrennt davon trägt dann die unterschiedliche Semantik von generischen und konventionellen Objekten noch zusätzlich zur Verwirrung bei.

So - da habe ich mich nun aber ganz schön weit aus dem Fenster gelehnt! Denn in Wirklichkeit bin ich mir keineswegs sicher, ob ich das alles richtig verstanden habe. Reißt mir also bitte nicht gleich den Kopf ab, falls ich irgendwo völlig danebenliegen sollte, sondern klärt mich (und den Rest der Welt) auf...

Gruß Rüdiger

[Patito]

Hallo exc-jdbi,

gefühlsmäßig würde ich sagen, laß mal lieber vorerst die Finger von diesem Generics-Zeug, das scheint doch noch in einem sehr undefinierten Entwicklungszustand zu schweben (oder weiß da jemand Genaueres?).

So in der Art würde ich das auch sagen. Es liegt nicht einmal so sehr am Entwicklungszustand.
Generics haben bei Containern einfach ein paar prinzipielle Probleme:

1) Performance
Generische Container verwenden eigentlich immer irgendeine Compare-Funktion um Objekte zu vergleichen,
diese wird bei allen wichtigen Operationen ständig aufgerufen.
Prinzipbedingt ist man damit langsam (-> langwieriger Funktionsaufruf vs. ggf. einzelne Assember-Anweisung, die zwei Interger vergleicht).
Grob geschätzt liegt der Geschwindigkeitsverlust durch die Compare-Funktionen auf einer Skala von Faktor 2 bis 10 eher Richtung Faktor 10...

2) Methoden-Signaturen
Wenn man ein (Key, Value)-Paar in einen Container wirft, will man es auch über den Key wieder finden können.
Besteht der Key z.B aus zwei Integern (X, Y) sieht das z.B. so aus:

Code: Alles auswählen

 
function TMyContainer.GetItem_ForKey(const X: Integer; const Y: Integer): TMyItem; // für eindeutige Maps
 
function TMyMultiContainer.GetItem_ForKey(const X: Integer; const Y: Integer; const Index: Integer): TMyItem; // für MultiMaps
 

Mit Generics kriegt man Prozedur-Signaturen, die je nach Key-Typ komplett unterschiedlich sind nicht vernünftig hin.
Daher sind die Methodensignaturen bei Generischen Containern nicht sonderlich gut.

Außerdem noch:
3) Generische Container sind vom Code her etwas unverständlicher
4) Generische Typen sind beim Debuggen/Profilen unhandlicher

Insgesamt:
Langsam, unpassendes Interface, unhandlicher und weniger lesbar....
Generische Container sind zwar für ein paar Sachen ganz praktisch, aber im Grunde ist das ganze Konzept nur eine halbe Sache.

[exc-jdbi]

Guten Tag Community

Meinen Dank für die Antworten. Dir besonders ruewa.

Wie ich noch in Erinnerung habe, besitzen Generics jedoch auch Ihre Vorzüge. Ob diese genauso auf Lazarus abgeleitet werden kann weiss ich nicht, aber ich nehme schon an. Generics verarbeiten nähmlich nur gleiche Typen, was bedeutet, dass man sich schlussendlich auf eine Art und Weise festlegen muss.

Auf der anderes Seite finde ich Generics ziemlich als stabil und was für mich auch wichtig ist, als sehr leicht zu implemetieren. Performensunterschiede empfand ich im normalen Rahmen.

Mit Hashtabels i.e.S. habe ich noch nicht viel gearbeitet. Aber die Gegebenheiten für den Zugriff auf einen "key-Schlüssel" mit entsprechender Ausgabe des Valuewertes sind hier klar gegeben, und das kann ich immer brauchen. Wenn dann noch ein Performensgewinn besteht dann sowieso.


Ich wollte es noch ein bisschen genauer Wissen, und habe mir kurz einen Testlauf geschrieben. Eigenlich sind es deren Drei die ich gemacht habe, und die "TFPGMap" habe ich auch gleich rein genommen, obwohl ich sie nicht benutzen werde.

Bei der "TFPHashList" hab ich jedoch die Sortier- und die Moving-Funktionen noch nicht realisiert. Ich werd mir aber noch gedanken machen, wie man dies lösen könnte. Ich hab mal etwas von verketteten Zeigerlisten gelesen, aber weiss noch nicht, ob man dies genau auf dieses Problem ansetzen kann.

Hier die Auswertungen. Die Tests sind nur auf die Bestimmung der Geschwindigkeit ausgelegt, bei 1 Mio. Datensätzen.

Freundliche Grüsse

exc-jdbi

Check tStringList

tStringlist.jpg (15.44 KiB) 3184 mal betrachtet

Check tfpgMap

tfpgMap.jpg (17.76 KiB) 3184 mal betrachtet

Check tfpHashList

tfpHashList.jpg (16.15 KiB) 3184 mal betrachtet

[ruewa]

Das ist schon mal sehr interessant, herzlichen Dank, exc-jdbi! Auch Dir, Patito, für die aufschlußreiche Darstellung zum Thema Generics!

Mir ist leider nicht ganz klar, was Deine einzelnen Routinen genau machen. Was macht LoadArray, was macht LoadDictionary (anders), was macht CreateDictionary (das ja doch einen großen Batzen Zeit verbraucht und daher mehr sein muß als ein simples List.Create)?

Was hat es mit den Find-in-Dictionary-Methoden auf sich? Gerade hier sind ja erhebliche Performance-Unterschiede zu erwarten, also wäre es vielleicht interessant, das mal mit 1000 (oder mehr) statt nur 10 Durchläufen zu testen.

Würde es Dir was ausmachen, den Quelltext zu posten (oder auch per PN/email)?

Der größte Flaschenhals ist offenbar das Sortieren (das ist auch mein größtes Probem im Moment). Das scheint die TFPGMap gut zu beherrschen. Die hatte ich mir noch gar nicht angesehen, aber vielleicht lohnt sich das. Ich will mal versuchen, zu verstehen, was sie da beim Sortieren genau macht, vielleicht läßt sich der Ansatz ja übernehmen. Aus welchen Gründen hast Du sie verworfen?

Gruß Rüdiger

[exc-jdbi]

Guten Tag ruewa

1. Erzeugen der Rnd-Array
Generiert in eine 'Array of Integer' eine Mio Zahlen und mische die ordendlich durch. Vorteil keine Dublikate.

2. Save Array
Speichere die soeben erzeugte unsortiere 'Array of Integer' auf die Hardware. Nur Standardkomponenten genommen.

3. Load Array
Die soeben abgespeicherte Liste wieder in das Programm einnehmen. (Neue Variable !)

4. Create Dictionary
(3 Programme je tfpgMap, tStringList, tfpHashList als Dictionary). Die Erstellung der jeweiligen Listen musste ich unterschiedlich auslegen. Die oben erzeugte Arrayliste (Nur die Werte z.B. key15 und dazu dann Value15) habe ich in die "Dictionary" (ich nenne sie jetzt einfach mal so) eingefügt, damit ich die Grundbasis Dictionary<String>,<String> erfülle.
Ich hätte auch die Array direkt in den Valuewert miteinbeziehen können, war aber für diesen Test nicht Sinn der Sache. Also habe ich mir eine Tlist genommen, und den Valuewert als String hinterlegt. Es Simuliert i. e. S. eine komplett neu erzeugte "Dictionary".

5. Save Dictionary
Ich hab mir dazu die einfachste Möglichkeit genutzt, die mir dazu in den Sinn gekommen ist. Nichts spezielles, und auch nicht's ausgeklügeltes. Aber doch so, dass Keywert + Valuewert beim Loadprozess wieder fehlerfrei in das Programm einbezogen werden konnte.

6. Load Dictionary
Lade die vorher auf der Hardware gespeicherten Daten wieder in die Dictionary. (Neue Variable !!)

7. Find in Dictionary
Finde 10 zufällig erzeute Key-Werte in der Dictionary und gib den Valuewert aus. (Reine simulative Darstellung)


8. Sort Dictionary.
Auch hier habe ich mir die Möglichkeiten die mir gegeben sind ausgenutzt, Nichts Spezielles und auch nichts ausgeklügeltes. Einfach "Standardkomponenten" halt, die im Lazarus vorhanden sind.
Wichtig war für mich, dass die Sortierung richtig verlauft. Komplette "Selective" Sortierung des Key-Value's und zwar so, dass die entsprechenden Valuewerte dann auch immer noch zu den entsprechenden Key's gehören.
Bei der tStringlist hatte ich ein Problem, und musste mir etwas einfallen lassen, damit nachher die Valuewerts wieder am richtigen Ort waren. Da es sich nur um "Standardkomponenten" handelt, die ich dafür genutzt habe, entsteht auch die extrem hohe Sortierungszeit. Es ist aber schon so, wie du es Anfangs erwähnt hast. Eine Sortierung der Werte in der tStringlist bezieht sich nur auf die Key-Werte. Schon dies alleine braucht sehr lange. Schlussendlich ist es also eine reine Summierung der entsprechenden Zeiten.

9. Remove oder Delete
Lösche 10 zufällige Key, mit der entsprechenden Values aus der Dictionary. (Reine simulative Darstellung)

10.Move
Verschiebe 10 zufällig gewählte Key, an einen zufällig gewählten Ort. (Reine simulative Darstellung)


Du siehst nichts weltbewegendes.

Die unterschiedlichen Zeiten, obwohl die ersten 3 Routinen (Arrays erzeugen,speichern, laden) komplett gleich sind, ist wohl Windowsbedingt. Die entsprechenen Zeiten habe ich mit 'GetTickCount' festgehalten.


Wenn einer der 10 Routinen komplett richtig verlauft, weise ich der entsprechenden Label einfach die Farbe grün zu. Standardmässig sind sie auf Rot gestellt.


Alle 3 Varianten finden die 10 zufällig gewählten Key's innert 0 ms. Du hast recht, ich hätte hier die Zahl ein bisschen höher setzen sollen, so z.B. auf 1000, so hätte sich sicher einen höheren Wert als 0 ms ergeben.


Der Grund warum ich die tfpgMap verworfen hab, liegt schon am Entwicklungsstand. Anderseits möchte ich mir etwas eigenes machen. Wäre für mich der ideale Zeitpunkt mich mehr mit den Pointern zu beschäftigen.


Freundliche Grüsse


exc-jdbi

[mse]

Der Grund warum ich die tfpgMap verworfen hab, liegt schon am Entwicklungsstand. Anderseits möchte ich mir etwas eigenes machen. Wäre für mich der ideale Zeitpunkt mich mehr mit den Pointern zu beschäftigen.

Dann interessiert dich vielleicht diese Implementierung von Hashlisten welche viel mit Pointern macht.

[exc-jdbi]

Danke mse

Werde ich mir heute Abend anschauen.

Freundliche Grüsse

exc-jdbi

[BeniBela]

1) Performance
Generische Container verwenden eigentlich immer irgendeine Compare-Funktion um Objekte zu vergleichen,
diese wird bei allen wichtigen Operationen ständig aufgerufen.
Prinzipbedingt ist man damit langsam (-> langwieriger Funktionsaufruf vs. ggf. einzelne Assember-Anweisung, die zwei Interger vergleicht).
Grob geschätzt liegt der Geschwindigkeitsverlust durch die Compare-Funktionen auf einer Skala von Faktor 2 bis 10 eher Richtung Faktor 10...
.

Wenn es richtig implementiert wurde, kann man eine inline Funktion mit in den Generikparametern haben, und der Compiler optimiert die dann weg.




Weiß jemand, ob es irgendwo ein immutable Dictionary gibt? Jedes Einfügen/Löschen erstellt eine Kopie des Dictionarys, aber in O(1)...

[ruewa]

Hallo exc-jdbi,

ich bin mit der Sortiergeschichte weitergekommen. TFPGMap.Sort ist letztlich in der TFPSList (einem Vorfahr der TFPGMap) implementiert. Dort befindet sich auch eine spezialisierte Quicksort-Methode, die ich für meine Zwecke umgestrickt habe.

Die Grundidee ist, ein PShortString-Array parallel zur TFPHashList zu erzeugen, in der zu Beginn des Sortiervorgangs alle Pointer auf die Hashlist-Keys abgelegt werden, bei zunächst identischer Indizierung (also PointerArray(i) = Pointer auf den Key-String von Hashlist.Items(i)). Bei der TFPHashlist ist zu beachten, daß deren Keys nur Shortstrings sein dürfen (was für meine Zwecke allerding vollkommen ausreicht). Der Stringvergleich greift dann über diese Pointer auf die Keys zu. Geordnet wird aber nur das Pointerarray, die Hashliste selbst und ihre Keys bleiben unangetastet. Liest man nach dem Sortieren das Array sequentiell aus und überträgt die dort verlinkten Keys in eine (unsortierte) Stringliste, sind deren Einträge dann sozusagen "wie von Geisterhand" alphabetisch sortiert (wahlweise case-sensitiv oder -insensitiv).

Das bringt nochmal ganz ordentlich was. Hier die Zeiten im Vergleich (jeweils mit denselben Daten, bestehend aus 4112 Einträgen und getestet mit DebugTimer) :
435 ms = 0,106 ms/Key --- Übertragen aller Keys in eine unsortierte Stingliste mit abschließendem StringList.Sort
259 ms = 0,063 ms/Key --- Übertragen aller Keys in eine sortierte Stingliste
135 ms = 0,033 ms/Key --- Sortieren im Pointerarray und Übertragen der sortierten Keys in eine unsortierte Stringliste
von Letzterem anteilig:
122 ms = 0,029 ms/Key --- QuickSortHashList
11 ms = 0,003 ms/Key --- Übertragen der Keys in eine unsortierte Stingliste

Das halbiert den Zeitbedarf damit ziemlich genau gegenüber dem Einfügen in eine sortierte Stringliste. Erstaunlicherweise ist das case-insensitive CompareText nicht langsamer als das sensitive CompareStr, sogar einen ganz kleinen Tick schneller (1 % Unterschied). Ich will mal sehen, ob eine ShortString-spezialisierte Variante der Compare-Funktionen noch etwas bringt, insbesondere der annähernd identische Zeitbedarf von CompareStr und CompareText hat mich doch ins Grübeln gebracht. Wenn noch was zu holen ist, dann eigentlich nur in der Compare-Methode. Mal sehen.

Hier der Code:

Code: Alles auswählen

type
  TCompareFunc = function(const Key1: String; const Key2: String): Integer;
  TSortArray   = Array of PShortString;
 
procedure QuickSortHashList(const HL: TFPHashList; var SA : TSortArray; Compare: TCompareFunc);
var
  n : integer;
 
  {Sub-}
  procedure DoQuickSort(L, R: integer);
  var
    I, J, P : Integer;
    tmp,
    PivotItem: PShortString;
  begin
    repeat
      I := L;
      J := R;
      P := (L + R) div 2;
      repeat
        PivotItem := SA[P];
        while Compare(PivotItem^, SA[I]^) > 0 do Inc(I);
        while Compare(PivotItem^, SA[J]^) < 0 do Dec(J);
        if I <= J then
        begin
          tmp := SA[I];
          SA[I] := SA[J];
          SA[J] := tmp;
          if P = I then P := J
          else if P = J then P := I;
          Inc(I);
          Dec(J);
        end;
      until I > J;
      if L < J then DoQuickSort(L, J);
      L := I;
    until I >= R;
  end;
  {/Subprocedure DoQuickSort}
 
{main QuickSortHashList}
begin
  if not Assigned(HL) or not Assigned(Compare) then exit;
  SetLength(SA, HL.Count);
  for n := 0 to HL.Count - 1 do SA[n] := PShortString(@HL.Strs[HL.List^[n].StrIndex]);
  if (HL.Count < 2) then exit;                  // Anordnung wg. Sonderfall Count=1
  DoQuickSort(0, HL.Count-1);
end;

Aufgerufen wird das dann so:

Code: Alles auswählen

var
  HashList     : TFPHashList;
  SortArray    : TSortArray;
  StringList   : TStringList;
  cnt          : integer;
 
{...}
begin
  StringList.Sorted := false;
  QuickSortHashList(HashList, SortArray, @CompareText);       // case-insensitive
  { alternativ case-sensitiv:   QuickSortHashList(HashList, SortArray, @CompareStr); }
  for cnt := 0 to HashList.Count - 1 do
      StringList.AddObject(SortArray[cnt]^, HashList.Find(SortArray[cnt]^);
end;

Wie immer: Ohne Gewähr! Meine Ausgabe sieht unauffällig aus, aber als "getestet" würde ich das noch nicht bezeichnen. Schon möglich, daß dort noch irgendwo eine kleinere Schweinerei schlummert...

Hilft Dir das weiter?

Gruß Rüdiger

[ruewa]

Jetzt aber!

Ich hatte gedacht, CompareStr / CompareText ließen sich vielleicht noch um 20, 30 % aufbohren. So kann man sich täuschen...

In 23 ms (case-sensitiv) bzw. 29 ms (case-insensitiv) rauscht das Zeug jetzt komplett durch - inclusive Laden der Stringliste und ein bißchen drumherum. Die reine Sortierzeit mit QuickSortHashList beträgt abhängig von den verschiedenen Compare-Funktionen für jeweils 4112 Elemente:

Code: Alles auswählen

SysUtils.CompareStr:              125 ms = 30,3 µs / Key
SysUtils.CompareText:             124 ms = 30,2 µs / Key
CompareAsciiShortStrInsensitive:   17 ms =  4,2 µs / Key
CompareAsciiShortStrSensitive:     11 ms =  2,7 µs / Key

Die Zahlen geben den Durchschnitt wieder, sie schwanken von Lauf zu Lauf immer so um +- 1%. Übrigens bringt die Inline-Deklaration der Compare-Funktionen keine erkennbare Verbesserung.

Also: Roundabout Faktor 10 beim Compare, insgesamt Faktor 20 gegenüber dem Sortieren via Stringliste! Und jetzt ist's auch ein gesundes Verhältnis zwischen sensitivem und dem aufwendigeren insensitiven Vergleich... Wobei:

1) Die Zeit pro Key dient erstmal vornehmlich dem Ego, wenn Du sie überschlägig hochrechnen willst auf Deine Datenmenge, mußt Du bedenken, daß die Anzahl der notwendigen Vergleichsoperationen >= n * log(n) ist, der Zeitbedarf also (leicht) überproportional zunimmt.

2) Die hier vorgestellten Sortier- und Vergleichsroutinen sind beschränkt auf ShortStrings (nur die kann die TFPHashList verarbeiten) und, was für Dich wahrscheinlich kritischer ist, auf ASCII-Zeichen. Letzteres gilt allerdings auch für SysUtils.CompareStr/-Text, von daher ist der Vergleich schon korrekt. Ob sich eine ähnlich spektakuläre Verbesserung auch in Bezug auf AnsiCompareStr/-Text erzielen läßt, kann ich nicht einschätzen, würde aber vermuten, daß sich der Versuch schon lohnen könnte.

3) Die Deklaration der Compare-Methoden ist gegenüber dem oberen Listing verändert.

Hier die beiden Vergleichsroutinen:

Code: Alles auswählen

type
  TCompareFunc = function(const Key1, Key2: ShortString): SmallInt;
 
 
function CompareAsciiShortStrSensitive(const S1, S2 : ShortString): SmallInt;
var
  i, len : SmallInt;
begin
  result := 0;
  i := 0;
  if S1[0] > S2[0] then len := Byte(S2[0]) else len := Byte(S1[0]);
  while (result = 0) and (i < len) do
  begin
    inc(i);
    result := Byte(S1[i]) - Byte(S2[i]);
  end;
  if result = 0 then result := Byte(S1[0]) - Byte(S2[0]);
end;
 
 
function CompareAsciiShortStrInsensitive(const S1, S2 : ShortString) : SmallInt;
var
  i, len, B1, B2 : Byte;
begin
  result := 0;
  i := 0;
  if S1[0] > S2[0] then len := Byte(S2[0]) else len := Byte(S1[0]);
  while (result = 0) and (i < len) do
  begin
    inc(i);
    B1 := Byte(S1[i]);
    B2 := Byte(S2[i]);
    if B1 in [97..122] then dec(B1, 32);
    if B2 in [97..122] then dec(B2, 32);
    result := B1 - B2;
  end;
  if result = 0 then result := Byte(S1[0]) - Byte(S2[0]);
end; 

Aufruf dann entsprechend mit

Code: Alles auswählen

  QuickSortHashList(HashList, SortArray, @CompareAsciiShortStrInsensitive);       // case-insensitiv oder...
  QuickSortHashList(HashList, SortArray, @CompareAsciiShortStrSensitive);        // case-sensitiv
 

Doch... So macht Programmieren wirklich Spaß...

Gruß Rüdiger


Edit: Mysteriöserweise läuft CompareAsciiShortStrSensitive um ca. 6 % schneller, wenn die lokalen Variablen i und len als SmallInt deklariert werden anstatt als Byte. Bei CompareAsciiShortStrInsensitive ist es hingegen (in derselben Größenordnung) genau umgekehrt... Der Compiler scheint da auf unterschiedliche Optimierungen zurückzugreifen, was vermutlich darauf zurückzuführen ist, daß er die 4 * 8-Bit- bzw. 2 * 16-Bit-Variablen im Programmablauf eleganter durch die CPU-Register jonglieren kann).