Suchgeschwindigkeit optimieren

Miri · Beiträge: 657 Delphi 3 Prof., Delphi 2005 PE

Hallo zusammen!

Ich bin gerade dabei, einen Quelltext mit Kommentaren zu versehen, da fiel mir auf, wie blöd mein aktuelles Suchverfahren darin eigentlich ist :mrgreen:

Aber mir stellt sich doch irgendwie die Frage, was nun wirklich am sinnvollsten ist. Vielleicht könnt ihr mir da ja was zu sagen...

Also: ich habe eine SEHR GROßE Textdatei (x Zeilen) und eine StringListe mit y Zeilen. Jetzt brauche ich nur die Zeilen aus der Textdatei, in der sich eine Zeile aus der Stringliste wiederfindet. Dazu suche ich bisher für jede Zeile der SL die komplette Textdatei durch und hab damit quasi y*x Durchläufe und das dauert ewig!

Als Alternative fiele mir ein,

1. wenn SL[1] in Textdatei[1], Zeile kopieren, und mit Textdatei[2] weitermachen. Wenn SL[1] nicht in Textdatei[1], dann gucken ob SL[2] in Textdatei[1], usw...

oder

2. so wie bisher, aber wenn SL[1] in Textdatei[1] gefunden, dann Textdatei[1] löschen. Dann würde SL[2] nicht mehr in Textdatei[1] suchen können. Hier stellt sich mir aber die Frage (ich arbeite mit AssignFile), ob, wenn ich dann Delete.Textdatei[1] ausführe, und nachher CloseFile anwende, ob die Textdatei am Ende leer ist, denn das will ich nicht...

oder

3. jemand hat eine andere (bessere) Idee?!

Ich hoffe, ich konnte mich verständlich ausdrücken und ihr antwortet fleißig

Gausi · Verfasst: Mi 16.11.05 10:47

Miri hat folgendes geschrieben:

Also: ich habe eine SEHR GROßE Textdatei (x Zeilen) und eine StringListe mit y Zeilen. Jetzt brauche ich nur die Zeilen aus der Textdatei, in der sich eine Zeile aus der Stringliste wiederfindet. Dazu suche ich bisher für jede Zeile der SL die komplette Textdatei durch und hab damit quasi y*x Durchläufe und das dauert ewig!

Unter der Voraussetzung, dass y > xlogx/(x-logx) (also auch ziemlich groß) ist, würde ich dir vorschlagen, die Zeilen der Textdatei vorher zu sortieren und dann die einzelnen Zeilen der Listbox mit Binärsuche zu suchen.
Wenn du die Zeilennummern brauchst, bau dir vorher ein Objekt, was die Zeile und die Original-Nr. enthält und sortiere es nach der Zeile.

Alternativ kannst du auch die Stringliste sortieren und jede Zeile der Textdatei in der Liste suchen - benötigt dann ylogy + xlogy viele Schritte.

(Zum Sortieren braucht man in etwa x*logx Schritte, fürs anschliessende Suchen insgesamt y*logx, insgesamt also (x+y)*logx Schritte, daraus folgt die obige Ungleichung)

_________________
We are, we were and will not be.

Miri · Beiträge: 657 Delphi 3 Prof., Delphi 2005 PE

Ähmm... sorry, das logarithmus-zeugs versteh ich nicht wirklich. Aber y ist nicht allzu groß. Momentan sind es max. 9 Zeilen, glaub ich.
Sieht also etwa so aus:

markieren

Quelltext

1:
2:
3:
4:
5:
6:

abc
def
ghi
jkl
mno
pqr

Die Zeilen der Textdatei enthalten mehrere Sachen, mit ; getrennt. da steht dann irgendwann z.B.

markieren

Quelltext

1:
2:
3:

irgendwas;abc;irgendwasanderes
irgendwas;jkl;irgendwasanderes
irgendwas;abc;irgendwasanderes

und die einzelnen Elemente werden dann in ne DB abgespeichert.

Da jede Zeile der Textdatei eindeutig einem Element der SL zugeordnet werden kann, dachte ich, es würde Sinn machen, wenn ich erst nach SL[1] (abc) suche, alle Zeilen der Textdatei zu löschen, in denen ich (abc) gefunden habe...

Horst_H · Verfasst: Mi 16.11.05 11:21

Hallo,

Also ein kleiner Vorschlag, sortieren nuetzt beim Suchen so nicht, ausser du benutzt CMsort, das auch nach inneren Spalten sortieren kann www.chmaas.handshake...re/cmsort/cmsort.htm
Warum schreibst Du die nicht verarbeiteten Zeilen nicht in eine seperate Datei.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

var
  i,ZeilZaehler : integer;
  Gefunden: boolean;
  Zeile :string;
begin
  DateienOeffnen..
  ZeilZaehler := 0;
  gefunden : boolean;
while notEOF(textDatei) do
  begin
  inc(ZeilZaehler);
  Gefunden := false;
  readln(textDatei,Zeile);
  For i := 1 to sl.Count do
    if Pos(sl[i],Zeile) <> 0 then
      begin
      Gefunden := true;
      ZeileVerarbeiten in DB!! 
      break;//Nicht mehr in dieser Zeile weitersuchen
      end;
  If Gefunden then
    writeln(AndereTextDatei,Zeile);
  end;//while 
CloseFile(AndereTextDatei);  
CloseFile(textDatei);
end;

Gruss Horst

Gausi · Verfasst: Mi 16.11.05 11:29

Jupp, meinen Vorschlag kannste getrost vergessen. Ich dachte, du suchst jeweils die ganze Zeile als ganze Zeile in der Datei.

Das Logarithmen-Gedöns basiert auf der Laufzeit des Sortierens und des Suchens in einer sortierten Liste. Wenn man nur einmal sucht, dann lohnt sich das vorherige Sortieren nicht. Sucht man öfter, ist ein Sortieren sinnvoll. Wo die ungefähre Grenze liegt kann man mit diesem Zeugs abschätzen ;-)

_________________
We are, we were and will not be.

Miri · Beiträge: 657 Delphi 3 Prof., Delphi 2005 PE

Horst_H hat folgendes geschrieben:

Hallo,

Also ein kleiner Vorschlag, sortieren nuetzt beim Suchen so nicht, ausser du benutzt CMsort, das auch nach inneren Spalten sortieren kann www.chmaas.handshake...re/cmsort/cmsort.htm
Warum schreibst Du die nicht verarbeiteten Zeilen nicht in eine seperate Datei.

markieren

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

var
  i,ZeilZaehler : integer;
  Gefunden: boolean;
  Zeile :string;
begin
  DateienOeffnen..
  ZeilZaehler := 0;
  gefunden : boolean;
while notEOF(textDatei) do
  begin
  inc(ZeilZaehler);
  Gefunden := false;
  readln(textDatei,Zeile);
  For i := 1 to sl.Count do
    if Pos(sl[i],Zeile) <> 0 then
      begin
      Gefunden := true;
      ZeileVerarbeiten in DB!! 
      break;//Nicht mehr in dieser Zeile weitersuchen
      end;
  If Gefunden then
    writeln(AndereTextDatei,Zeile);
  end;//while 
CloseFile(AndereTextDatei);  
CloseFile(textDatei);
end;

Gruss Horst

Das entspricht ja soweit meiner ersten Überlegung (nur so lange eine Zeile nach den SL-Elementen durchsuchen, bis eins gefunden wurde).

Hab das jetzt mal auf mein Prog angepasst. In der If-Schleife (if Pos(sl[i].....) verwurste ich meine Zeile in die DB. Dann setze ich das break, was - wenn ich's richtig verstehe - die For-Schleife beenden sollte. Gefunden und die andere Text-Datei brauche ich eigentlich nicht, da ich doch meine Daten dann in der DB habe und auch sonst nur aus der DB benötige.
Also war alles, was ich gesucht hab, das break

aber so ist das ja mit dem Wald und den Bäumen

Ich hätte jetzt an gaaaanz viele if-Verschachtelungen gedacht *g*

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme