Code Optimierung

[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?