Delphi-PRAXiS
Seite 1 von 2  1 2   

Delphi-PRAXiS (https://www.delphipraxis.net/forum.php)
-   Object-Pascal / Delphi-Language (https://www.delphipraxis.net/32-object-pascal-delphi-language/)
-   -   [Algorithmus] Binäre Suche für Zeichenketten (https://www.delphipraxis.net/114951-%5Balgorithmus%5D-binaere-suche-fuer-zeichenketten.html)

Luckie 3. Jun 2008 12:16


[Algorithmus] Binäre Suche für Zeichenketten
 
Hat jemand von euch eine Idee, wie man eine binäre Suche für Zeichenketten realisieren könnte? Das Problem ist ja, dass man Zeichenketten ja nicht auf größer oder kleiner vergleichen kann - oder doch?

Der.Kaktus 3. Jun 2008 12:27

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Hallo Micha,

schau mal hier-->Binarysearch

Luckie 3. Jun 2008 12:40

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Äh, ja mir ist auch gerade eingefallen dass man die Vregleiochsoperatoren auch auf Strings anwenden kann. Hat sich also erledigt.

Aber irgendwas stimmt noch nicht:
Delphi-Quellcode:
function TBSearch.Search(SortedStrArray: TStrArray; s: String): Integer;
var
  left             : Integer;
  middle           : Integer;
  right            : Integer;
  found            : Boolean;
  index            : Integer;
begin
  found := False;
  index := -1;
  left := 0;
  right := Length(SortedStrArray);

  while (left <= right) and (not Found) do
  begin
    middle := left + ((right - left) div 2);
    if (SortedStrArray[middle] = s) then
    begin
      index := middle;
      Found := True;
    end;
    if (SortedStrArray[middle] > s) then
      right := middle - 1
    else
      left := middle + 1;
  end;

  result := index;
end;
Suche ich nach einer Zeichenkette, die nicht vorkommt, bekomme ich gleich beim ersten Vergleich
Delphi-Quellcode:
if (SortedStrArray[middle] = s) then
eine AccessViolation. Irgendwas stimmt da nicht.

Der.Kaktus 3. Jun 2008 12:56

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
aender mal die Zeile um

Delphi-Quellcode:
 //middle := left + ((right - left) div 2);
 middle := (left + right) div 2;

Luckie 3. Jun 2008 13:04

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Ändert nichts an der AV. middle hat auch einen gültigen Wert. Wie kann ein Vergleich eine ASV auslösen?
Zitat:

---------------------------
Benachrichtigung über Debugger-Exception
---------------------------
Im Projekt Project1.exe ist eine Exception der Klasse EAccessViolation aufgetreten. Meldung: 'Zugriffsverletzung bei Adresse 0040465B in Modul 'Project1.exe'. Lesen von Adresse 00000012'. Prozeß wurde angehalten. Mit Einzelne Anweisung oder Start fortsetzen.
---------------------------
OK Hilfe
---------------------------

marabu 3. Jun 2008 13:09

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Hallo Michael,

nimm dir ein Beispiel an der Methode TStringList.Find() - deren Implementierung ist best practise, da der Rückgabewert für Index bei Misserfolg die Stelle bezeichnet, an der die Einfügung vorzunehmen wäre.

Freundliche Grüße

alzaimar 3. Jun 2008 13:10

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Der Vergleich führt nicht zur Zugriffsverletzung, sondern der Versuch, auf das Element 'middle' zuzugreifen, welches dann vermutlich außerhalb des Bereiches ist. Ändere mal diese Zeilen;
Delphi-Quellcode:
left := 0;
right := Length(SortedStrArray);
in
Delphi-Quellcode:
left := Low (SortedStrArray);
right := High(SortedStrArray);

Luckie 3. Jun 2008 13:20

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Zitat:

Zitat von alzaimar
Delphi-Quellcode:
left := Low (SortedStrArray);
right := High(SortedStrArray);

Danke, das scheint es gewesen zu sein. Aber darüber muss ich noch mal nachdenken. ;)

@marabu: Hm, wäre eine Option, allerdings nutze ich den Rückgabewert schon, für die Position, wo das Element gefunden wurde und -1 entspricht "nicht gefunden".

Der.Kaktus 3. Jun 2008 14:27

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
..so, nun iss der Code wie bei dem Link von "#2" ;-)

Amateurprofi 4. Jun 2008 09:55

Re: [Algorithmus] Binäre Suche für Zeichenketten
 
Michael,
vielleicht solltest du das noch etwas optimieren.

Delphi-Quellcode:
var ...
     relationship : integer;
begin
   ...
   relationship := CompareStr(SortedStrArray[middle], s);
   if relationship < 0 then begin
      // SortedStrArray[middle] < s
   else if relationship=0 then begin
      // SortedStrArray[middle] = s
   else begin
      // SortedStrArray[middle] > s
   end;
   ...
end;
Warum :
Bei deiner Konstruktion vergleichst du in der While-Schleife die Strings (bis auf den letzten Durchlauf) immer zwei Mal.
So, wie oben dargestellt, vergleichst du die Strings immer nur ein Mal und prüfst danach einen Integerwert, was deutlich schneller geht.


Alle Zeitangaben in WEZ +1. Es ist jetzt 19:47 Uhr.
Seite 1 von 2  1 2   

Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz