Suche in Sortierter Liste

F34r0fTh3D4rk · Verfasst: Do 25.01.07 20:53

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 · Verfasst: 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.

_________________
We are, we were and will not be.

F34r0fTh3D4rk · Verfasst: Do 25.01.07 21:06

aso, in der mitte und dann von den beiden geteilten hälften wieder die mitte usw ?

mfg

Gausi · Verfasst: Do 25.01.07 21:12

Richtig. Am einfachsten geht das rekursiv, wenn man die Funktion in etwa so aufbaut

markieren

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;

// ""else""

  mitte := (links + rechts) /2;
  
  result := binaersuche(myarray, linkeGrenze, mitte-1)
  //oder, je nachdem
  result := binaersuche(myarray, mitte+1, rechte Grenze)

end;

_________________
We are, we were and will not be.

F34r0fTh3D4rk · Verfasst: Do 25.01.07 21:43

ich hab das jetzt so aufgebaut, aber das ganze klappt noch net:

markieren

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;

markieren

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 · Verfasst: 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:

markieren

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;

_________________
We are, we were and will not be.

F34r0fTh3D4rk · Verfasst: 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 · Verfasst: 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:

markieren

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:

markieren

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

Ehemaliges Mitglied Erhaltene Danke: 1

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 · Verfasst: 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 · Beiträge: 275 WinXP BDS 2006

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

markieren

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.

_________________
erare humanum est

F34r0fTh3D4rk · Verfasst: Sa 03.02.07 19:16

danke, genau die funktion die ich brauchte :lol:

so klappt das:

markieren

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

Ehemaliges Mitglied Erhaltene Danke: 1

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 · Beiträge: 275 WinXP BDS 2006

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

_________________
erare humanum est

Ehemaliges Mitglied Erhaltene Danke: 1

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 · Verfasst: Sa 03.02.07 22:33

das ganze ist case sensitive, gibt es noch eine methode die das außer acht lässt ?

mfg

alzaimar · Verfasst: Sa 03.02.07 22:47

Du willst eine große Wortliste aufbauen, in der man schnell suchen kann?
THashStringList reich bis 20000-30000 Einträge und ist dann wirklich sehr schnell.

Bei Millionen von Einträgen hilft eine richtige Hashmap oder gleich ein DAWG.

Hashmap: www.delphipraxis.net...ht=tstringdictionary
DAWG: www.delphipraxis.net...wg+dawg&start=15

Der DAWG von Hagen Redmann ist für Dich eigentlich genau das Richtige, denn er verwurstet die Wörter automatisch.

U

_________________
Na denn, dann. Bis dann, denn.

wulfskin · Verfasst: 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!

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.

alzaimar · Verfasst: So 04.02.07 16:23

Die Methode 'IndexOf' einer TStringList sucht binär, wenn die Eigenschaft 'Sorted' auf 'True' eingestellt ist, sonst sequentiell.

_________________
Na denn, dann. Bis dann, denn.

wulfskin · Verfasst: 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.

_________________
Manche antworten um ihren Beitragszähler zu erhöhen, andere um zu Helfen.

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme