Forum: Programmieren allgemein
by himitsu,
10. Jan 2017
Jain.
Bei der Vergrößerung der Liste müssen ab und an mal alle Einträge neu positioniert werden, wenn der interne Speicher die Größe ändert.
Forum: Programmieren allgemein
by himitsu,
10. Jan 2017
Es kommt auf den Verwendungsfall drauf an.
Wenn sich die Liste oft ändert, aber nur selten darauf zugegriffen wird, dann kann die Suche langsamer sein, aber das Hinzufügen/Löschen/Ändern sollte schnell sein,
aber wenn die Liste sich selten ändert und oft gesucht wird, dann natürlich andersrum.
Und dann kann man noch unterscheiden wie die Liste gefüllt wird.
Wird sie einmal schnell gefüllt...
Forum: Programmieren allgemein
by himitsu,
8. Jan 2017
Rein "logisch" nur eine mathematische Rechnung.
V = A - B (gleich 0, kleiner 0, größer 0)
CompareValue
Dann weiß man sofort ob größer, kleiner oder gleich.
Aber aus diesem Grund sind Hash-Listen schneller, da dort je Wert nur ein "Vergleich" nötig ist, während bei Strings ja jedes einzelne Char verglichen werden muß.
Die genaue Anzahl der physischen Vergleiche, im Bytecode (Assembler)...
Forum: Programmieren allgemein
by himitsu,
7. Jan 2017
Wenn deine Liste also Sortiert ist, ergibt es das. :roll:
function TStringList.IndexOf(const S: string): Integer;
begin
if not Find(S, Result) then
Result := -1;
end;
Forum: Programmieren allgemein
by himitsu,
7. Jan 2017
Wurde schon erwähnt.
TDictionary ist eine sortierte Hash-Liste mit binärer Suche.
Forum: Programmieren allgemein
by himitsu,
7. Jan 2017
Darum auch Binär (Zwei), weil man dort immer alles halbiert.
Die maximal nötigen Vergleiche, bis man einen Eintrag gefunden hat, sind auch "zufällig" immer Zweiterpotenzen.
...
65 bis 128 = maximal 7 Vergleiche
129 bis 256 Werte = maximal 8 Vergleiche
257 bis 512 Werte = maximal 9 Vergleiche
513 bis 1024 Werte = maximal 10 Vergleiche
...
Forum: Programmieren allgemein
by himitsu,
7. Jan 2017
Das Tempo ist da logarithmisch und nicht linear.
* jeden Eintrag durchsuchen, also im Durchschnitt 50% aller Einträge, bis man was findet.
* die binäre Suche ist für Sortiertes optimiert, da man beim Vergleich sofort weiß, ob man was getroffen hat und wenn nicht, ob es vor oder hinter dem Eintrag zu finden ist
bei 1000 Einträgem
* linear = durchschnittlich 500 Vergleiche
* binär =...
Forum: Programmieren allgemein
by himitsu,
7. Jan 2017
IndexOf und Find sollte doch gleich schnell sein?
Und ja, sortieren hilft (Sorted=True), denn dann wird eine andere Suchmethode verwendet.
> TArray.BinarySearch
Alternativ eine HashList.
TDictionary?