AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

[Algorithmus] Binäre Suche für Zeichenketten

Ein Thema von Luckie · begonnen am 3. Jun 2008 · letzter Beitrag vom 4. Jun 2008
Antwort Antwort
Seite 1 von 2  1 2   
Benutzerbild von Luckie
Luckie
(Moderator)

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#1

[Algorithmus] Binäre Suche für Zeichenketten

  Alt 3. Jun 2008, 12:16
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?
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von Der.Kaktus
Der.Kaktus

Registriert seit: 22. Jan 2008
Ort: Erfurt
958 Beiträge
 
Delphi 7 Enterprise
 
#2

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

  Alt 3. Jun 2008, 12:27
Hallo Micha,

schau mal hier-->Binarysearch
Gruss Kaki

Repeat Until true=false;
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie
(Moderator)

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#3

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

  Alt 3. Jun 2008, 12:40
Ä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 if (SortedStrArray[middle] = s) then eine AccessViolation. Irgendwas stimmt da nicht.
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von Der.Kaktus
Der.Kaktus

Registriert seit: 22. Jan 2008
Ort: Erfurt
958 Beiträge
 
Delphi 7 Enterprise
 
#4

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

  Alt 3. Jun 2008, 12:56
aender mal die Zeile um

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

Repeat Until true=false;
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie
(Moderator)

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#5

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

  Alt 3. Jun 2008, 13:04
Ä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
---------------------------
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
marabu

Registriert seit: 6. Apr 2005
10.109 Beiträge
 
#6

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

  Alt 3. Jun 2008, 13:09
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
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#7

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

  Alt 3. Jun 2008, 13:10
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);
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von Luckie
Luckie
(Moderator)

Registriert seit: 29. Mai 2002
37.621 Beiträge
 
Delphi 2006 Professional
 
#8

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

  Alt 3. Jun 2008, 13:20
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".
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
Benutzerbild von Der.Kaktus
Der.Kaktus

Registriert seit: 22. Jan 2008
Ort: Erfurt
958 Beiträge
 
Delphi 7 Enterprise
 
#9

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

  Alt 3. Jun 2008, 14:27
..so, nun iss der Code wie bei dem Link von "#2"
Gruss Kaki

Repeat Until true=false;
  Mit Zitat antworten Zitat
Amateurprofi

Registriert seit: 17. Nov 2005
Ort: Hamburg
941 Beiträge
 
Delphi XE2 Professional
 
#10

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

  Alt 4. Jun 2008, 09:55
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.
Gruß, Klaus
Die Titanic wurde von Profis gebaut,
die Arche Noah von einem Amateur.
... Und dieser Beitrag vom Amateurprofi....
  Mit Zitat antworten Zitat
Antwort Antwort
Seite 1 von 2  1 2   

Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 07:39 Uhr.
Powered by vBulletin® Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2021 by Daniel R. Wolf