Entwickler-Ecke
Algorithmen, Optimierung und Assembler - Suche in Sortierter Liste
F34r0fTh3D4rk - Do 25.01.07 20:53
Titel: Suche in Sortierter Liste
hi, angenommen, ich habe eine Liste mit Namen / Wörtern, die vorsortiert ist, wie kann ich von dieser Sortierung bei der Suche nach einem bestimmten Wort profitieren ? Ich meine, da kann ich mir doch sicherlich einen enormen Geschwindigkeitsvorteil verschaffen oder nicht ?
mfg
Gausi - Do 25.01.07 21:04
Jup. Mach dich mal über Binäre Suche schlau. Manchmal nennt man das auch Halbierungsverfahren. Funktioniert im groben so:
Guck dir das Element in der Mitte an und vergleiche es mit dem Suchbegriff. Ist es kleiner, suche links weiter, ansonsten rechts. Ist "linke Grenze = rechte Grenze" kann man die Suche abbrechen. Findet man das Wort, kann man natürlich auch abbrechen ;-).
Somit braucht man bei einer Suche nach einem Element in einer Liste mit 1024 Elementen maximal 10 Vergleiche.
F34r0fTh3D4rk - Do 25.01.07 21:06
aso, in der mitte und dann von den beiden geteilten hälften wieder die mitte usw ?
mfg
Gausi - Do 25.01.07 21:12
Richtig. Am einfachsten geht das rekursiv, wenn man die Funktion in etwa so aufbaut
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19:
| function binaersuche(MyArray, links, rechts, Suchbegriff); begin If links > rechts then result := -1;
if links = rechts then if MyArray(links) = Suchbegriff then result := links else result := -1;
mitte := (links + rechts) /2; result := binaersuche(myarray, linkeGrenze, mitte-1) result := binaersuche(myarray, mitte+1, rechte Grenze)
end; |
F34r0fTh3D4rk - Do 25.01.07 21:43
ich hab das jetzt so aufgebaut, aber das ganze klappt noch net:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16:
| function BS(astrl: TStringlist; aWord: string; iLo, iHi: integer; var position: integer): boolean; var apos: integer; begin result := false; apos := ((iLo + iHi) div 2); position := apos; if (lowercase(astrl[apos]) < lowercase(aWord)) then inc(iLo); if (lowercase(astrl[apos]) > lowercase(aWord)) then dec(iHi); if (lowercase(astrl[apos]) = lowercase(aWord)) then result := true; if ((result = false) and (iLo <= iHi)) then BS(astrl, aWord, iLo, iHi, position); end; |
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| procedure AddWordToList(aWord: string; var astrl: TStringlist); var position: integer; begin position := 0; if astrl.Count = 0 then begin astrl.add(aWord); exit; end; if BS(astrl, aWord, 0, astrl.Count - 1, position) = false then astrl.Insert(position, aWord); end; |
ich möchte nämlich schauen, ob das wort in der liste ist, falls net, soll es gleich an die richtige stelle eingefügt werden, damit ich nimmer sortieren muss, leider sind trotzdem einige wörter doppelt drinne :(
mfg
Gausi - Do 25.01.07 21:57
Schau dir mal mein Funktionsprinzip an. Es ist recht sinnvoll, als Rückgabewert die Position des Items zu liefern (-1 wenns nicht drin ist).
Und: du hast keine Binärsuche, da du den Suchbereich immer nur um 1 einschränkst (durch das dec/inc iLo/iHi). Man muss dabei aber eine Fallunterscheidung machen, und den rekursiven Aufruf von "mitte+1 bis rechts" oder von "links bis mitte-1" machen, je nachdem ob der Vergelcih größer oder kleiner ergeben hat.
Edit: Hier mal ein Code, der in einer Objectlist sucht:
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:
| function binaersuche(Liste: TObjectlist;filename:WideString; l,r:integer):integer; var m:integer; c:integer; begin if r<l then begin result:=-1; end else begin m:=(l+r) DIV 2; c := WideCompareText(filename,(Liste[m] as TAudioFile).Pfad); if l=r then begin if c=0 then result:=l else result:=-1; end else begin if c=0 then result:=m else if c > 0 then result := binaersuche(Liste,filename,m+1,r) else result := binaersuche(Liste,filename,l,m-1); end; end; end; |
F34r0fTh3D4rk - Do 25.01.07 22:09
ich finde es nur nicht sinnvoll, die position auszugeben und dann die position noch ein zweites mal zu speichern, als result reicht mir dann true oder falls, ich möchte ja gucken ob ein item nicht existiert und es dann an der richtigen stelle einfügen.
F34r0fTh3D4rk - Sa 03.02.07 15:24
hm so richtig funktionieren tut das net, es soll ein wort in eine liste gefügt werden und zwar so, dass es an die stelle kommt, an die es nach alphabethischer sortierung gehört, sodass ich mit einer leeren liste anfange und sich diese dann füllt, aber sofort sortiert ist, ohne dass ich extra quicksort oder so draufjagen muss und kein wort soll doppelt vorkommen:
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: 31: 32: 33: 34: 35: 36: 37: 38:
| function BS(astrl: TStringlist; aWord: String; l, r: integer; var position: integer): boolean; var m: integer; begin if r < l then result := false else begin m := (l + r) div 2; position := m; if l = r then begin if lowercase(astrl[m]) = lowercase(aWord) then result := true else result:= false; end else begin if lowercase(astrl[m]) = lowercase(aWord) then result := true else if lowercase(astrl[m]) > lowercase(aWord) then result := BS(astrl, aWord, m + 1, r, position) else result := BS(astrl, aWord, l, m - 1, position); end; end; end;
procedure AddWordToList(aWord: string; var astrl: TStringlist); var position: integer; begin position := 0; if astrl.Count = 0 then begin astrl.add(aWord); exit; end; if BS(astrl, aWord, 0, astrl.Count - 1, position) = false then astrl.Insert(position, aWord); end; |
momentan lasse ich ihn aus einem satz alle wörter extrahieren, aus
Zitat: |
Hallo, mein Name ist Horst (Schlemmer). [(Die
Redaktion)] Mein Hund hat die Schnauze voll. Hallo,
mein Name ist...
|
wird
Zitat: |
voll
Schnauze
Redaktion
Schlemmer
Name
ist
mein
Hund
ist
Horst
Hallo
hat
Die
Hallo
|
der sinn des textes ist fragwürdig ^^
an den markierten stellen treten auch immer noch redundanzen auf.
so extrahiere ich die wörter:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21:
| procedure ExtractWords(input: TStringlist; var output: TStringlist); function isSep(aChar: Char): Boolean; begin result := aChar in [#0..#32, '.', ',', '?', ':', ';', '(',')', '[', ']', '/', '\']; end; var i, sep: integer; temptext: string; begin i := 1; sep := 1; temptext := ''; for i := 1 to length(input.text) do if isSep(input.text[i]) then begin temptext := copy(input.text, sep, i - sep); if length(temptext) > 0 then AddWordToList(temptext, output); sep := i + 1; end; end; |
mfg und danke schonmal
Delete - Sa 03.02.07 15:49
so mal grundsätzlich, den insertionsort kannst du eigentlich nur bei 'ner liste oder 'n baum gebrauchen, nicht bei 'n array. im ersteren fall, brauchst nur 'n paar pointer umhängen beim array hingegen musst du den halben hauptspeicher umschichten. überdenke mal deinen ansatz oder deine datenstruktur. nur 'n kleiner tipp von mir.
F34r0fTh3D4rk - Sa 03.02.07 18:40
mein ansatz ist, dass ich nichts sortieren muss, und ich habe eine stringliste, ich könnte diese natürlich sortieren, das will ich aber nicht, ich will die liste so füllen, dass ich das eben nicht zu tun brauche.
Robinator - Sa 03.02.07 18:52
Aus der delphil OH
TStringList.Find Method
Locates the index for a string in a sorted list and indicates whether a string with that value already exists in the list.
Class
TStringList
Syntax
Delphi-Quelltext
1:
| function Find(const S: string; var Index: Integer): Boolean; virtual; |
Description
Use Find to obtain the index in a sorted list where the string S should be added. If the string S, or a string that differs from S only in case when CaseSensitive is false, already exists in the list, Find returns true. If the list does not contain a string that matches S, Find returns false. The index where S should go is returned in the Index parameter. The value of Index is zero-based, where the first string has the index 0, the second string has the index 1, and so on.
Note:
Only use Find with sorted lists. For unsorted lists, use the IndexOf method instead.
F34r0fTh3D4rk - Sa 03.02.07 19:16
danke, genau die funktion die ich brauchte :lol:
so klappt das:
Delphi-Quelltext
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| procedure AddWordToList(aWord: string; var astrl: TStringlist); var position: integer; begin position := 0; if astrl.Count = 0 then begin astrl.add(aWord); exit; end; if astrl.Find(aWord, position) = false then astrl.Insert(position, aWord); end; |
delphi ist doch ne tolle sache ;)
mfg
Delete - Sa 03.02.07 19:34
F34r0fTh3D4rk hat folgendes geschrieben: |
mein ansatz ist, dass ich nichts sortieren muss, und ich habe eine stringliste, ich könnte diese natürlich sortieren, das will ich aber nicht, ich will die liste so füllen, dass ich das eben nicht zu tun brauche. |
denke, da täuscht du dich, insertsort, sortieren beim einfügen, ist doch grad das was du vorhast. wenn die anzahl der einträge wenig sind, kannst es auch auf diese weise mit arrays machen, werden es mehr, wirst du ziemliche performance probleme bekommen, um einen eintrag in die liste einzufügen.
aber dies nur als denkanstoss.
Robinator - Sa 03.02.07 19:36
Ihm geht es ja primär ums suchen. Damit die Suche performant ist, ist wahlfreier Zugriff unerlässlich - und den bieten nunmal nur arrays.
gruss, rob
Delete - Sa 03.02.07 19:40
für 'n paar hundert einträge funktionierts so auch einwandfrei. und wenns 'n paar mehr einträge werden, muss er sich halt 'n neuen rechner kaufen :-)
aber ist sein bier :-) . hier im forum liegen jedenfalls genügend threads rum, bei dennen es darum ging, die performanceprobleme aufgrund einer falsch gewählten datenstruktur in den griff zu bekommen. aber wie gesagt, PAL.
F34r0fTh3D4rk - Sa 03.02.07 22:33
das ganze ist case sensitive, gibt es noch eine methode die das außer acht lässt ?
mfg
wulfskin - Sa 03.02.07 23:24
F34r0fTh3D4rk hat folgendes geschrieben: |
das ganze ist case sensitive, gibt es noch eine methode die das außer acht lässt ?
mfg |
Du sagtest doch vorher schon: "Delphi ist eine tolle Sache." Also gibt es dafür (bei der StringListe) auch die passende Eigenschaft, rate mal wie die heisst! Übrigens: Find sucht auch Binär. Ein Blick in den Quelltext lohnt sich also!
Gruß Hape!
alzaimar - So 04.02.07 16:23
Die Methode 'IndexOf' einer TStringList sucht binär, wenn die Eigenschaft 'Sorted' auf 'True' eingestellt ist, sonst sequentiell.
wulfskin - So 04.02.07 16:53
alzaimar hat folgendes geschrieben: |
Die Methode 'IndexOf' einer TStringList sucht binär, wenn die Eigenschaft 'Sorted' auf 'True' eingestellt ist, sonst sequentiell. |
Das mit der Eigenschaft stimmt natürlich, aber IndexOf ruft auch nur intern
Find auf.
alzaimar - So 04.02.07 17:00
wulfskin hat folgendes geschrieben: |
alzaimar hat folgendes geschrieben: | Die Methode 'IndexOf' einer TStringList sucht binär, wenn die Eigenschaft 'Sorted' auf 'True' eingestellt ist, sonst sequentiell. | Das mit der Eigenschaft stimmt natürlich, aber IndexOf ruft auch nur intern Find auf. |
Ich wollte damit nur auf die Möglichkeit der Steuerung des Suchverfahrens hinweisen. 'Find' verwende ich gar nicht.
matze - So 04.02.07 17:21
und das mit den Dubletten kannst du dir auch automatisch erledigen lassen, wenn du
Stringlist.duplicated := dupIgnore; machst.
F34r0fTh3D4rk - So 04.02.07 17:56
wenn ich sorted := true setze, wird dann immer sortiert oder wird mit einem abbruch verfahren getestet, ob die liste sortiert ist ? weil wenn ich das einstelle, sollte ich eigentlich einen performance schub durch die binäre suche erlangen können.
mfg
alzaimar - So 04.02.07 18:00
Fear, nimm Dir meine Links zur Brust und mach es damit. Dann hast Du keine Performanceprobleme mehr.
Sorted := True fügt das neue Wort immer an die richtige Stelle ein=> etwas langsamer beim Einfügen.
wulfskin - So 04.02.07 18:15
alzaimar hat folgendes geschrieben: |
Sorted := True fügt das neue Wort immer an die richtige Stelle ein=> etwas langsamer beim Einfügen. |
Genau, wenn es dir _nur_ um einen schnellen Zugriff geht, dann erstell die Liste mit
Sorted := False;, füg die Elemente ein und setz dann diese Eigenschaft auf wahr.
Danach kannst du dann über
IndexOf die Elemente binär suchen!
Viele Grüße,
Hape
Delete - So 04.02.07 19:13
er hat ja auch noch nix gesagt, wie häufig dass er etwas einfügen will. nur einalig mit etwas pflege dann und wann, oder ständig etwas einfügen... und stelten etwas abfragen. all dies sind fragen, welche zuvor zu beantworten sind, bevor man sich auf 'n algo festlegt. wenn's nur seltene einfügeoperationen sind, so ist die unit und ggf. auch das array (tstringlist) gut geeingnet. werden häufiger daten eingefügt und ist die anzahl hoch, so scheidet das array aus, weil die aktualisierung zu lange benötigt... so hat jeder algo seie vor und nachteile.
Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!