Discussion:
Sortierte Listen
(zu alt für eine Antwort)
Matthias Frey
2013-03-22 19:36:14 UTC
Permalink
Hallo,

ich schaue gerade die unit System.Generics.Collections (XE3) durch
und wundere mich, dass ich keine sortierte Liste finde.
In der Regel kann man zwar sortieren, aber nur mit einer separaten
Operation. Eine sortierte Liste oder gar einen AVL-Baum habe ich
dort nicht gefunden.
Ein TDictionary ist zwar schnell, aber auch nicht sortiert.

Ich habe noch eine alten Implementation einer sortierten Liste
ohne Generic (TStSortedCollection) in Verwendung und möchte die
nun ablösen.

Weiß oder hat jemand was?

Nachtrag: Habe da etwas gefunden:
http://code.google.com/p/delphi-coll/

Dort gibt es eine TSortedList<T>, aber die Implementation ist
nicht schnell: "Supports indexing, fast lookup and enumeration
operations, doesn't support sorting or reversing. Slower insert
times because of automated sorting. If you plan to use a list
that is always sorted, and if you don't plan on inserting or
removing a lot, then this is the best choice. If you need
sorted elements but need to insert/add/remove a lot, use
TList<T> and sort on demand."

Auch gibt es da noch: TSortedDictionary<TKey,TValue>
Die sieht recht gut aus. Was mich daran stört ist
a) die Lizenzbedingungen und
b) dass die Letzte Änderung von 2011 ist

Hat jemand Erfahrungen, Ideen, Meinungen?
Danke.

Matthias
Peter
2013-03-23 09:01:59 UTC
Permalink
Post by Matthias Frey
Hallo,
ich schaue gerade die unit System.Generics.Collections (XE3) durch
und wundere mich, dass ich keine sortierte Liste finde.
In der Regel kann man zwar sortieren, aber nur mit einer separaten
Operation. Eine sortierte Liste oder gar einen AVL-Baum habe ich
dort nicht gefunden.
Ein TDictionary ist zwar schnell, aber auch nicht sortiert.
Ich habe noch eine alten Implementation einer sortierten Liste
ohne Generic (TStSortedCollection) in Verwendung und möchte die
nun ablösen.
Weiß oder hat jemand was?
http://code.google.com/p/delphi-coll/
Dort gibt es eine TSortedList<T>, aber die Implementation ist
nicht schnell: "Supports indexing, fast lookup and enumeration
operations, doesn't support sorting or reversing. Slower insert
times because of automated sorting. If you plan to use a list
that is always sorted, and if you don't plan on inserting or
removing a lot, then this is the best choice. If you need
sorted elements but need to insert/add/remove a lot, use
TList<T> and sort on demand."
Um eine Liste zu sortieren muß man wissen, wie zwei Einträge zu
vergleichen sind. Dafür gibt es keine allgemeine Lösung, weshalb die
generischen Container dieses Problem quasi outsourcen: man kann dem
Container beim Erzeugen eine geeignete Implementierung von IComparer<T>
mitgeben.

Allerdings hast Du Recht, es gibt keinen Container, der immer sortiert
bleibt, auch wenn man neue Elemente hinzufügt. Man kann das zwar
relativ einfach nachrüsten (Notify-Methode überschreiben, beim
Hinzufügen eines neuen Elements Liste sortieren), aber das ist
natürlich nicht besonders effizient. Und es gibt immer noch reichlich
Möglichkeiten, die Liste aus der Sortierfolge zu bringen, ohne das sie
das mitkriegt. Nimm eine Liste von Objekten, die basierend auf einem
Datenelement des Objektes sortiert ist. Man kann dieses Element ändern,
ohne das die Liste das mitkriegt. Vermutlich gibt es deshalb keine
generische TSortedList<T> oder so, sie würde einfach nicht für alle
möglichen Datentypen funktionieren. Und man erwartet von einem
generischen Typ das er das kann.
--
Peter Below
Matthias Frey
2013-03-25 12:38:05 UTC
Permalink
Post by Peter
Post by Matthias Frey
Hallo,
ich schaue gerade die unit System.Generics.Collections (XE3) durch
und wundere mich, dass ich keine sortierte Liste finde.
In der Regel kann man zwar sortieren, aber nur mit einer separaten
Operation. Eine sortierte Liste oder gar einen AVL-Baum habe ich
dort nicht gefunden.
Ein TDictionary ist zwar schnell, aber auch nicht sortiert.
Ich habe noch eine alten Implementation einer sortierten Liste
ohne Generic (TStSortedCollection) in Verwendung und möchte die
nun ablösen.
Weiß oder hat jemand was?
http://code.google.com/p/delphi-coll/
Dort gibt es eine TSortedList<T>, aber die Implementation ist
nicht schnell: "Supports indexing, fast lookup and enumeration
operations, doesn't support sorting or reversing. Slower insert
times because of automated sorting. If you plan to use a list
that is always sorted, and if you don't plan on inserting or
removing a lot, then this is the best choice. If you need
sorted elements but need to insert/add/remove a lot, use
TList<T> and sort on demand."
Vielleicht muss ich vorraus schicken dass ich statt Listen
besser Container geschrieben hätte. Es muss keine Liste sein.
Post by Peter
Um eine Liste zu sortieren muß man wissen, wie zwei Einträge zu
vergleichen sind. Dafür gibt es keine allgemeine Lösung, weshalb die
generischen Container dieses Problem quasi outsourcen: man kann dem
Container beim Erzeugen eine geeignete Implementierung von IComparer<T>
mitgeben.
Ja, klar. Habe ich schon einige Male so benutzt.
Post by Peter
Allerdings hast Du Recht, es gibt keinen Container, der immer sortiert
bleibt, auch wenn man neue Elemente hinzufügt. Man kann das zwar
relativ einfach nachrüsten (Notify-Methode überschreiben, beim
Hinzufügen eines neuen Elements Liste sortieren), aber das ist
natürlich nicht besonders effizient. Und es gibt immer noch reichlich
Möglichkeiten, die Liste aus der Sortierfolge zu bringen, ohne das sie
das mitkriegt. Nimm eine Liste von Objekten, die basierend auf einem
Datenelement des Objektes sortiert ist. Man kann dieses Element ändern,
ohne das die Liste das mitkriegt.
Dann brauchts halt ein Notify-Event.
Post by Peter
Vermutlich gibt es deshalb keine
generische TSortedList<T> oder so, sie würde einfach nicht für alle
möglichen Datentypen funktionieren. Und man erwartet von einem
generischen Typ das er das kann.
Das verstehe ich nicht. Warum sollte das nicht gehen?
Bei einem TDictionary geht es doch auch. Und dass ein eingefügtes
Element geändert oder gar gelöscht wird kann man den Entwickler
nicht hindern. Gegen alle Dummheiten muss so ein Container auch nicht
sein.

Embarcadero sollte da was tun. AVL-Bäume gibt es schon seit
min. 20 Jahren. Und für etliche Anwendungen ist ein AVL-Baum optimal.
(Andere Bäume gibt es ja auch nicht.)


Matthias
Arno Garrels
2013-03-26 06:41:24 UTC
Permalink
Post by Matthias Frey
Embarcadero sollte da was tun. AVL-Bäume gibt es schon seit
min. 20 Jahren. Und für etliche Anwendungen ist ein AVL-Baum optimal.
(Andere Bäume gibt es ja auch nicht.)
Ich wollte vor einem Jahr meinen AVL-Baum zum generischen machen.
Das scheiterte daran, dass es nicht möglich war, einen Pointer
auf ein generisches Record zu deklarieren:

PNodeRec<T> = ^TNodeRec<T>; // <<= Compiler error
TNodeRec<T> = record
Data: T;
Link array [0..1] of PNodeRec<T>;
end;

Also müsste man TNodeRec<T> als Klasse deklarieren, das wäre aber
langsamer, habe ich deshalb bisher nicht gemacht.

Seltsam nur, dass folgendes Beispiel funktioniert:

TNodeRec<T> = record
PNodeRec: ^TNodeRec<T>;
end;
--
Arno
Matthias Frey
2013-03-27 12:38:22 UTC
Permalink
Post by Arno Garrels
Post by Matthias Frey
Embarcadero sollte da was tun. AVL-Bäume gibt es schon seit
min. 20 Jahren. Und für etliche Anwendungen ist ein AVL-Baum optimal.
(Andere Bäume gibt es ja auch nicht.)
Ich wollte vor einem Jahr meinen AVL-Baum zum generischen machen.
Das scheiterte daran, dass es nicht möglich war, einen Pointer
PNodeRec<T> = ^TNodeRec<T>; // <<= Compiler error
TNodeRec<T> = record
Data: T;
Link array [0..1] of PNodeRec<T>;
end;
Das ist nicht schön.
Du könntest statt "PNodeRec<T>" einfach einen Pointer nehmen und
bei Bedarf casten. Sehr unschön aber eine Möglichkeit.
Post by Arno Garrels
Also müsste man TNodeRec<T> als Klasse deklarieren, das wäre aber
langsamer, habe ich deshalb bisher nicht gemacht.
Warum ist das langsamer? Auch die Records musst du doch
dynamisch erzeugen - oder nicht?
Post by Arno Garrels
TNodeRec<T> = record
PNodeRec: ^TNodeRec<T>;
end;
Das wundert mich nicht. Hier ist die Definition ja nachher.
"TNodeRec<T>" gibt es in der zweiten Zeile ja schon.
Dass oben "TNodeRec<T>" vor der Definion benutzt wird ist
schon ohne Generics nicht naheliegend (und trotzdem wichtig)


Matthias
Arno Garrels
2013-03-27 18:15:05 UTC
Permalink
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
Embarcadero sollte da was tun. AVL-Bäume gibt es schon seit
min. 20 Jahren. Und für etliche Anwendungen ist ein AVL-Baum
optimal. (Andere Bäume gibt es ja auch nicht.)
Ich wollte vor einem Jahr meinen AVL-Baum zum generischen machen.
Das scheiterte daran, dass es nicht möglich war, einen Pointer
PNodeRec<T> = ^TNodeRec<T>; // <<= Compiler error
TNodeRec<T> = record
Data: T;
Link array [0..1] of PNodeRec<T>;
end;
Das ist nicht schön.
Du könntest statt "PNodeRec<T>" einfach einen Pointer nehmen und
bei Bedarf casten. Sehr unschön aber eine Möglichkeit.
Ja, das könnte funktionieren.
Post by Matthias Frey
Post by Arno Garrels
Also müsste man TNodeRec<T> als Klasse deklarieren, das wäre aber
langsamer, habe ich deshalb bisher nicht gemacht.
Warum ist das langsamer?
Klassen-Overhead.
Post by Matthias Frey
Auch die Records musst du doch
dynamisch erzeugen - oder nicht?
Klar, hab's damals aber verglichen. Die Nodes als Klasse und als Record.
Record war (deutlich) schneller gewesen (kann mich aber nicht mehr
daran erinnern, wie viel schneller genau).
Post by Matthias Frey
Post by Arno Garrels
TNodeRec<T> = record
PNodeRec: ^TNodeRec<T>;
end;
Das wundert mich nicht. Hier ist die Definition ja nachher.
"TNodeRec<T>" gibt es in der zweiten Zeile ja schon.
Dass oben "TNodeRec<T>" vor der Definion benutzt wird ist
schon ohne Generics nicht naheliegend (und trotzdem wichtig)
Ich denke es ist ein Bug, dass man keinen Pointer auf ein
generisches Record deklarieren kann, jemand anderer Meinung?
--
Arno
Arno Garrels
2013-03-23 11:14:21 UTC
Permalink
Post by Matthias Frey
Ich habe noch eine alten Implementation einer sortierten Liste
ohne Generic (TStSortedCollection) in Verwendung und möchte die
nun ablösen.
Kann man doch einfach von TList<T> ableiten, so ähnlich wie unten,
bzw. ähnlich wie in Classes.TStringList.
Wenn's ausschließlich um Geschwindigkeit beim Einfügen, Löschen und
Suchen geht, ist TDictionary<T> eine gute Wahl. Auch AVL-Bäume sind
schneller beim Einfügen, Löschen und Suchen als eine sortierte Liste,
jedoch viel langsamer beim Iterieren.
Möchte man z.B. nur eine Liste sortiert ausgeben ist die Methode Sort
sicher schneller als das sortierte Einfügen von tausenden Einträgen in
eine sortierte Liste.

TSortedList<T> = class(TList<T>)
private
FDuplicates: TDuplicates;
public
function Add(const Value: T): Integer;
function IndexOf(const Value: T): Integer;
function Contains(const Value: T): Boolean;
procedure Insert(Index: Integer; const Value: T);
property Duplicates: TDuplicates read FDuplicates write FDuplicates;
end;

{ TSortedList<T> }

function TSortedList<T>.Add(const Value: T): Integer;
begin
if BinarySearch(Value, Result) then
begin
case FDuplicates of
dupIgnore: Exit;
dupError: Error(@SDuplicateItem, 0);
end;
end;
inherited Insert(Result, Value);
end;

function TSortedList<T>.IndexOf(const Value: T): Integer;
begin
if not BinarySearch(Value, Result) then
Result := -1;
end;

function TSortedList<T>.Contains(const Value: T): Boolean;
begin
Result := IndexOf(Value) >= 0;
end;

procedure TSortedList<T>.Insert(Index: Integer; const Value: T);
begin
Error(@SSortedListError, 0);
end;
...
weitere Methoden ausschalten
--
Arno
Arno Garrels
2013-03-29 18:49:14 UTC
Permalink
Post by Matthias Frey
Weiß oder hat jemand was?
Jetzt hab ich was:
http://delphi.duodata.de/archiv/uAvlTreeT.pas

Frische Ware von heute :)
Bugreports und Verbesserungsvorschläge bitte in diese
Gruppe posten.
--
Arno
Matthias Frey
2013-04-11 08:46:34 UTC
Permalink
Post by Arno Garrels
Post by Matthias Frey
Weiß oder hat jemand was?
http://delphi.duodata.de/archiv/uAvlTreeT.pas
Frische Ware von heute :)
Grüne Bananen? :-D
SCNR
Post by Arno Garrels
Bugreports und Verbesserungsvorschläge bitte in diese
Gruppe posten.
Du willst wirklich? ;-)
Also:

"array [0..1] of PAvlNode"
warum statt 0..1 nicht besser "left..right" oder so ähnlich?

strict private und strict protected

Braucht man wirklich einen IComparer und IEqualityComparer?

Anleitung und/oder Beispiele?

unit-test?


Am Schluß noch ein fettes Danke. Leider bin ich noch nicht
dazu gekommen das auszuprobieren.

Matthias
Arno Garrels
2013-04-11 15:48:40 UTC
Permalink
Post by Matthias Frey
Post by Arno Garrels
Bugreports und Verbesserungsvorschläge bitte in diese
Gruppe posten.
Du willst wirklich? ;-)
Ostern wollte ich wirklich, jetzt ist die Zeit leider etwas knapp :(
Post by Matthias Frey
"array [0..1] of PAvlNode"
warum statt 0..1 nicht besser "left..right" oder so ähnlich?
strict private und strict protected
Hmm, das ist nicht wirklich wichtig, aber du kannst mir gerne
deine Version schicken.
Post by Matthias Frey
Braucht man wirklich einen IComparer und IEqualityComparer?
Der Baum benötigt ausschließlich einen Gleichheitsvergleicher
und einen LinksKleinerAlsRechtsVergleicher. Dies ist ein
Schmankerl der nicht generischen Klasse, welches etwas Performance
bringt. Da ich aber nicht die Zeit hatte/habe so einen generischen
LinksKleinerAlsRechtsVergleicher zu schreiben, benutzt die aktuelle
Version für diesen Zweck den stino IComparer, was leider etwas
Performance kostet :(
Function TDDAvlTree<T>.CmpLeftSmallerThanRight(Left, Right: T): Boolean;
kann aber ggf. überschrieben werden.

Wie zuvor schon angedeutet ist TDictionary z.B. mit einem Integer oder
TObject gut doppelt so schnell:

TDictionary<Integer, Integer> add 200000 entries 63 ms
TDictionary<Integer, Integer> search 200000 and then clear 200000 entries 31ms

TDDAvlTree<integer> add 200000 entries 156ms
TDDAvlTree<integer> search 200000 and then clear 200000 entries 109 ms

Nur zum Spaß:
TSortedList<integer> add 200000 entries 4961 ms
TSortedList<integer> search 200000 and then clear 200000 entries 4883 ms
Die vielen **Moves** sind hier tödlich, bzw. das Problem.

Alle drei verwenden die exakt selben, **zufällig** erzeugten Daten.
Post by Matthias Frey
Anleitung und/oder Beispiele?
Beispiele hab ich, aber die sind "quick and dirty".
Post by Matthias Frey
unit-test?
Wat is denn dette? <g>
--
Arno
Matthias Frey
2013-04-11 18:47:38 UTC
Permalink
Post by Arno Garrels
Post by Matthias Frey
Braucht man wirklich einen IComparer und IEqualityComparer?
Der Baum benötigt ausschließlich einen Gleichheitsvergleicher
und einen LinksKleinerAlsRechtsVergleicher. Dies ist ein
Schmankerl der nicht generischen Klasse, welches etwas Performance
bringt. Da ich aber nicht die Zeit hatte/habe so einen generischen
LinksKleinerAlsRechtsVergleicher zu schreiben, benutzt die aktuelle
Version für diesen Zweck den stino IComparer, was leider etwas
Performance kostet :(
Function TDDAvlTree<T>.CmpLeftSmallerThanRight(Left, Right: T): Boolean;
kann aber ggf. überschrieben werden.
Wäre es nicht einfacher beim Create eine anonyme Methode zu übergeben?
Post by Arno Garrels
Wie zuvor schon angedeutet ist TDictionary z.B. mit einem Integer oder
Vorsicht - nicht Äpfel mit Birnen vergleichen. Es kommt immer drauf
an was man macht.
Post by Arno Garrels
TDictionary<Integer, Integer> add 200000 entries 63 ms
TDictionary<Integer, Integer> search 200000 and then clear 200000 entries 31ms
TDictionary<Integer, Integer> traverse sorted through 200000 entires ??ms
Post by Arno Garrels
TDDAvlTree<integer> add 200000 entries 156ms
TDDAvlTree<integer> search 200000 and then clear 200000 entries 109 ms
TDDAvlTree<integer> traverse sorted through 200000 entires ??ms
Post by Arno Garrels
Post by Matthias Frey
unit-test?
Wat is denn dette? <g>
Das was ich schreiben müsste, wenn ich dein Zeug bei uns in der Firma
benutzen wollte ;-)

Matthias
Arno Garrels
2013-04-12 05:16:17 UTC
Permalink
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
Braucht man wirklich einen IComparer und IEqualityComparer?
Der Baum benötigt ausschließlich einen Gleichheitsvergleicher
und einen LinksKleinerAlsRechtsVergleicher. Dies ist ein
Schmankerl der nicht generischen Klasse, welches etwas Performance
bringt. Da ich aber nicht die Zeit hatte/habe so einen generischen
LinksKleinerAlsRechtsVergleicher zu schreiben, benutzt die aktuelle
Version für diesen Zweck den stino IComparer, was leider etwas
Performance kostet :(
Function TDDAvlTree<T>.CmpLeftSmallerThanRight(Left, Right: T): Boolean;
kann aber ggf. überschrieben werden.
Wäre es nicht einfacher beim Create eine anonyme Methode zu übergeben?
Das ginge natürlich auch, einfacher ist es nicht, denn für viele
Standardtypen funktionieren ja die eingebauten Default-Comparer.
Post by Matthias Frey
Post by Arno Garrels
Wie zuvor schon angedeutet ist TDictionary z.B. mit einem Integer
Vorsicht - nicht Äpfel mit Birnen vergleichen. Es kommt immer drauf
an was man macht.
Das ist richtig.
Post by Matthias Frey
Post by Arno Garrels
TDictionary<Integer, Integer> add 200000 entries 63 ms
TDictionary<Integer, Integer> search 200000 and then clear 200000 entries 31ms
TDictionary<Integer, Integer> traverse sorted through 200000 entires ??ms
Dann müsste man aber erst die Einträge sortieren, TDictionary ist dafür
nicht geeignet.
Post by Matthias Frey
Post by Arno Garrels
TDDAvlTree<integer> add 200000 entries 156ms
TDDAvlTree<integer> search 200000 and then clear 200000 entries 109 ms
TDDAvlTree<integer> traverse sorted through 200000 entires ??ms
16 ms
Ist natürlich viel langsamer, als über eine (sortierte) Liste/Array zu
iterieren.
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
unit-test?
Wat is denn dette? <g>
Das was ich schreiben müsste, wenn ich dein Zeug bei uns in der Firma
benutzen wollte ;-)
Und was würdest du damit testen wollen?
--
Arno
Matthias Frey
2013-04-12 15:34:17 UTC
Permalink
Post by Arno Garrels
Post by Matthias Frey
Wäre es nicht einfacher beim Create eine anonyme Methode zu übergeben?
Das ginge natürlich auch, einfacher ist es nicht, denn für viele
Standardtypen funktionieren ja die eingebauten Default-Comparer.
Dann natürlich nicht. Man könnte noch eine overload machen.
Mit den Compareren ist es mehr Delphi style
Post by Arno Garrels
Post by Matthias Frey
Post by Arno Garrels
TDictionary<Integer, Integer> add 200000 entries 63 ms
TDictionary<Integer, Integer> search 200000 and then clear 200000 entries 31ms
TDictionary<Integer, Integer> traverse sorted through 200000 entires ??ms
Dann müsste man aber erst die Einträge sortieren, TDictionary ist dafür
nicht geeignet.
Eben. Deshalb wollte ich auch eine Liste die sortiert ist und da
fand ich den AVL-Baum naheliegend.
In einem Fall wird der Inhalt des Dictionary in ein Array abgefüllt
und dieses dann sortiert.
Post by Arno Garrels
Post by Matthias Frey
Post by Arno Garrels
TDDAvlTree<integer> add 200000 entries 156ms
TDDAvlTree<integer> search 200000 and then clear 200000 entries 109 ms
TDDAvlTree<integer> traverse sorted through 200000 entires ??ms
16 ms
Finde ich top.
Post by Arno Garrels
Ist natürlich viel langsamer, als über eine (sortierte) Liste/Array zu
iterieren.
Sicher? Also "viel" langsamer würde ich jetzt nicht gerade erwarten.
Post by Arno Garrels
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
unit-test?
Wat is denn dette? <g>
Das was ich schreiben müsste, wenn ich dein Zeug bei uns in der Firma
benutzen wollte ;-)
Und was würdest du damit testen wollen?
Ob das Ding tut was wir erwarten.
Ob das Ding nach einem Update - das ein übereifriger Kollege einfach
so ohne Grund eingepielt hat - immer noch funktioniert.
Ob das Ding immer noch funktioniert wie erwartet, wenn der Matthias
meint etwas dran verbesern zu können. ;-)

Matthias
Arno Garrels
2013-04-14 14:15:58 UTC
Permalink
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
Wäre es nicht einfacher beim Create eine anonyme Methode zu
übergeben?
Das ginge natürlich auch, einfacher ist es nicht, denn für viele
Standardtypen funktionieren ja die eingebauten Default-Comparer.
Dann natürlich nicht. Man könnte noch eine overload machen.
Mit den Compareren ist es mehr Delphi style
M.E. entweder anonyme Methoden oder IComparer.
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
Post by Arno Garrels
Post by Matthias Frey
unit-test?
Wat is denn dette? <g>
Das was ich schreiben müsste, wenn ich dein Zeug bei uns in der
Firma benutzen wollte ;-)
Und was würdest du damit testen wollen?
Ob das Ding tut was wir erwarten.
Ob das Ding nach einem Update - das ein übereifriger Kollege einfach
so ohne Grund eingepielt hat - immer noch funktioniert.
Ob das Ding immer noch funktioniert wie erwartet, wenn der Matthias
meint etwas dran verbesern zu können. ;-)
ok, das kann nützlich sein.
--
Arno
Loading...