AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Binäre Suche

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

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

Re: Binäre Suche

  Alt 8. Jul 2008, 09:21
Na das sieht doch schon ganz gut aus.
Michael
Ein Teil meines Codes würde euch verunsichern.
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Binäre Suche

  Alt 8. Jul 2008, 09:35
... sooo, nun eine kleine Kritik.
  • Das Quicksort-Verfahren kann dahingehend optimiert werden, das nur ein rekursiver Aufruf erfolgt. Vorlage wäre die Quicksort-Routine von TStringlist. Ich meine, das die schneller/besser ist.
  • Das Suchen mit vorherigem Sortieren ist Quark, denn das dauert länger (O(n log n) als eine Suche in einer unsortierten Liste (O(n)). Da der Anwender genau weiss, ob seine Liste sortiert ist, oder nicht, kann/muss er sie eben gleich selbst sortieren (lassen)
  • Die hier angestrengen Überlegungen für eine allgemeine Listenklasse sind insofern kontraproduktiv, als das die daraus resultierende Klasse sehr behäbig seinen Dienst verrichten würde, da die für die Sortierung elementaren Operationen ('Swap') ausgelagert werden.

Ex-CodeGear! Her mit den Generics! Aber zack! Zack!
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#13

Re: Binäre Suche

  Alt 8. Jul 2008, 09:38
Zitat von alzaimar:

Delphi-Quellcode:
function Search(const aItem: TElement; AArray: TElementArray; var aIndex: Integer): Boolean;
var
  L, R, M: integer; // Für Left, Right, Middle

begin
  L := Low(aItem);
  R := High(aItem);
...
end;
Sollte das nicht besser heißen
Delphi-Quellcode:
  
L := Low(AArray);
R := High(AArray);
Gruß Gammatester
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Binäre Suche

  Alt 8. Jul 2008, 09:51
Och.. äh... Spießer..
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat
Benutzerbild von p80286
p80286

Registriert seit: 28. Apr 2008
Ort: Stolberg (Rhl)
6.658 Beiträge
 
Delphi 7 Personal
 
#15

Re: Binäre Suche

  Alt 8. Jul 2008, 16:10
Hallo sx2008,

ich hab mir Deine Demo einmal angeschaut, und bin bei der Stringsuche irgenwie in der Botanik gelandet.
Ich hab dann ein wenig angepasst und jetzt läufts.

Gruß K-H
Angehängte Dateien
Dateityp: pas binarysearch_205.pas (5,1 KB, 13x aufgerufen)
  Mit Zitat antworten Zitat
gammatester

Registriert seit: 6. Dez 2005
999 Beiträge
 
#16

Re: Binäre Suche

  Alt 8. Jul 2008, 16:33
Zitat von p80286:
Hallo sx2008,

ich hab mir Deine Demo einmal angeschaut, und bin bei der Stringsuche irgenwie in der Botanik gelandet.
Ich hab dann ein wenig angepasst und jetzt läufts.

Gruß K-H
Ich denke, daß zumindest Deine Quciksort-Routine unter einem bekannten Problem leidet:
Delphi-Quellcode:
procedure TBSearch.QuickSort(L, R: Integer);
var
  I, J, P: Integer;
begin
  repeat
    I := L;
    J := R;
    P := (L + R) shr 1;
    repeat
      while Compare(I, P) < 0 do
        Inc(I);
      while Compare(J, P) > 0 do
        Dec(J);
      if (I <= J) then
      begin
        Exchange(I, J);
        Inc(I);
        Dec(J);
      end;
    until (I > J);
    if (L < J) then
      QuickSort(L, J);
    L := I;
  until (I >= R);
end;
Beim Tauschen wird der Pivotindex nicht angepaßt, vgl http://www.delphipraxis.net/internal...ighlight=pivot

Nach Exchange sollte also eingefügt werden

Delphi-Quellcode:
{P muss weiter auf Pivot zeigen} 
if I=P then P:=J
else if J=P then P:=I;
Luckies Routine hat das Problem nicht, da direkt mit einem Array gearbeitet wird.

Gruß Gammatester
  Mit Zitat antworten Zitat
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 +2. Es ist jetzt 05:41 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