optimierung

[grinsebacke]

Hallo Gemeinde,
und zwar hoffe ich auf ein paar tipps von euch.
ich lese eine große datenmenge über einen stringstream ein ca 10mb.
wenn ich nun dieses stream durchsuche beispielsweise nach einem höchsten messwert dauert das eweig.
ich benutze eine simple for schleife.
Nun meine frage welche möglichkeiten gibt es berechnungen zu beschleunigen.
Ich hoffe auf ein paar tipps oder begriffe.
Vielen dank
grinsebacke

[Der schöne Günther]

Den größten Wert in einer verketteten Liste zu suchen ist an sich keine komplexe "Berechnung".

Wächst die Liste auf das zehnfache an, wird es (im Groben) auch zehn mal so lange dauern - Diese Operation (das Suchen des größten Werts) hat eine lineare Laufzeit.

Würdest du aus dieser Liste nicht den größten Wert haben wollen sondern den in der Mitte, ist das immer gleich schnell - Egal wie groß deine Liste ist.

Weiteres zur Laufzeit mit anschaulichen Beispielen findest du z.B. bei

• StackOverflow
• Wikipedia
• Hier

Zu deinem konkreten Problem:
Wenn deine Eingabedaten wirklich absolut unsortiert vorliegen und du nur einmal den größten Wert suchen willst, kann man da nicht viel machen (oder ich stehe ebenfalls auf dem Schlauch). Die meiste Zeit wird höchstwahrscheinlich für das Parsen der Fließkommazahl aus dem String sein - So etwas ist nicht mit ein paar CPU-Takten erledigt!

Hast du nicht die Möglichkeit, die Daten wenigstens direkt als Zahlen einzulesen und nicht als Strings?

Gibt es genaueres? Vielleicht liest du ständig neue Blöcke von der Platte anstatt den ganzen Kram wenigstens einmal komplett in den Hauptspeicher zu schaufeln?

[Klaus01]

. Du könntest den Stream in mehrere Abschnitte einteilen.
Pro Abschnitt dann einen Thread einsetzen der den höchsten Wert aus dem Abschnitt holt.
Zum Schluss alle "höchsten" Werte der Threads vergleichen und daraus den höchsten der Gesamtdatenmemge ermitteln.

Grüße
Klaus

[Furtbichler]

Zusätzlich würde ich noch anregen, das hier 2x durch die 10mb gerattert wird. Das erst Mal beim einlesen und das zweite Mal beim parsen/ermitteln des höchsten Wertes. Beim Einlesen könnte man einen DEA (Deterministischer Endlicher Automat) verwenden, der eine Fließkommazahl fast ohne Zeitverluste erkennt. RegEx arbeitet so, wäre also auch eine Variante.

Wenn die Thread-Variante möglich ist, könnte dies jedoch wirklich die einzige Optimierungsmöglichkeit sein.

Zitat von Der schöne Günther:

Würdest du aus dieser Liste nicht den größten Wert haben wollen sondern den in der Mitte, ist das immer gleich schnell - Egal wie groß deine Liste ist.

'den in der Mitte' = Median? Bei einer verketteten Liste musst Du trotzdem (n/2) Operationen durchführen, um den Median zu erreichen, ergo O(n). Bei einem Array natürlich nicht.

[Der schöne Günther]

Hoppla, als die Finger die Tasten berührten war die verkettete Liste bereits wieder auf meinem Hinterkopf verschwunden.

Ohne Hilfszeiger ist das Navigieren zum Wert in der Mitte tatsächlich weiterhin linear.

[grinsebacke]

wow das ist ja hier ein super forum,
hätte garnicht mit soviel antworten gerechnet.
Das einlesen der Daten und konvertieren (hex->int) dauert ca 6 sekunden.
Das Suchen nach dem größten und kleinsten wert ca. 12 sekunden.
Ich werde mal versuchen einen Thread anzulegen mal sehen.
Erstmal vielen Dank für eure Mühe.
grinsebacke

[gammatester]

Zitat von grinsebacke:

Das einlesen der Daten und konvertieren (hex->int) dauert ca 6 sekunden.
Das Suchen nach dem größten und kleinsten wert ca. 12 sekunden.

Die Bestimmung dee größten und kleinsten Wertes sollte doch praktisch in nicht ins Gewicht fallen im Vergleich zur Umwandlung? Nach dem Schema

Code:

min := MaxInt;
max := -MaxInt;
for ...
  hex -> int 
  if int < min then min := int;
  if int > max then max := int;
endfor

Oder habe ich etwas falsch verstanden?

[grinsebacke]

Jo danke genau das habe ich gerade getan.
Aber im ganzen wird es leider nicht schneller.
Vielleicht finde ich im code ja doch noch ein paar optimierungen

[stahli]

Wenn Du Dein Projekt etwas genauer beschreibst (Quelltext?), kann man vielleicht noch genauer helfen.

Wie oft musst Du denn suchen? Wie oft ändern sich Werte? Gibt es zu den Strings andere zugehörige Daten?
Evtl. ist es sinnvoll, die Daten sortiert zu verwalten.

Welche Delphi-Version nutzt Du denn?

[Mavarik]

hmm

10mb mit einem Blockread in den Speicher laden!

Mavarik