Thema: Delphi Code Optimierung

Einzelnen Beitrag anzeigen

alzaimar
(Moderator)

Registriert seit: 6. Mai 2005
Ort: Berlin
4.956 Beiträge
 
Delphi 2007 Enterprise
 
#16

Re: Code Optimierung

  Alt 21. Jul 2008, 19:56
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.
"Wenn ist das Nunstruck git und Slotermeyer? Ja! Beiherhund das Oder die Flipperwaldt gersput!"
(Monty Python "Joke Warefare")
  Mit Zitat antworten Zitat