Prozedur zu langsam, Optimierung nötig

[oldmax]

Hi
Nun, ich denke, die Ablage der Daten in eine Datenbank und die Suchen durch SQL-Anweisung bringen erhebliche Geschwindigkeitsvorteile. Auch wenn's sich kompliziert anhört, ich würd's damit lösen. Filezugriffe sind nun mal einfach zu langsam.
Gruß oldmax

[Reinhard Kern]

Zitat:

Zitat von carknue

Klar, hier ein Beispiel, die erste Zeile ist die Überschrift, die in jeder Datei enthalten ist.

lon lat RXL CID BCCH
6.612051 51.329779 -70 00276 963
6.6122 51.3297 -67 00276 963
6.612051 51.329779 -61 00275 973


Wie gesagt, die Werte sind mit Tabs getrennt. rxl sind immer negative integer von -120 bis -40. lon und lat sind Fließkommazahlen mit unterschiedlich Nachkommastellen.

Den Vorschlag mit Nach Koordinate sortieren, habe ich noch nicht ganz verstanden. Eine Koordinate besteht doch aus zwei Werten, lon und lat. Nach welchem soll ich dann sortieren?

Und wichtig wäre, dass keine doppelten Koordinaten mehr in der Ausgangs Datei sind, sondern nur einmal mit dem größten Wert von rxl

Gruß
Carsten

Sortiert wird erst nach lon, dann nach lat: zum Sortieren must du ja eine Vergleichsfunktion liefern, die vergleicht also lon1 und lon2, nur wenn die gleich sind, vergleicht sie lat1 und lat2. Da das selten vorkommt, hat das nicht mal grossen Einfluss auf die Rechenzeit.

Eine andere Möglichkeit: du liest alles gleich sortiert ein, d.h. jeder Record wird gleich am richtigen Platz eingefügt (mit binärer Suche). Steht da schon einer mit den gleichen Koordinaten, so brauchst du nur den mit dem besseren Wert zu speichern. Dann ist nach dem Einlesen auch schon alles so gut wie fertig. Das gibt natürlich eine Menge Schieberei, aber die braucht jedes Sortierprogramm.

Gruss Reinhard

[carknue]

Ich habe jetzt mal den Tip, die Festplatten Zugriffe durch Open, Close und read und writeln möglichst wegzulassen befolgt. Dies hat in einer anderen Prozedur in meinem Programm auch einen erhelblichen Geschwindigkeitszuwachs gebracht. Mit Matritzen, Quickseach usw. blick ich leider nicht durch, deswegen habe ich die Prozedur jetzt mal so geändert. Leider ist diese Variante überhaupt nicht schneller, würde eher sagen deutlich langsamer. Wo ist denn da jetzt der Flaschenhals? Das Loadfrom File geht noch recht schnell aber dann braucht der Rechner bestimmt 1-5 Sekunden pro Zeile. Die Listboxen habe ich unsichtbar gemacht.

Delphi-Quellcode:

procedure TForm1.Button7Click(Sender: TObject);
var
  rxl: string;
  suchkoor: string;
  Koor: Array[0..1000] of string;
  i,l,k,j,maxi: Integer;
  maxrxl: Integer;


begin
 Screen.Cursor:=crHourglass;
 DecimalSeparator:='.';
 listbox1.Clear;
 listbox2.Clear;
 listbox2.items.Add('lon'+chr(9)+'lat'+chr(9)+'RXL'+chr(9)+'CID'+chr(9)+'BCCH');
 listbox1.Items.LoadFromFile(OpenDialog1.FileName);
 label10.Caption:=inttostr(listbox1.Items.Count);
 update;
 i:=1;
 repeat
     suchkoor:=copy(Listbox1.Items[i],1,GetPosNumX(chr(9),Listbox1.Items[i],2)-1);
     l:=1;
     k:=0;
     repeat
       if pos(suchkoor,listbox1.Items[l])>0 then
       begin
        koor[k]:=listbox1.Items[l];
        k:=k+1;
        listbox1.Items.Delete(l);
        l:=l-1;
       end;
       l:=l+1;
     until l=listbox1.Items.Count-1;
     maxrxl:=-200;
     maxi:=0;
   if k=1 then listbox2.Items.Add(koor[0])
   else
   begin
     for j := 0 to k - 1 do
     begin
       rxl:=copy(koor[j],GetPosNumX(chr(9),koor[j],2)+1,GetPosNumX(chr(9),koor[j],3)-GetPosNumX(chr(9),koor[j],2)-1);
       label11.Caption:=koor[j];
       label12.Caption:=inttostr(k);
       update;
       if strtoint(rxl)>maxrxl then
       begin
        maxrxl:=strtoint(rxl);
        maxi:=j;
       end;
     end;
     listbox2.Items.Add(koor[maxi]);

   end;
    i:=1;
   until i=listbox1.Items.count-1 ;

 listbox2.Items.SaveToFile('c:\bs.txt');
 Screen.Cursor:=crDefault;
end;

Gruß
Carsten

[Ghostwalker]

Also spontan:

1. Statt einer Listbox eine Stringliste verwenden
2. BeginUpdate/EndUpdate vor/nach der Verarbeitung
3. Um die Copy's zu sparen, die Eigenschaft Delimiter auf TAB setzen. Damit dröselt die Stringliste
die Werte in einzelne Zeilen auf und du kannst dir die copy's und Pos sparen. Jeweils 5 Zeilen in
der Stringlist würden dann einer Zeile in der Datei entsprechen.

[Mavarik]

Zitat:

Zitat von carknue

lon lat RXL CID BCCH
6.612051 51.329779 -70 00276 963
6.6122 51.3297 -67 00276 963
6.612051 51.329779 -61 00275 973

OK wie wäre es mit diesem Ansatz:

Bilde aus lon und lat einen CRC32
Erzeuge Dir einen Record im Speicher für die o.g. Daten
Erzeuge eine sortierte Liste von der CRC32 koordinaten mit einem Pointer auf den entsprechenden Record...
Oder noch schneller immer 1000 Datensätze einlesen, dann die Liste wieder per Qsort sortieren und doppelte löschen...

Würde sagen dauert dann noch 10-15 sekunde um alles zu erzeugen...

Frank :coder:

PS:Ich bin Pilot und habe mit GPS öffter zu tun, daher die Frage... Was sind das für Daten und woher kommen die bzw. was machst Du damit?

[Michael Habbe]

Hi,

versuche doch einfach erstmal die Daten aus der Textdatei in eine Datenbank einzulesen, z. B. JvMemoryData von den JediVCL.

Hier mal mein Beispiel des Einlesens einer vorher gespeicherten Inventur:

Delphi-Quellcode:

procedure blablupp;
var
  F: TextFile;
  zeile: string;
  art, men, bez, ek, lag: string;
  errorcount: integer;
  k   : array [1..6] of Integer;
  Posi: integer;
  lauf: integer;
  dat : string;
begin
  AssignFile(F, FileName);
  Reset(F);

  MemTbl.EmptyTable;
  while not eof(f) do
  begin
    ReadLn(f, Zeile);
    try
      // Bestimmung der Trennzeichenpositionen
      Posi:=1;
      for Lauf := 1 to length(Zeile) do
      begin
        if (Zeile[Lauf] = #9) then
        begin
          K[Posi] := Lauf;
          Inc(Posi);
        end;
      end;
      K[6] := Length(Zeile)+1;

      art := copy(Zeile, 1, K[1]-1);
      men := copy(Zeile, K[1]+1, K[2]-K[1]-1);
      bez := copy(Zeile, K[2]+1, K[3]-K[2]-1);
      ek  := copy(Zeile, K[3]+1, K[4]-K[3]-1);
      dat := copy(Zeile, K[4]+1, K[5]-K[4]-1);
      lag := copy(Zeile, K[5]+1, K[6]-K[5]-1);
      MemTbl.Append;
      MemTblArtikelnummer.AsString := art;
      MemTblBezeichnung1.AsString := bez;
      MemTblEinkaufspreis.AsString := ek;
      MemTblMenge.AsString := men;
      MemTblZaehldatum.AsString := dat;
      MemTblLagerort.AsString := lag;
      MemTbl.Post;
    except
      inc(errorcount);
      MemTbl.Cancel;
    end;
  end;
  CloseFile(f);
end;

Wenn Du anschließend die Daten in der Tabelle hast, kannst Du mit TDataSet-Funktionen Deine Auswertung weiterlaufen lassen.

So wird die Datei jedenfalls nur ein einziges Mal angerührt.

mfg
Michael

[carknue]

Ich denke, ich habe jetzt eine brauchbare Lösung gefunden. Nach der Stringbox Variante hatte ich es noch mit variablen Arrays versucht. Dies war dann schon deutlich schneller. Von ursprünglich über 3 Stunden für 120.000 Zeilen auf ca 20 Minuten auf einem E6600. Auf einem Celeron D war es dann mit gut einer Stunde immer noch unzumutbar. Habe es dann mit Stringlisten und einem kleinen Array probiert. Hierbei wird jeder gefundene Eintrag sofort gelöscht, damit wird die Routine immer schneller. Nun braucht die Prozedur nur noch 2.5 Minuten auf dem E6600. Und der Code wird auch immer kleiner :wink: Das Sortieren würde bei 120.000 Zeilen ja auch etwas dauern und wenn ich jeden Wert in eine Zeile schreiben würde, hätte ich 600.000 Zeilen. Müßte ich vielleicht nochmal ausprobieren, was das noch bringt.

Hier mein Code:

Delphi-Quellcode:

procedure TForm1.Button8Click(Sender: TObject);
var
  rxl: string;
  suchkoor: string;
  Koor: Array[0..1000] of string[35];
  i,l,k,j,maxi,cl: Integer;
  maxrxl: Integer;
  Liste1: Tstringlist;
  Liste2: Tstringlist;

begin
 Screen.Cursor:=crHourglass;
 DecimalSeparator:='.';
 liste1:=Tstringlist.Create;
 liste1.LoadFromFile(OpenDialog1.FileName);
 l:=liste1.Count;
 progressbar1.Min:=-l;
 progressbar1.Max:=0;
 liste2:=Tstringlist.Create;
 liste2.add('lon'+chr(9)+'lat'+chr(9)+'RXL'+chr(9)+'CID'+chr(9)+'BCCH');
 repeat
  suchkoor:=copy(Liste1[1],1,GetPosNumX(chr(9),Liste1[1],2)-1);
  k:=0;
  i:=1;
  repeat
      if (pos(suchkoor,liste1[i])>0) then
      begin
        koor[k]:=liste1[i];
        k:=k+1;
        liste1.Delete(i);
        i:=i-1;
      end;
      i:=i+1;
      cl:=Liste1.Count;
  until i=cl;
  maxrxl:=-200;
  maxi:=0;
  progressbar1.position:=-cl;
  if k=1 then
  begin
    liste2.Add(koor[0]);
  end
  else if k>1 then
   begin
     for j := 0 to k - 1 do
     begin
       rxl:=copy(koor[j],GetPosNumX(chr(9),koor[j],2)+1,GetPosNumX(chr(9),koor[j],3)-GetPosNumX(chr(9),koor[j],2)-1);
       if strtoint(rxl)>maxrxl then
       begin
        maxrxl:=strtoint(rxl);
        maxi:=j;
       end;
     end;
     liste2.Add(koor[maxi]);
   end;
 until liste1.Count=1;
 liste2.SaveToFile(extractfilepath(OpenDialog1.FileName)+'Best.txt');
 liste1.Destroy;
 liste2.Destroy;
 Screen.Cursor:=crDefault;
end;

Die Daten sind Messwerte von Handys.

Gruß
Carsten

[Jelly]

Kannst Du mal genau sagen, was dein Algorythmus mit den Daten berechnet. Vielleicht findet sich ja auf der Ebene etwas viel Performanteres.

[Hawkeye219]

Hallo Carsten,

ich habe meinen Vorschlag (Beitrag #10) einmal mit zufälligen Daten getestet (E6600-CPU, 2 GByte RAM):

Code:

 25000 Zeilen: Laufzeit < 0.2 sec
 50000 Zeilen: Laufzeit < 0.4 sec
100000 Zeilen: Laufzeit < 0.8 sec

Die Anwendung der Klasse TSparseMatrix ist denkbar einfach:

Delphi-Quellcode:

var
  M : TSparseMatrix;
begin
  M := TSparseMatrix.Create;
  try
    // Originaldatei laden
    M.LoadFromFile ('gps-original.txt');
    // Ergebnis speichern
    M.SaveToFile ('gps-optimized.txt');
  finally
    M.Free;
  end;
end;

Im Anhang findest du eine neue Version, die zwei Fehler korrigiert. Zum einen fehlte eine Initialisierung der Matrixelemente, wodurch negativen RXL-Werte falsch behandelt wurden. Zum anderen erforderte die fehlerhafte Implementierung der Val()-Routine in Delphi eine Nachbehandlung beim Zerlegen der Datenzeilen. Beim Testen konnte ich - abgesehen von der Sortierung - keine Unterschiede in den Ergebnissen beider Verfahren feststellen.

Wenn du Fragen zum Algorithmus hast, kannst du sie gerne hier stellen.

Gruß Hawkeye

[carknue]

@Hawkeye
Ich verstehe nicht ganz, was ich mit der Liste mit allen Elementen einer y-Koordinate soll? Ich brauche doch eher eine Liste mit allen Elementen einer x,y Kombination :gruebel: