binäre Suche... Ich bin echt grad' zu blöd

[yankee]

Es ist zwar schon etwas peinlich, aber ich bin gerade an einem der simpelsten Prinzipien der Informatik am scheitern: Bei der binären Suche.
Ich habe einen Array aus:

Delphi-Quellcode:

  TVarManEntry =record
    name: string;
    data: TLeanoVar;
  end;

Bei der ich auf einzelne Elemente per name zugreifen will und zu Geschwindigkeitszwecken den Array nach name sortiere.
Hier ist zum Beispiel meine procedure, die einen Eintrag erneuern soll, bzw. bei nicht-Existenz einen Eintrag anlegen soll:

Delphi-Quellcode:

procedure TVarManager.setVar(const key: string; val: TLeanoVar);
var hi,lo,cur,i: integer;
begin
  hi :=length(FVars);
  lo :=0;
  cur :=0;
  while (hi >=lo) do
  begin
    cur :=(hi+lo) div 2;
    if FVars[cur].name > key then lo :=cur+1
    else if FVars[cur].name < key then hi :=cur-1
    else
    begin
      FVars[cur].data.Free;
      Fvars[cur].data :=val;
      exit;
    end;
  end;
  setlength(FVars, length(FVars)+1);
  for i:=length(FVars)-1 downto cur+1 do FVars[i] :=FVars[i-1];
  FVars[cur].name :=key;
  FVars[cur].data :=val;
end;

FVars ist das Array.
Ich habe da jetzt immer wieder dran rumgespielt und die procedure wurde wahrscheinlich nur falscher und falscher und jetzt bin ich schon so frustriert, dass ich bereit bin mir die Blöße zu geben undn öffentlich nach Hilfe zu fragen :-(.

F1!

[alzaimar]

Bei der binären Suche ist es leider nicht so, das cur am Schluss auf die richtige Stelle zeigt. Du musst noch prüfen, ob das einzufügende Element wirklich an die Stelle kommt. Der Rest sieht soweit ganz gut aus.

Für Deine Bedürfnisse bietet sich eine Hashmap an, die ist schneller. Fertiges Zeugs findest Du hier.

Ein DAWG ist noch schneller, verbrät aber auch wesentlich mehr Speicherplatz.

[marabu]

Hallo,

hi sollte besser mit High(FVars) initialisiert werden. Bei deinen Vergleichen hast du die Zuweisungen vertauscht. Nach dem erfolglosen Durchlauf zeigt lo auf die Stelle an der das nicht gefundene Item eingefügt werden muss.

Du hast offensichtlich eine Klasse TVarManager entworfen. Ich würde dann die Funktionalitäten entkoppeln und die Methoden Compare, KeyOf, IndexOf und Find implementieren. Als Besitzer einer Enterprise Version kannst du dir das Zusammenspiel bei TStringList anlesen.

Grüße vom marabu

@alzaimar: dein Beitrag ist so komisch rot unterlegt - schämst du dich etwa, weil du ihn abgeschickt hast, während ich noch am tipopen bin?

[alzaimar]

Zitat:

Zitat von marabu

@alzaimar: dein Beitrag ist so komisch rot unterlegt - schämst du dich etwa, weil du ihn abgeschickt hast, während ich noch am tipopen bin?

Ja, denn den Fehler im Code hab ich gar nicht gesehen. :oops:

[yankee]

@alzaimar:
Du hast schon in gewisser Weise recht, dass Hashtabellen dafür besser wären. Ich hatte für diese Aufgabe sogar vorher deine Hashtabelle ingesetzt, aber dann kam ich an die Stelle, wo ich wissen wollte, ob ein bestimmtes Objekt irgendwo in der Liste referenziert ist. Ist natürlich auch mit Hashtabellen alles m,öglich, aber bei deiner Hashtabelle muss ich dann auch noch ständig rumcasten. Und da es unwahrscheinlich ist, dass meine Tabelle jemals den 2-stelligen Bereich sprengen wird, wollte ich erstmal sowas "einfaches" machen.

@marabu:
Ok, dass heisst ich ersetze in:

Delphi-Quellcode:

  for i:=length(FVars)-1 downto cur+1 do FVars[i] :=FVars[i-1];
  FVars[cur].name :=key;
  FVars[cur].data :=val;

cur durch val.

Aber was, wenn die Liste leer ist? Dann kommt schonmal garnichts zustande mit diesem Algo. Muss ich da auf einen Sonderfall schauen? Man müsste das doch auch irgendwie "elegant" als nicht sondefall unterkiregen, oder?

[marabu]

Delphi-Quellcode:

for i := High(FVars) downto Succ(Lo) do 
  FVars[i] := FVars[i-1]; 

FVars[lo].name := key;
FVars[lo].data := val;

Müsste es nicht eher so aussehen?

[yankee]

Zitat:

Zitat von marabu

Müsste es nicht eher so aussehen?

Das ist doch das gleiche nur anders aufgeschrieben ;-).

[marabu]

Ich verwende LO wo du CUR verwendest.