AGB  ·  Datenschutz  ·  Impressum  







Anmelden
Nützliche Links
Registrieren

Code Optimierung

Offene Frage von "Diamondback2007"
Ein Thema von Diamondback2007 · begonnen am 21. Jul 2008 · letzter Beitrag vom 22. Jul 2008
Antwort Antwort
Seite 2 von 3     12 3   
Benutzerbild von Diamondback2007
Diamondback2007

Registriert seit: 2. Feb 2007
260 Beiträge
 
Delphi 2007 Professional
 
#11

Re: Code Optimierung

  Alt 21. Jul 2008, 17:47
Hm...Das verstehe ich nicht... Wo extrahiere ich denn zwei Mal die selben Daten?
Fabian E.
  Mit Zitat antworten Zitat
Horst_

Registriert seit: 22. Jul 2004
Ort: Münster Osnabrück
116 Beiträge
 
#12

Re: Code Optimierung

  Alt 21. Jul 2008, 17:49
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
  Mit Zitat antworten Zitat
Benutzerbild von Diamondback2007
Diamondback2007

Registriert seit: 2. Feb 2007
260 Beiträge
 
Delphi 2007 Professional
 
#13

Re: Code Optimierung

  Alt 21. Jul 2008, 17:52
Ist es denn sinnvoll 13 Millionen Einträge vorher zu sortieren? wenn ja wäre das natürlich super
Fabian E.
  Mit Zitat antworten Zitat
nahpets
(Gast)

n/a Beiträge
 
#14

Re: Code Optimierung

  Alt 21. Jul 2008, 17:58
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.
  Mit Zitat antworten Zitat
Apollonius

Registriert seit: 16. Apr 2007
2.325 Beiträge
 
Turbo Delphi für Win32
 
#15

Re: Code Optimierung

  Alt 21. Jul 2008, 18:00
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.
Wer erweist der Welt einen Dienst und findet ein gutes Synonym für "Pointer"?
"An interface pointer is a pointer to a pointer. This pointer points to an array of pointers, each of which points to an interface function."
  Mit Zitat antworten Zitat
alzaimar
(Moderator)

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

Re: Code Optimierung

  Alt 21. Jul 2008, 20: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
nahpets
(Gast)

n/a Beiträge
 
#17

Re: Code Optimierung

  Alt 22. Jul 2008, 08:51
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
  Mit Zitat antworten Zitat
Benutzerbild von Diamondback2007
Diamondback2007

Registriert seit: 2. Feb 2007
260 Beiträge
 
Delphi 2007 Professional
 
#18

Re: Code Optimierung

  Alt 22. Jul 2008, 09:38
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
Fabian E.
  Mit Zitat antworten Zitat
Benutzerbild von Diamondback2007
Diamondback2007

Registriert seit: 2. Feb 2007
260 Beiträge
 
Delphi 2007 Professional
 
#19

Re: Code Optimierung

  Alt 22. Jul 2008, 09:45
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
Fabian E.
  Mit Zitat antworten Zitat
Benutzerbild von Diamondback2007
Diamondback2007

Registriert seit: 2. Feb 2007
260 Beiträge
 
Delphi 2007 Professional
 
#20

Re: Code Optimierung

  Alt 22. Jul 2008, 10:16
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?
Fabian E.
  Mit Zitat antworten Zitat
Themen-Optionen Thema durchsuchen
Thema durchsuchen:

Erweiterte Suche
Ansicht

Forumregeln

Es ist dir nicht erlaubt, neue Themen zu verfassen.
Es ist dir nicht erlaubt, auf Beiträge zu antworten.
Es ist dir nicht erlaubt, Anhänge hochzuladen.
Es ist dir nicht erlaubt, deine Beiträge zu bearbeiten.

BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks are an
Pingbacks are an
Refbacks are aus

Gehe zu:

Impressum · AGB · Datenschutz · Nach oben
Alle Zeitangaben in WEZ +1. Es ist jetzt 16:48 Uhr.
Powered by vBulletin® Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz