Code Optimierung

[Diamondback2007]

Hallo zusammen,

ich habe hier einen ganz kleinen Algorithmus den ich gerne noch etwas optimieren würde, da er sehr zeitkritisch ist.

Hier mal die interessanten Stellen:

Delphi-Quellcode:

while sl.Count > 0 do
      begin
        SetLength(IDArray, Length(IDArray) + 1);
        IDArray[High(IDArray)].ID := Copy(sl.Strings[0], 0, Pos(';', sl.Strings[0]) - 1);
        IDArray[High(IDArray)].Sum := IDArray[High(IDArray)].Sum + StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[0]));
        sl.Delete(0);
        for i := sl.Count - 1 downto 0 do
          begin
            if IDArray[High(IDArray)].ID = ExtractID(sl.Strings[i]) then
              begin
                IDArray[High(IDArray)].Sum := IDArray[High(IDArray)].Sum + StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
                sl.Delete(i);
              end;
          end;
      end;

Delphi-Quellcode:

function ExtractPZN(const Value: string): string; inline;
begin
  Result := Copy(Value, 9, 7);
{$MESSAGE Warn 'Methode geht von einer konstanten Länge der PZN aus.'}
end;

function ExtractID(const Value: string): string; inline;
begin
  Result := Copy(Value, 0, 7);
{$MESSAGE Warn 'Methode geht von einer konstanten Länge der ID aus.'}
end;

Es geht darum durch diesen Algo knapp 13 Millionen Zeilen zu jagen ;)
Momentan braucht er für 100.000 Sätze knapp 24 Sekunden.
Kann man das noch schneller machen?
Achja die seltsamen IntToStr-Methoden sind Replacements vom FastCodeprojekt und haben schon ziemlich viel gebracht :)

[Apollonius]

Zieh das SetLength vor die Schleife. Das bewirkt Wunder.

[mkinzler]

Setzte die Größe des dynamischen Arrays vor der Schleife einmalig.

[Diamondback2007]

Ich weiß aber nicht wie groß das Array wird... :(

[Diamondback2007]

Obwohl also ich könnte natürlich eine statisches Array draus machen mit ner Größe die auf jeden Fall reicht. Macht das Sinn?

[Apollonius]

Falls das Array vor der Schleife die Länge 0 hat, hat es danach höchstens so lang wie die Stringliste vor der Schleife. Also kannst du die Länge vor der Schleife auf diese obere Schranke setzen, in der Schleife dann mit einer Variablen mitzählen und nachher dann anpassen. Das sind dann nur noch zwei SetLength-Aufrufe.

Des Weiteren würde ich empfehlen, getrennte Daten getrennt zu speichern (z.B. in Records - das spart die Copy-Aufrufe) und eine Zahl auch als Zahl zu speichern.

[nahpets]

High(IDArray) wird ziemlich oft ermittelt, speicher den Wert einmal in einer Variabel und benutze diese, dürfte immer Length(IDArray) + 1 sein (?), muss dann nur einmal pro Schleifendurchlauf der äußeren Schleife ermittelt werden.

Ändert sich die Größe des Arrays während der Laufzeit?

Ist sl sortiert? Wenn ja, dann müsstest Du einen Algorhythmus finden können, der ohne sl.delete(0) auskommt.

Eventuell ist ein sl.sort und dann sequentiell abarbeiten schneller.

Kannst Du die zu erwartende Größe des Array vorher bestimmen, dann musst Du sie nur einmal setzen. (Könnte ein Nebeneffekt des Sortierens sein, dass die Ermittlung vereinfacht wird. (= Anzahl der ID's?))

[mkinzler]

Zitat:

Zitat von Diamondback2007

Ich weiß aber nicht wie groß das Array wird... :(

Maximal sl.Count

Lieber einmal größer initialisieren und am Ende kürzen

[Diamondback2007]

Zitat:

Zitat von Apollonius

Falls das Array vor der Schleife die Länge 0 hat, hat es danach höchstens so lang wie die Stringliste vor der Schleife. Also kannst du die Länge vor der Schleife auf diese obere Schranke setzen, in der Schleife dann mit einer Variablen mitzählen und nachher dann anpassen. Das sind dann nur noch zwei SetLength-Aufrufe.

Des Weiteren würde ich empfehlen, getrennte Daten getrennt zu speichern (z.B. in Records - das spart die Copy-Aufrufe) und eine Zahl auch als Zahl zu speichern.

Auf die Daten an sich habe ich leider keinen Einfluss, die muss ich nehmen wie sie kommen.
Und wo speichere ich eine zahl nicht als Zahl? eher andersherum ;) Einen string als Zahl ;)

Das Setzen von SetLength vor der Schleife hat bei 100.000 Sätzen noch nicht wirklich was gebracht, aber ich denke bei mehr sollten das was bringen.

Zitat:

Zitat von nahpets

High(IDArray) wird ziemlich oft ermittelt, speicher den Wert einmal in einer Variabel und benutze diese, dürfte immer Length(IDArray) + 1 sein (?), muss dann nur einmal pro Schleifendurchlauf der äußeren Schleife ermittelt werden.

Ändert sich die Größe des Arrays während der Laufzeit?

Ist sl sortiert? Wenn ja, dann müsstest Du einen Algorhythmus finden können, der ohne sl.delete(0) auskommt.

Eventuell ist ein sl.sort und dann sequentiell abarbeiten schneller.

Kannst Du die zu erwartende Größe des Array vorher bestimmen, dann musst Du sie nur einmal setzen. (Könnte ein Nebeneffekt des Sortierens sein, dass die Ermittlung vereinfacht wird. (= Anzahl der ID's?))

Also sl ist nicht sortiert und die Größe ändert sich eigentlich auch nicht wenn ich das vorher mache.

[Apollonius]

Natürlich speicherst du Zahlen als Strings. Deshalb brauchst du ja eine StrToInt-Funktion. ;-)
Und diese rufst du für die PZN-Strings mehrfach auf. Also ist es effektiver, wenn du aus deinem String einmal die Daten extrahierst und sie in einem Record speicherst.

[Diamondback2007]

Hm...Das verstehe ich nicht... Wo extrahiere ich denn zwei Mal die selben Daten?

[Horst_]

Hallo,

Du gehst von einer konstanten Länge der ID aus und diese steht auch noch an erster Stelle 0..6 der Strings in der SL.
Dann kannst Du also die Stringlist vorher sortieren und diese dann der Reihe nach abarbeiten und brauchst nur einmal die SL abklappern (lineare Laufzeit), wie nahpets geschrieben hat, statt immer komplett die verbliebene SL (Quadratische Laufzeit).
Alternativ ein customsort entwickeln.
Bei sortierter Liste ist es ganz simpel.
...
Steze Länge des Feldes auf sl.count (oder einer praxisnahen Faktor davon)
j=0
Wiederhole
ID[j] einlesen, merken in LaufendeID
Summe auf Wert von PZN setzen,
erhöhe i solange i < sl.count
falls ID = LaufendeID dann
erhöhe sum um PZN
sonst
erhöhe j
mache oben hinter wiederhole weiter
...


Gruß Horst

[Diamondback2007]

Ist es denn sinnvoll 13 Millionen Einträge vorher zu sortieren? wenn ja wäre das natürlich super :)

[nahpets]

Zitat:

Zitat von Diamondback2007

Ist es denn sinnvoll 13 Millionen Einträge vorher zu sortieren? wenn ja wäre das natürlich super :)

Probier mal aus, wielange ein sl.sort braucht, einfach so, ohne jetzt schon was einzubauen.

Du rechnest momentan mit einer Laufzeit von 13 * 24 Sekunden (ca.) = 5,irgendwas Minuten. Dauert das sl.sort deutlich weniger, solltest Du es mit dem Sortieren und dann sequentiellem abarbeiten versuchen.

[Apollonius]

Hm, du hast recht, ich habe mich getäuscht. Aber eines fällt noch auf: Einmal extrahierst du die ID, indem du mit Pos nach dem Delimiter suchst; sonst nimmst du an, dass die Länge der ID konstant ist. Entweder du machst diese Annahme gar nicht oder immer!
Und dem Vorschlag, die List nach der ID zu sortieren, kann ich mich nur anschließen. Du erreichst damit eine Laufzeit O(n log n) statt O(n²).

Nebenbei würde mich mal interessieren, wer sich dieses Format ausgedacht hat und woher die Daten kommen.

[alzaimar]

Ich hab das nicht genau analyisert, aber du hast eine Liste mit irgendwelchen Daten und willst die nun unifizieren, also alle doppelten Einträge raussschmeissen. Richtig?

Egal, denn du hast einen Aufwand von O(n^2), die Laufzeit wächst also quadratisch mit der Listenlänge. Das ist schlecht, denn es geht viel schneller:
Die erste Idee ist ja, die Liste zu sortieren, und dann einfach von vorne durch und die mehrfachvorkommen eliminieren. Das wäre in O(n log n) zu machen (verdoppelung der Listenlänge = 2,2x Zeit). Schon recht ordendlich. Aaaaber: Man sortiert vorher und benötigt die sortierten Daten eigentlich nicht, also ein algorithmischer Overkill.

Ich würde es mit einer Hashmap machen. Das ist eine Datenstruktur, mit der man verdammt schnell Daten speichern und wiederfinden kann. Damit wäre das in O(n) zu machen, was dann optimal wäre, denn schneller geht es nicht: Du musst schließlich einmal durch die ganze Liste durch...

Im Prinzip sieht das so aus:

Delphi-Quellcode:

For Element in Liste Do
  If not Hashmap.Find (Element.ID) Then Begin// Wenn wir diese ID noch nicht haben
     SaveToFinalList (element);  
     Hashmap.Add (Element.ID);
  End;

Das ist jetzt Pseudocode, aber ich denke, Du verstehst das Prinzip. Eine Hashmap findest du hier

Da Du gut programmieren kannst, bekommst Du das sicherlich ohne Probleme hin.

[nahpets]

Hallo,

noch eine andere Idee:

Delphi-Quellcode:

// Du hast eine ID von 7 Zeichen Länge.
// Da sie numerisch ist, kann sie alle ganzzahligen Werte von 0 bis 9999999 enthalten.
// Gehe davon aus, dass grundsätzlich jede der möglichen IDs auch vorkommen kann.
Const
     min = 0;
     max = 9999999; 

// Definiere ein Array entsprechender Größe:
Var
     IDArray : Array[min..max] of Cardinal; // Gehe davon aus, dass die Summe aus positiven Integerwerten gebildet wird. 
     iID     : integer; // ID aus der Liste zur weiteren Verarbeitung.
     i       : Integer; // Schleifenzähler

// Wenn Du nun die ID liest, kannst Du sie direkt als Index 
// für das Array benutzen und muss sie nicht extra im Array speichern, 
// da Index und ID identisch sind.
begin
  for i := min to max do IDArray[i] := 0; // Damit wir einen definierten Inhalt haben.
  for i := 0 to sl.count - 1 do begin
    iID := ExtractID(sl.Strings[i]);
    IDArray[iID] := IDArray[iID] + StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
  end;
end;

Das sollte es gewesen sein (nicht getestet).

Stephan

[Diamondback2007]

Zitat:

Zitat von alzaimar

Ich hab das nicht genau analyisert, aber du hast eine Liste mit irgendwelchen Daten und willst die nun unifizieren, also alle doppelten Einträge raussschmeissen. Richtig?

Egal, denn du hast einen Aufwand von O(n^2), die Laufzeit wächst also quadratisch mit der Listenlänge. Das ist schlecht, denn es geht viel schneller:
Die erste Idee ist ja, die Liste zu sortieren, und dann einfach von vorne durch und die mehrfachvorkommen eliminieren. Das wäre in O(n log n) zu machen (verdoppelung der Listenlänge = 2,2x Zeit). Schon recht ordendlich. Aaaaber: Man sortiert vorher und benötigt die sortierten Daten eigentlich nicht, also ein algorithmischer Overkill.

Ich würde es mit einer Hashmap machen. Das ist eine Datenstruktur, mit der man verdammt schnell Daten speichern und wiederfinden kann. Damit wäre das in O(n) zu machen, was dann optimal wäre, denn schneller geht es nicht: Du musst schließlich einmal durch die ganze Liste durch...

Im Prinzip sieht das so aus:

Delphi-Quellcode:

For Element in Liste Do
  If not Hashmap.Find (Element.ID) Then Begin// Wenn wir diese ID noch nicht haben
     SaveToFinalList (element);  
     Hashmap.Add (Element.ID);
  End;

Das ist jetzt Pseudocode, aber ich denke, Du verstehst das Prinzip. Eine Hashmap findest du hier

Da Du gut programmieren kannst, bekommst Du das sicherlich ohne Probleme hin.

Ja, da werde ich mich wohl mal mit auseinander setzen. Das sieht ja ganz nett aus ;)
Ich möchte zwar nicht die doppelten Einträge löschen sondern nur suchen und den zweiten Teil des Eintrages (die PZN) ausummieren. Aber ist ja prinzipiell kein großer Unterschied.

Zitat:

Zitat von nahpets

Hallo,

noch eine andere Idee:

Delphi-Quellcode:

// Du hast eine ID von 7 Zeichen Länge.
// Da sie numerisch ist, kann sie alle ganzzahligen Werte von 0 bis 9999999 enthalten.
// Gehe davon aus, dass grundsätzlich jede der möglichen IDs auch vorkommen kann.
Const
     min = 0;
     max = 9999999; 

// Definiere ein Array entsprechender Größe:
Var
     IDArray : Array[min..max] of Cardinal; // Gehe davon aus, dass die Summe aus positiven Integerwerten gebildet wird. 
     iID     : integer; // ID aus der Liste zur weiteren Verarbeitung.
     i       : Integer; // Schleifenzähler

// Wenn Du nun die ID liest, kannst Du sie direkt als Index 
// für das Array benutzen und muss sie nicht extra im Array speichern, 
// da Index und ID identisch sind.
begin
  for i := min to max do IDArray[i] := 0; // Damit wir einen definierten Inhalt haben.
  for i := 0 to sl.count - 1 do begin
    iID := ExtractID(sl.Strings[i]);
    IDArray[iID] := IDArray[iID] + StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
  end;
end;

Das sollte es gewesen sein (nicht getestet).

Stephan

Das habe ich mal grade ganz schnell getestet, aber ich glaube ich kann keine Array erstellen die so groß sind. Jedenfalls klappt das bei mir nicht. Delphi macht das Array einfach nur bis ca. 131.000 dan ist Schluss.
VOn der Idee her aber genial :)

[Diamondback2007]

Nochmal zu der Hashmap.... Könnte ich die auch so verwenden wie das mit dem Array gezeigt wurde? Also Liste durchgehen, ID als Index in der Hasmap speichern und dann als Data die PZN. Dann über Find gucken ob die ID schon vorhanden ist, und wenn ja dann addieren, wenn nein dann enben hinzufügen. Wäre das schnell? Wie könnte ich denn den Dataoutpout bei Find verändern? Einfach den Wert an der Adresse des Pointers ändern? Geht das?

@alzaimar: Du bist übrigens der erste Mensch außer meinem Info-Lehrer der mich auf die O-Notation anspricht ;) Ich hätte nicht gedacht, dass ich das so schnell wiederhöre :)

[Diamondback2007]

So, ich hätte jetzt folgenden Code:

Delphi-Quellcode:

for i := 0 to sl.Count - 1 do
      begin
        if not StringDic.Find(ExtractID(sl.Strings[i]), Data) then
          begin
            tmpPZN := StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
            Data := @tmpPZN;
            StringDic.Add(ExtractID(sl.Strings[i]), Data);
          end
        else
          begin
            Integer(Data^) := Integer(Data^) + StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
          end;
      end;

Sollte das so klappen?

[nahpets]

Hallo,

wenn Du kein Array der passenden Größe machen kannst, dann mach doch 100.
Eins für 0 bis 99999, eins für 100000 bis 199999 ....
Per Case könntest Du dann nach iID-Bereich abfragen und entscheiden, in welches Array Du die Summe speichern muss.

Naja, diese Lösung ist dann suboptimal und grenzt schon an Gefrickel, aber wenn's funktioniert...

Wofür wird bitteschön der ganze Spaß gebraucht und wie ist mit der Verteilung der IDs zu rechnen?
Gibt es da irgendwelche Bereiche von IDs, die überhaupt nur infrage kommen. Dann läßt sich das Array ja durch anpassen von min und max auf diesen Bereich einschränken ohne dass die übrige Logik davon betroffen wird.
Zumindest von der Zeilenzahl der Liste, kann jede ID 1,3mal vorkommen. Die Hashmap muss dann auch entsprechend groß werden können.

Stephan

[Diamondback2007]

Ähm naja das sind Daten aus dem medizinischen Bereich. Kann ich euch also nicht allzu viel zu sagen.
Es geht nur darum erst mal alle doppelten zu finden und zu addieren und danach alle IDs die die selbe Summe an PZNs haben zu einer Gruppe zusammenzufassen.
Die Hashmap ist groß genug, die vergrößert sich von selber :)

[angos]

--

[alzaimar]

Zitat:

Zitat von Diamondback2007

So, ich hätte jetzt folgenden Code:
...
Sollte das so klappen?

Nein. Du willst die Adresse der lokalen Variablen speichernm aber tmpPZN wird jedesmal verändert. Entweder Du veränderst die Hashmap, sodaß sie bei einem gefundenen Schlüssel die Data-Information gleich überarbeitet, oder Du erzeugst jedesmal Dir dynamisch einen Integer:
Mach es so:

Delphi-Quellcode:

Type
  PInteger = ^Integer;

Var
  Data : PInteger;
  sID : String;

for i := 0 to sl.Count - 1 do Begin
  tmpPZN := StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
  sID := ExtractID(sl.Strings[i]);
  if not StringDic.Find(sID, Pointer (Data)) then begin
    New (Data);
    Data^ := tmpPZN;  
    StringDic.Add(sID, Data);
  end
  else 
    Inc(Data^, tmpPTN);
end;

Achtung! Hinterher aber die Data wieder mit Dispose freigeben! Dazu wanderst Du per 'First/Next durch die Hashmap und gibst einzeln die gelieferten Data wieder frei.

Delphi-Quellcode:

StringDic.First;
While StringDic.Next (sID, PInteger (Data)) Do 
  Dispose (Data);

Große Arrays erzeugt man übrigens dynamisch.

Delphi-Quellcode:

Var
  BigArray : Array Of Integer;

Begin
  SetLength(BigArray, 10000000);

[Diamondback2007]

Achs

Zitat:

Zitat von alzaimar

Zitat:

Zitat von Diamondback2007

So, ich hätte jetzt folgenden Code:
...
Sollte das so klappen?

Nein. Du willst die Adresse der lokalen Variablen speichernm aber tmpPZN wird jedesmal verändert. Entweder Du veränderst die Hashmap, sodaß sie bei einem gefundenen Schlüssel die Data-Information gleich überarbeitet, oder Du erzeugst jedesmal Dir dynamisch einen Integer:
Mach es so:

Delphi-Quellcode:

Type
  PInteger = ^Integer;

Var
  Data : PInteger;
  sID : String;

for i := 0 to sl.Count - 1 do Begin
  tmpPZN := StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
  sID := ExtractID(sl.Strings[i]);
  if not StringDic.Find(sID, Pointer (Data)) then begin
    New (Data);
    Data^ := tmpPZN;  
    StringDic.Add(sID, Data);
  end
  else 
    Inc(Data^, tmpPTN);
end;

Achtung! Hinterher aber die Data wieder mit Dispose freigeben! Dazu wanderst Du per 'First/Next durch die Hashmap und gibst einzeln die gelieferten Data wieder frei.

Delphi-Quellcode:

StringDic.First;
While StringDic.Next (sID, PInteger (Data)) Do 
  Dispose (Data);

Große Arrays erzeugt man übrigens dynamisch.

Delphi-Quellcode:

Var
  BigArray : Array Of Integer;

Begin
  SetLength(BigArray, 10000000);

Okay vielen Dank erst einmal :) Dann werde ich mich mal damit beschäftigen ;)
Wenn man das Array dynamisch erzeugt klappts dann auch größer oder was? :)

[Diamondback2007]

Also das mit dem Array scheint nicht zu funktionieren, dafür das mit der Hashmap aber umso besser :)
Also wenn die Daten die da jetzt rausgekommen sind wirklich stimmen, dann :shock: .
Er braucht jetzt für die 13 Millionen Einträge kürzer als vorher für 100.000 :lol: .
Also vielen Dank schonmal :) :) .
Das war ja eine super Hilfe :dp:

[Diamondback2007]

Hmmm... Ich habe noch etwas Probleme, die Werte aus der Map auszulesen...
Hier mal mein Code:

Delphi-Quellcode:

  StringDic.First;
  ListBox1.Items.BeginUpdate;
  for i := 0 to StringDic.TotalCount - 1 do
    begin
      StringDic.Next(sID, tmpData);
      ListBox1.Items.Add('ID: ' + sID + ' Summe: ' + IntToStr(Integer(tmpData^)));
    end;
  ListBox1.Items.EndUpdate;

So, an sich klappt das nur leider bekomme ich dann Integer Überläufe angezeigt, also halt negative Werte.
Nehme ich nun beim Casten Int64 anstatt Integer, so kommen vollkommen falsche Werte herraus.
Was kann man dagegen tun?

[Diamondback2007]

Okay, Problem gelöst. Ich musste natürlich Data nicht als PInteger sondern als PInt64 deklarieren.
Hier der gesamte Code:

Delphi-Quellcode:

var
  StringDic                   : TStringDictionary;
  tmpPZN                      : Integer;
  Data                        : PInt64;
  sl                          : TStringList;
  sID                         : string;

[...]

    for i := 0 to sl.Count - 1 do
      begin
        tmpPZN := StrToInt32_JOH_IA32_7_a(ExtractPZN(sl.Strings[i]));
        sID := ExtractID(sl.Strings[i]);
        if not StringDic.Find(sID, Pointer(Data)) then
          begin
            New(Data);
            Data^ := tmpPZN;
            StringDic.Add(sID, Data);
          end
        else
          begin
            Inc(Data^, tmpPZN);
          end;
      end;

Vielen Dank :)

[alzaimar]

Delphi-Quellcode:

Var
  tmpData : PInteger;

Begin
  StringDic.First;
  ListBox1.Items.BeginUpdate;
  while StringDic.Next(sID, tmpData) do
    ListBox1.Items.Add('ID: ' + sID + ' Summe: ' + IntToStr(tmpData^));
  ListBox1.Items.EndUpdate;
End;

Bei mir funktioniert das tadellos auch mit PInteger. Hast Du Data etwa schon wieder per Dispose freigegeben?

[Diamondback2007]

Ich darf halt tmpData nicht als PInteger deklarieren... Dann gibt er mir den fehler dass die Parameter stimmen müssen. Ich brauche also einen untyped Pointer. Außerdem reicht Integer halt nicht aus von der Größe. Bei 13 Millionen Einträgen kommt da was zusammen ;)