String of Array performance/performante Datenverarbeitung

[Bauer321]

Moin,

ich lade mehrere Dateien aus dem Internet herunter und speichere den Inhalt dieser Zeilenweise in Arrays.
Insgesamt habe ich dann (im Moment) 4 Arrays mit bis zu 15000 "Zeilen" pro Array.
Außerdem sollen dieses 4 Arrays dann noch angezeigt werden (Aktuell mache ich dies mit Memos).
Das Nutzen von StringLists war auch sehr langsam. (Also getestet habe ich bisher Array of String und TStringList - beides war sehr langsam)

Problem: Das Programm ist sehr langsam, es dauert mehrere Minuten bis die Operation durchgeführt wurde.
Der Download an sich dürfte dabei nicht das Problem sein (auch wenn ich aktuell keinen eigenen Thread dafür nutze).
Außerdem braucht das Programm Zeitweise bis zu 800MB Ram.

Meine Frage ist nun, wie kann ich die Daten effizient (Speicher & CPU) "verwalten"/verarbeiten?
Ziel ist es am Ende auch noch größere Dateien zu laden (bis 500000 Zeilen).

Ich brauche Zugriff auf die einzelnen Zeilen.
Als Textdatei gespeichert umfassen die Daten momentan 1MB (bis 25MB möchte ich am Ende verwalten).
Es geht um ein Programm welches mehrere "hosts" Listen aus dem Web laden soll.
Diese sollen anschließend zusammengefügt werden, um doppelte Einträge bereinigt werden und es soll eine eigene Whitelist und Blacklist angewendet werden.


Gruß Sven

edit: Arrays scheinen mir aber auch nicht der richtige Weg zu sein, da ich ja auch an beliebiger Stelle Zeilen entfernen können möchte.

[corpsman]

Viel Zeit macht man unbewusst kaputt

wenn du z.b. deine Array's so allokierst :

Code: Alles auswählen

 
var f:Textfile;
s:String;
a:Array of String;
begin
..
while not eof(f) do begin
readln(f,s);
setlength(a, high(a)+2);
a[high(a)] := s;
end;
 

ist das extrem langsam. Schneller geht es z.B. so.

Code: Alles auswählen

 
var f:Textfile;
s:String;
a:Array of String;
c:integer;
begin
..
c := 0;
setlength(a, 1000);
while not eof(f) do begin
readln(f,s);
a[c] := s;
inc(c);
if c > high(a) then 
setlength(a, high(a)+1001);
end;
setlength(a, c);
 

So gibt es ettliche Beispiele die Ineffizent sein können. Unter Linux gibts das Valgrind tool, welches dir hilft zu zeigen wo du Zeit verplemperst. Evtl. hilft es auch wenn du uns mehr informationen (zeig deinen Code) gibst.

Wenn Du Löschen auch haben willst wäre eine Überlegung mittels Baumstrukturen wahrscheinlich am sinnvollsten, die sind gut beim suchen ( z.B. Rot-Schwarz-Baum, AVL-Baum..) und durch die Zeiger-strukturen muss nicht bei jedem Löschen alles andere umkopiert werden (wie das beim Array der Fall ist).

Gruß

Corpsman

[mschnell]

Oft ist das Anzeigen mit Memo eine Bremse.

Bau das zum Testen mal aus.

Eigentlich sollten Strings eine ziemlich optimale Verwaltung sein.

Langsamer als bei anderen möglichen Strukturen ist bei Strings (solange Du keine Code - Konvertierung machst) als Einzel-Aktion eigentlich nur "delete()"

Wenn Du Strings "schreddern" willst wird die Sachen natürlich aufwendig. Ich glaube aber kaum, dass es eine bessere Standard-Verwaltung für Byte-Ketten beliebiger Länge gibt

-Michael

[Bauer321]

aufgrund des Löschens habe ich überlegt eventuell eine doppelt verkette Liste zu nutzen.
Bei der muss man nur zwei Zeiger ändern um ein Element zu entfernen und den Speicher des entfernten Elements wieder frei geben.
Das wird auf jeden Fall erheblich schneller sein, als den kompletten Inhalt des Arrays um ein Element zu verschieben (Ok, auch daran könnte man arbeiten, z.B. erst allen zu entfernenden Strings eine leere Zeichenkette zuweisen und anschließend den Inhalt des Arrays "umschaufeln" - würde mehrmaliges Verschieben von Inhalten verhindern).

Und das mit dem Ändern der Größe des Array habe ich glaube ich schon recht optimal gemacht (Man könnte noch erst eine Schleife machen die berechnet wie groß der Array sein muss, das würde die Anzahl der Änderungen von aktuell 4 auf 1 verkleinern.

Der Code sieht aktuell wie folgt aus.

Code: Alles auswählen

 
function TFMain.getHosts():Boolean;
var
  x, n, z: Integer;
  tmp: TStringList;
begin
  result := true;
  tmp := TStringList.Create;
 
  for x := 0 to Length(sources)-1 do
  begin
    with THTTPSend.Create do
      begin
        if HTTPMethod('GET', sources[x].url) then
        try
          tmp.clear;
          tmp.LoadFromStream(Document);
          SetLength(sources[x].hosts, tmp.count);
          for n := 0 to Length(sources[x].hosts)-1 do
          begin
            sources[x].hosts[n] := tmp.Strings[n];
          end;
        except
          result := false;
        end;
        Free;
      end;
  end;
 
  SetLength(hosts, 0);
  z := 0;
  for x := 0 to Length(sources)-1 do
  begin
    SetLength(hosts, Length(hosts)+Length(sources[x].hosts)); //Hier hatte sich der Fehler eingeschlichen
    for n := 0 to Length(sources[x].hosts)-1 do
    begin
      hosts[z] := sources[x].hosts[n];
      z += 1;
    end;
  end;
end;
 
procedure TFMain.bupdateClick(Sender: TObject);
var
  x, n: Integer;
  start, stop: Real;
begin
  start := GetTickCount();
  if getHosts() = true then
     begin
      //DropComments();
 
      memos[0].Lines.BeginUpdate;
      for n := 0 to Length(hosts)-1 do memos[0].Lines.Add(hosts[n]);
      memos[0].Lines.Add('#Anzahl der Zeilen: '+InttoStr(memos[0].Lines.Count));
      memos[0].Visible := true;
      memos[0].Lines.EndUpdate;
 
      for x := 1 to Length(sources) do
      begin
        memos[x].Lines.BeginUpdate;
        for n := 0 to Length(sources[x-1].hosts)-1 do memos[x].Lines.Add(sources[x-1].hosts[n]);
        memos[x].Lines.Add('#Anzahl der Zeilen: '+InttoStr(memos[x].Lines.Count));
        memos[x].Lines.EndUpdate;
      end;
 
  end else ShowMessage('false');
  stop := GetTickCount();
  ShowMessage('Laufzeit: '+FloatToStr(stop-start)+'ms; '+FloatToStr((stop-start)/1000)+'s');
end;    

Ich nutze bewusst mehrere StringLists, deren Sichtbarkeit ich ändere, da bei der Nutzung eines Memos je nach Liste welche man sehen möchte wieder das komplette Memo geändert werden müsste.
Eventuell gibt es noch eine bessere Möglichkeit die Daten vom Stream im Array zu speichern.

Edit: ich glaube ich habe den Fehler gefunden
hat sich ganz unbeabsichtigt eingeschlichen.
Ich habe SetLength an der falschen Stelle geschrieben.
Das erklärt auch weshalb das GB an Ram brauchte - es wurde ein Array mit Millionen von Elementen geschaffen

[Bauer321]

Ich hab den vorigen Beitrag nun bearbeitet.

Ich bin mir nicht sicher ob man das Auslesen der Informationen aus dem Stream nicht noch beschleunigen kann.
Aktuell braucht das Programm 5-20 Sekunden (für den Download von 4 Dateien mit insgesamt 34000 Zeilen - inklusive des Speicherns in den Arrays und der Ausgabe in den Memos) um es zu beschleunigen werde ich auf jeden Fall noch Threads nutzen.

[Patito]

Moin,

ich lade mehrere Dateien aus dem Internet herunter und speichere den Inhalt dieser Zeilenweise in Arrays.
Meine Frage ist nun, wie kann ich die Daten effizient (Speicher & CPU) "verwalten"/verarbeiten?
Ziel ist es am Ende auch noch größere Dateien zu laden (bis 500000 Zeilen).

Ich brauche Zugriff auf die einzelnen Zeilen.

Am effizientesten ist es sicher die Daten aus dem Stream einfach direkt in einen einzigen großen
Speicherblock zu knallen, und den Rest (Zeilenindex, ...) zu Fuß (mit Pointern) selbst zu machen.
Je schneller man es haben will, umso weniger kann man sich leider auf Standardklassen wie TStringList, TStream, ...
verlassen. Wenn man nicht alles selbst machen will, sollte man zumindest erst mal alles vermeiden,
was intern die eingelesenen Daten irgendwie kopiert oder umcodiert.

TMemo ist für große Datenmengen auch schlecht, da man dort den ganzen Text in das Memo hinein kopieren muss.
Besser ist es z.B. ein DrawGrid zu nehmen, dem man nur sagt wieviele Zeilen es gibt. Im OnDraw() muss man dann
nur die paar Textstellen heraussuchen, die gerade auf den Bildschirm gezeichnet werden sollen.

Der Flaschenhals sollte bei "kleinen" Datenmengen (< 1GB) eigentlich immer außerhalb
vom Pascal-Code liegen. Wenn man für 50 MB intern mehr als 100 Millisekunden verbrät ist irgendwas faul.

Wenn Du es schnell haben willst, solltest Du unbedingt einen Profiler verwenden, ohne Profiler stochert man nur im Dunkeln rum.

[mschnell]

Am effizientesten ist es sicher die Daten aus dem Stream einfach direkt in einen einzigen großen
Speicherblock zu knallen, und den Rest (Zeilenindex, ...) zu Fuß (mit Pointern) selbst zu machen.

Das sehe ich auch so.

Zum Glück haben die Rechner ja heute viel Speicher.

Für Große Dateien brauchst Du möglicherweise komplette 64 Bit Verarbeitung.

-Michael

[Bauer321]

Ich mache es nun mal mit einem StringGrid - oder hat das im Gegensatz zum DrawGrid wieder einen Nachteil?

Edit: Es scheint mit einem StringGrid nicht zu funktionieren. - siehe: http://forum.lazarus.freepascal.org/ind ... l#msg79233
Edit2: Ich habe das Ganze jetzt mit dem DrawGrid umgesetzt und es funktioniert wunderbar!