Code Optimierung

[Diamondback2007]

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