Suche in ListBox beschleunigen

[rawsoul]

einen guten morgen meine lieben delphianer ;)

mein ziel:
aus vorgegebener wordlist (liste mit ganz vielen wörtern halt ;)) werden einige herausgezogen, und deren buchstaben verdreht. <- das ganze ist vorgegeben... die verdrehten worte sollen nun wieder "zurückverdreht" werden, bis sie einem der wörter in der wordlist gleichen.

soweit die aufgabe. ich habe nun eine funktion geschrieben, die die wörter per zufallsprinzip verdreht und möchte diese nun mit der wordlist, die in einer tlistbox eingeladen sind vergleichen bzw. suchen. falls dieses wort nicht gefunden wurde, soll das vorgegebene wort nochmals verdreht werden, so lange, bis dieses wort dem original gleicht.

1. verdrehe das vorgegebene wort
2. vergleiche es mit allen einträgen der listbox (for .. to .. do)
3. falls es einem der originalwörter gleicht, gebe es in einem memo aus
4. falls es diesem nicht gleicht, beginne bei 1

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
var
  wort,verdreht:string;
  equal:byte;
  listindex,listlaenge:integer;
begin
  equal:=0;
  listlaenge:=listbox1.count;
  wort:=memo1.lines[0];
  repeat
    listindex:=0;
    begin
      verdreht:=wortverdrehen(wort);
      repeat
        begin
          repeat
            begin
              if ListBox1.Items[listindex]=verdreht then equal:=1;
              listindex:=listindex+1
            end;
          until (equal=1) or (listindex=listlaenge-1);
        end until (equal=1) or (listindex=listlaenge-1);
    end until (equal=1) or (listindex=listlaenge-1);
    beep;
  memo2.Lines.Add(memo1.lines[0]);
end;

ich hoffe, man kann mich soweit halbwegs nachvollziehen ;)

jetzt kommen folgende probleme hinzu: in der wordlist sind zirka 1300 wörter und ich habe zum "knacken" von 8 worten gerade mal 30 sekunden zeit. leider brauche ich _mit glück_ schon 30 sekunden für ein wort.

wie kann ich das ganze beschleunigen? oder gibt es eine bessere oder schnellere möglichkeit? (was schöneres möchte ich nicht, man sieht den quelltext später eh nicht) :wall:

viele liebe grüße und nachträglich ein frohes neues jahr ;)

[edit=RawSoul]Quelltext upgedatet... Nochmal komplett von vorn angefangen :lol:[/edit]
[edit=RawSoul]Oh Gott, entschuldigt meine Sauklaue *wegduck*... Sowohl Quelltext als auch komplette Sätze :oops:[/edit]
[edit=RawSoul]Noch ein Quelltextupdate...[/edit]

[Hansa]

Ja, schön. 4 Edits. :lol: Insbesondere, dass der Quelltext von der Prozedur Wortverdrehen nicht gepostet wurde. Denn da liegt wohl der Hund begraben.

[rawsoul]

Hab mich ja dafür entschuldigt... :P

Ich denke, die Prozedur ist ok, aber ich klatsch sie trotzdem mal heir rein ;)

Delphi-Quellcode:

function wortverdrehen(eingabe:string):string;
var
  laenge,k:integer;
  wort:string;
  buchstabe:char;
begin
  result:='';
  wort:=eingabe;
  while length(wort)>0 do
    begin
      laenge:=length(wort);
      k:=random(laenge)+1;
      buchstabe:=wort[k];
      result:=result+buchstabe;
      delete(wort,k,1);
    end;
end;

[Robert Marquardt]

Diese Function ist genau der Zeitfresser. result:=result+buchstabe; und delete(wort,k,1); erstellen dauernd neue Strings.

Delphi-Quellcode:

function wortverdrehen(const eingabe: string): string;
var
  I, Pos1, Pos2: Integer;
  Temp: Char;
begin
  Result := Eingabe;
  for I := 1 to Length(Eingabe)*2 do
  begin
    Pos1 := Random(Length(Eingabe)) + 1;
    Pos2 := Random(Length(Eingabe)) + 1;
    Temp := Result[Pos1];
    Result[Pos1] := Result[Pos2];
    Result[Pos2] := Temp;
  end;
end;

Die obige Funktion verwuerfelt den String einfach durch haeufiges Vertauschen zweier Buchstaben.
Length(Eingabe)*2 stellt einfach sicher das genuegend oft getauscht wird. Das gelegentlich ein Buchstabe mit sich selbst getauscht wird ist nicht weiter tragisch.
(die Funktion ist ungetestet)

[SirThornberry]

es ist nicht gerade effektiv das wort immer wieder zu verdrehen bis es zufälliger weise richtig gedreht ist. Sinvoller wäre es nach Wörtern zu suchen welche gleich lang sind. Wörter die gleich lang sind sollten dann darauf verglichen werde ob die gleichen Buchstaben in der gleichen Menge vorhanden sind.

[marabu]

Hallo Frank,

natürlich kannst du deinen Wortverdreher gewaltig beschleunigen, wenn du einen eleganteren Algorithmus dafür verwendest - den von Robert oder auch diesen. Der Ansatz ist dann aber immer noch brute force.

Eine drastische Beschleunigung erreichst du nur, wenn du eine optimale Speicherung der Wörterliste einführst - den Directed Acyclic Word Graph (DAWG). Die Suche geschieht dann genau anders herum und hoch effektiv.

Grüße vom marabu

[Robert Marquardt]

Na gleich mit dem DAWG nach dem armen Jungen werfen ist ein bischen sehr hart.
Erst mal wuerde mich interessieren was meine Funktion bringt. Danach den Vorschlag von SirThornberry verwirklichen, der darauf hinauslaeuft nur die erfolgversprechenden Worte ueberhaupt zu testen.

[marabu]

Hallo Robert,

der arme Junge wird in knapp zwei Wochen volljährig. Eine naive Implementierung eines DAWG sollte kein Problem sein, wenn er eine verkettete Liste implementieren kann. Wir sollten die Jugend von heute nicht unterschätzen. Außerdem ist es für jeden späteren Leser mit Ambitionen sicher interessant zu lesen, dass es da etwas geben könnte, was die eigene Vorstellungskraft sprengt.

Aber wer weiß: Vielleicht kann Frank mit deiner Hilfe die Laufzeit schon unter 30 Sekunden drücken und alles andere ist ihm egal.

Freundliche Grüße

[rawsoul]

Wow, erstmal vielen Dank für die ganzen Tipps, werde ich alle mal ausprobieren :)

Zitat:

Zitat von marabu

Aber wer weiß: Vielleicht kann Frank mit deiner Hilfe die Laufzeit schon unter 30 Sekunden drücken und alles andere ist ihm egal.

Nein! Das ganz sicherlich nicht! Ich lerne Pascal zwar in meinem Infokurs der Schule, jedoch arbeite ich auch in meiner Freizeit gerne und oft damit. Es ist reines Interesse aus welchem dieser Thread folgte, also bitte keine Vorurteile... :(

Zitat:

Zitat von marabu

der arme Junge wird in knapp zwei Wochen volljährig.

*Freu* :cheers:

Sobald ich Resultate habe, werde ich berichten ;)

LG,
Frank.

[Robert Marquardt]

Mit meinen bald 46 habe ich da eine andere Perspektive :-)
Besonders da ich jetzt einen 21-jaehrigen Kollegen habe. Niht zuletzt waechst mir nach der Chemotherapie wieder der erste Flaum.
Da fuehlt man sich vielleicht merkwuerdig. Wie alt bin ich denn jetzt? Wie war das mit den Blumen und den Bienen?