Autor |
Beitrag |
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Do 10.02.05 15:12
Hallo,
ich suche nach einer Möglichkeit in einer Liste (TList) mit ca. 2000 Elemente eine 4-stellige Zeichenkette schnell zu finden. Die Liste enthält Elemente mit folgendem Muster: Delphi-Quelltext 1: 2: 3:
| Item = record Id: String[4]; Data: Pointer; | Die Liste ist nach Id alphabetisch sortiert.
Zur Zeit suche ich das Item durch eine einfache Schleife, wobei dass bei zu vielen Zugriffen einfach zu lange dauert. Welche Möglichkeiten gibt es, die Suche zu verschnellern?
Gruß Hape! Moderiert von Gausi: Topic aus CLX / Delphi Language (Object-Pascal) verschoben am Fr 11.02.2005 um 15:02
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
jasocul
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Do 10.02.05 15:25
Wenn du nach der Id suchst, würde ich zunächst mit einem Halbierungsverfahren rangehen.
Andere Möglichkeit wäre eine zweite List zu führen, die die 26 Buchstaben des Alphabets enthält mit einem Index für deine TList.
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Do 10.02.05 19:04
jasocul hat folgendes geschrieben: | Wenn du nach der Id suchst, würde ich zunächst mit einem Halbierungsverfahren rangehen.
Andere Möglichkeit wäre eine zweite List zu führen, die die 26 Buchstaben des Alphabets enthält mit einem Index für deine TList. |
Danke für die Antwort,
leider musst du mir das noch etwas genauer erklären: - Wie funktioniert das Halbierungsverfahren?
- Wie meinst du das mit dem Index
Danke dir!
Hape
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
Elite
Ehemaliges Mitglied
Erhaltene Danke: 1
|
Verfasst: Do 10.02.05 19:20
Er meint ne Intervallschachtelung. Sagt dir das etwas
|
|
tommie-lie
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Do 10.02.05 19:21
wulfskin hat folgendes geschrieben: | Wie funktioniert das Halbierungsverfahren? |
Du sagtest, dein Index ist alphabetisch sortiert. Also gehst du zum Element in der Mitte, und guckst, ob der String "größer" oder "kleiner" ist. Ist er größer, liegt das gesuchte Objekt irdendwo weiter vorne, also überprüfst du das Objekt in der Mitte der Mitte.
Beispiel:
Liste:
a b c d e f g h i jDu suchst nach g, das mittlere Element wäre e. g ist aber größer als e, also nimmst du die Mitte der Hälfte, wäre h. g ist aber kleiner als h, also nimmst du die Mitte des verbleibenden Restes, wäre f. g ist größer als f, also nimmst du wieder die Mitte, wäre g. g ist g, also hast du das Objekt gefunden. Du halbierst also immer das Intervall, in dem du suchst, und schränkst es so auf ein Intervall der Größe 1 ein, welches das gesuchte Element enthält.
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
jasocul
Beiträge: 6388
Erhaltene Danke: 146
Windows 7 + Windows 10
Sydney Prof + CE
|
Verfasst: Do 10.02.05 19:35
Danke tommie-lie
Sollte wulfskin noch fragen haben, kann er uns das ja mitteilen.
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Do 10.02.05 19:51
Hallo,
ist klar! Hätte man auch selber draufkommen können. Ich bastel mir mal was zusammen und schau ob es dadurch viel schneller geht!
Gruß Hape!
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
UC-Chewie
Beiträge: 531
WinXP
D5 Ent
|
Verfasst: Do 10.02.05 20:40
Zur Info: Das ganze nennt man binäre Suche und die Anzahl der Zugriffe beträgt max. floor(ld(n)), wobei floor() aufrundet und ld() der Logarithmus zur Basis 2 ist.
Bei 2.000 Einträgen brauchst du also maximal 11 Zugriffe.
_________________ Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Fr 11.02.05 14:33
UC-Chewie hat folgendes geschrieben: | Zur Info: Das ganze nennt man binäre Suche und die Anzahl der Zugriffe beträgt max. floor(ld(n)), wobei floor() aufrundet und ld() der Logarithmus zur Basis 2 ist.
Bei 2.000 Einträgen brauchst du also maximal 11 Zugriffe. |
Danke schön,
das geht jetzt wirklich richtig schnell! Für alle die es interessiert, hier mein Quelltext: Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30:
| function TW3gItemList.GetItemById(const AId: TItemId): TW3gItem; function FindInList(const AStart, AEnd: Integer; const AId: TItemId): TW3gItem; var I: Integer; begin Result := nil; if CompareText(Items[AStart].Id, AId) = 0 then Result := Items[AStart] else if CompareText(Items[AEnd].Id, AId) = 0 then Result := Items[AEnd] else begin if (AStart <> AEnd) and ((AEnd - AStart) > 1) then begin I := (AStart + AEnd) div 2; if AId > Items[I].Id then Result := FindInList(I, AEnd, AId) else Result := FindInList(AStart, I, AId); end else ; end; end; begin Result := nil; if Count > 0 then Result := FindInList(0, Count - 1, AId); end; | Jetzt muss ich nur noch schauen, wie ich ein Item schnell einfügen kann ohne die Liste jedesmal neu sortieren zu müssen.
Gruß Hape!
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
Gausi
Beiträge: 8538
Erhaltene Danke: 475
Windows 7, Windows 10
D7 PE, Delphi XE3 Prof, Delphi 10.3 CE
|
Verfasst: Fr 11.02.05 16:01
Das geht auch einfach: Such das Item, was du einfügen willst, in deiner Liste, und merke dir die Position, an der die Suche (erfolglos) endet. Das ist dann die Einfügeposition (oder 1 davor oder dahinter).
Edit: Aber das gehört ja nicht hierhin *verschieb*
_________________ We are, we were and will not be.
|
|
Lossy eX
Beiträge: 1048
Erhaltene Danke: 4
|
Verfasst: Fr 11.02.05 17:32
Hi Wulfskin. Habe deine Frage erst jetzt gesehen. Und ich habe die ultimative Lösung für dich.
Ich sage nur Hash. Dort werden die Einträge nach einem bestimmten Verfahren in einem Array verteilt und du kannst so wahnsinnig schnell auf die entsprechenden Einträge zugreifen. Es wird intern nur eine Zahl anhand des Namens errechnen. Simples addieren und bits rotieren. Zu einem Namen kannst du einen Pointer ablegen. Das Einfügen geht auch wahnsinnig flott, da die Daten nun mal nicht sortiert werden müssen und auch keine Unmengen von Einträgen verschoben werden müssen. Kann auch problemlos Mengen von 100.000 Einträgen und mehr ab.
Hier kommst du zu meiner Hashklasse
_________________ Nur die Menschheit ist arrogant genug, um zu glauben sie sei die einzige intelligente Lebensform im All. Wo nicht mal das nachhaltig bewiesen wurde.
|
|
UC-Chewie
Beiträge: 531
WinXP
D5 Ent
|
Verfasst: Fr 11.02.05 19:24
Hashes sind u.U. gut geeignet, in diesem Fall seh ich aber keinen Grund, wieso man einen benutzen soll. Die Daten sind ja sowieso schon sortiert und werden anscheinend nur nach dieser Sortierung verwendet, also bietet sich die binäre Suche an, die im Übrigen oft schneller als jedes Hashverfahren ist (aufgrund der Kollisionen, die dort auftreten).
_________________ Egal wie dumm man selbst ist, es gibt immer andere, die noch dümmer sind
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Fr 11.02.05 19:35
Lossy eX hat folgendes geschrieben: | Hi Wulfskin. Habe deine Frage erst jetzt gesehen. Und ich habe die ultimative Lösung für dich. |
Danke,
Hash kenn ich, aber ist für mein Problem ein bisschen zu aufwenidig (und wohl auch nicht schneller), da ich maximal 2000 Einträge habe.
Trotzdem danke,
Hape!
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Fr 11.02.05 20:49
So hier der komplette Quelltext zum Einfügen und Finden: 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40:
| function TW3gItemList.BinarySearch(const AId: TItemId; var AFound: Boolean): Integer; function FindInList(const AStart, AEnd: Integer): Integer; var I: Integer; begin if CompareText(Items[AStart].Id, AId) = 0 then begin Result := AStart; AFound := True; end else if CompareText(Items[AEnd].Id, AId) = 0 then begin Result := AEnd; AFound := True; end else begin if (AEnd - AStart) > 1 then begin I := (AStart + AEnd) div 2; if CompareText(Items[I].Id, AId) = 0 then begin Result := I; AFound := True; end else if AId > Items[I].Id then Result := FindInList(I, AEnd) else Result := FindInList(AStart, I); end else Result := AStart; end; end; begin Result := -1; AFound := False; if Count > 0 then Result := FindInList(0, Count - 1); end; | Danke an alle Helfer. Irgend etwas, was man noch optimieren könnte?
Gruß Hape!
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
alexanm
Hält's aus hier
Beiträge: 1
|
Verfasst: Sa 12.02.05 06:06
Hallo wulfskin,
also wenn ich mir die Struktur Deiner Daten ansehe so würde ich eine TStringList nehmen. Diese kann den String (der Schlüssel) und die Daten (als Object) aufnehmen.
Weiters hat die StringList ein paar nette Properties:
- Sorted: Wenn true dann werden die Strings sortiert eingefügt und es wird beim Zugriff binär gesucht.
- CaseSensitive: Wenn false dann wird zwischen Groß-/Kleinschreibung nicht unterschieden.
Weiters wäre es echt interessant wie schnell die Stringliste im Gegensatz zu Deiner aktuellen Lösung ist.
cu
Maxx
|
|
tommie-lie
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Sa 12.02.05 12:28
alexanm hat folgendes geschrieben: | also wenn ich mir die Struktur Deiner Daten ansehe so würde ich eine TStringList nehmen. Diese kann den String (der Schlüssel) und die Daten (als Object) aufnehmen. |
Mag zwar komfortabel sein, aber die geht auch nur die einträge der Reihe nach durch und guckt, ob's passt, womit er wieder am Anfang stehen würde.
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Sa 12.02.05 12:39
Hallo,
danke für die Tipps, aber mein record ist hier nur sehr vereinfacht dargestellt und sieht in Wirklichkeit etwas komplexer aus, so dass eine StringListe für mich nicht in Frage kommt.
@Tommie-Lie: Ich habe die Funktion IndexOf der StringListe nur kurz überflogen, aber ich glaube da wird auch binär gesucht.
Gruß Hape!
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
tommie-lie
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Sa 12.02.05 12:55
wulfskin hat folgendes geschrieben: | @Tommie-Lie: Ich habe die Funktion IndexOf der StringListe nur kurz überflogen, aber ich glaube da wird auch binär gesucht. |
Oops, stimmt, ich habe an eine unsortierte Liste gedacht. Wenn nicht sortiert ist, wird IndexOf() von TStrings aufgerufen, und der geht von 0 bis Count-1 alle Elemente durch, überprüft, ob die Strings übereinstimmen und gibt das gefundene Objekt zurück.
Bei sortierten Listen wird auch binär gesucht.
wulskin hat folgendes geschrieben: | mein record ist hier nur sehr vereinfacht dargestellt und sieht in Wirklichkeit etwas komplexer aus, so dass eine StringListe für mich nicht in Frage kommt. |
Das ist eigentlich gar nicht wichtig. Durch das Objekt eines Stringlisteneintrages hast du die Möglichkeit, einen Pointer zu speichern. Deinen Record, egal wie kompliziert er ist, kannst du auch darin speichern, indem du einen Pointer auf das Record nimmst und ihn in ein TObject castest. Beim lesenden Zugriff musst du halt nur den Pointer wieder in einen Pointer auf dein Record casten und dereferenzieren.
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
wulfskin
Beiträge: 1349
Erhaltene Danke: 1
Win XP
D5 Pers (SSL), D2005 Pro, C, C#
|
Verfasst: Sa 12.02.05 15:00
Hallo Tommie-Lie, hallo Alex,
eigentlich habt ihr Recht, ich könnte wirklich eine StringListe benutzen. Naja, jetzt hab ich es auch so geschafft. Ich werd mal schauen was schneller ist und mich für das bessere entscheiden!
(Obwohl der Thread als abgeschlossen markiert ist, geht er doch immer weiter .)
Danke für eure Hilfe!
Hape
_________________ Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.
|
|
tommie-lie
Beiträge: 4373
Ubuntu 7.10 "Gutsy Gibbon"
|
Verfasst: Sa 12.02.05 15:03
wulfskin hat folgendes geschrieben: | eigentlich habt ihr Recht, ich könnte wirklich eine StringListe benutzen. Naja, jetzt hab ich es auch so geschafft. Ich werd mal schauen was schneller ist und mich für das bessere entscheiden! |
Wenn du's richtig implementiert hast, dürfte sich deine Implementierung und TStrinList nicht viel nehmen ;-9
wulskin hat folgendes geschrieben: | (Obwohl der Thread als abgeschlossen markiert ist, geht er doch immer weiter .) |
Nur weil die Frage beantwortet wurde, heißt es doch noch lange nicht, daß es keine weiteren Möglichkeiten zur Problemlösung mehr gibt
_________________ Your computer is designed to become slower and more unreliable over time, so you have to upgrade. But if you'd like some false hope, I can tell you how to defragment your disk. - Dilbert
|
|
|