große stringlisten schnell vergleichen

[erik]

Hallo

ich habe ein Problem.
Und zwar versuche Messwerte miteinander zu vergleichen und dann den Mittelwert aus mehreren Messreihen zu bilden.
Dabei lese ich die Messwerte als String in eine Stringlist ein.

Das eigentliche Problem dabei ist, dass die Versuche nicht alle gleich lang gelaufen sind (die Stringlists ist also nicht immer gleich lang) und die Messwerte zu unterschiedlichen Zeiten aufgenommen wurden. Daher muss ich die Stringlisten miteinander vergleichen und dem entsprechenden Zeitintervall dann den richtigen Wert zuordnen.

BSP:

SlZeit1 SlWert1 SlZeit2 SlWert2
0 0,1 0 0,3
1 0,12 2 0,1
2 0,22 4 0,4
3 0,23 6 0,3
4 0,1

in Endeffekt soll dann man sowas rauskommen:
SlzeitErgeb SlWertErg
0 0,4
2 0,32
4 0,5


im Moment sortiere ich die Stringlist nach der Anzahl der Einträge und vergleiche anschließend die Werte der kleineren Stringlist mit der Größeren und ordne die Werte zu, allerdings dauert das bei teilweise 8000 Messwerten (pro Liste) zu lang.
Gibt es da einen Effektiveren weg? Bei mehreren hundert zu vergleichenden Listen würde das ja Tage dauern wenn ich jedweils 640000 Vergleiche habe

Code: Alles auswählen

if tmplist1z.Count < tmplist2z.Count then
       begin
       tmplist3z:=tmplist1z;
       tmplist3m:=tmplist1m;
 
       tmplist1z:=tmplist2z;
       tmplist1m:=tmplist2m;
 
       tmplist2z:=tmplist3z;
       tmplist2m:=tmplist3m;
 
       end;
 
              begin
              for k:=0 to tmplist2z.Count-2 do
                begin
                for j:=k to tmplist1z.Count-2 do
                    begin
                     if tmplist2z.ValueFromIndex[k]=tmplist1z.ValueFromIndex[j]
                     then
                         begin
 
                         tmplist2m.Insert(k,floattostr(strtofloat(tmplist1m.ValueFromIndex[j])+strtofloat(tmplist2m.ValueFromIndex[k])));
 
 
                         end;
                    end;
                 end;
              end;

[Scotty]

Warum nimmst du nicht R, Matlab, SPSS, Statistica o.ä.?

[mschnell]

Dabei lese ich die Messwerte als String in eine Stringlist ein....

Wenn es auf Geschwindigkeit und Massen-Verarbeitung von Messwerten ankommt sind Strings natürlich die schlechteste aller Alternativen.

Genau dafür wurde der Typ Real erfunden.

Also beim Einlesen in Real verwandeln und dann sortieren / verarbeiten! Die Verwendung solcher extrem langsame Operationen wie FloastToStr() und StrToFloat() innerhalb der Verarbeitungsschleifen muss natürlich unbedingt vermieden werden. Auperdem muss darauf geachtet werden, dass der verwendete Speicher so klein wie möglich ist (Strings brauchen viel mehr platz als Real-Werte), damit der Cache des Prozessors optimal ausgenutzt wird. Im schlimmsten Fall werden Speicherbereiche auf die Platte ausgelagert, was die Verarbeitung tausendfach verlangsamen kann.

Für Werte-Listen unterschiedlicher Länge kannst Du dynamische Arrays verwenden.

Die Zeilen von mit Dynamischen Arrays aufgebaute Matrizen kannst Du z.B. durch Bearbeitung der ganzen Zeilen-Vektoren (also mit Pointer-Operationen) sehr schnell (ohne Umspeichern der Elemente) sortieren.

Je nach Anwendung sind statische Arrays noch schneller. Es macht auch nichts, einige große Statische Arrays anzulegen. Der Speicherbereich dafür wird physikalisch erst aktiviert, wenn er wirklich gebraucht wird.

-Michael

[erik]

@ scotty
zum einen, weil ich die programme nicht zu verfügung habe zum anderen weil das programm messwertprotokolle auslesen soll ( es sind noch andere daten enthalten) und die dann in einer datenbank ablegt, welche anschließend nach bestimmten kriterien gefiltert werden kann um die versuche zu vergleichen


@michael

das mit den arrays muss ich mir mal anschauen, habe da leider keine ahnung davon

die messwerte sind in der form :
"|0|,|1|,|2| ..." als string gespeichert (messwerte und zeit separat)
daher habe ich die stringlist verwendet, da ich die mit quotechar und delimitertext einlesen und dann abarbeiten konnte

Ich habe es so abgeändert, dass nur noch die entsprechenden werte, je nach messintervall (60sek, 30 sek...) miteinander verglichen werden, das funktioniert an sich ganz gut "relativ" schnell, zumindest im vergleich zu vorher allerdings kommt es doch immer mal zu abbrüchen, da die listenlänge nicht funzt (out of bounds)

Code: Alles auswählen

teiler:=round(strtofloat(tmplist2z.ValueFromIndex[1])/strtofloat(tmplist1z.ValueFromIndex[1]));
 
 for k:=0 to tmplist2z.Count-2 do
      begin
       j:=round(k*teiler);
       try
       tmplist2m.Insert(k,floattostr(strtofloat(tmplist1m.ValueFromIndex[(j)])+strtofloat(tmplist2m.ValueFromIndex[k])));
 
       except
       tmplist2m.Insert(k,(tmplist2m.ValueFromIndex[k]))
       end;
 
      end;

[Eclipticon]

Nur der Vollstaendigkeit halber: R (http://www.r-project.org/" onclick="window.open(this.href);return false;) und Octave (http://www.gnu.org/software/octave/" onclick="window.open(this.href);return false; ; MATLAB-aehnlich) sind freie Software ...

[Scotty]

@ scotty: zum einen, weil ich die programme nicht zu verfügung habe zum anderen weil das programm messwertprotokolle auslesen soll ( es sind noch andere daten enthalten) und die dann in einer datenbank ablegt, welche anschließend nach bestimmten kriterien gefiltert werden kann um die versuche zu vergleichen

R ist kostenlos (siehe Link von Eclipticon), hat flexible Leseroutinen - und ein Script zu erzeugen, macht genauso viel Spaß wie Pascal programmieren. Zusätzlich gibt es ein sehr effizientes Datenhandling, hübsche Graphiken, feinste Statistiken... Gründe etwas selbst zu bauen, wären IMHO kommerzielle Interessen und Einarbeitungszeit in die Scriptsprache oder Datenmengen deutlich oberhalb von Gigabyte. Und vielleicht noch eine (übersteigerte) Freude an Lazarus.
In deinem Code sind unzählige Geschwindigkeitsbremsen, von der Verarbeitungslogik abgesehen. Insert statt Add, Konvertierung float-str, ValueFromIndex... Ein paar Tausend Messwerte sind nicht "groß" sondern eher ziemlich wenig; das sollte sogar mit Stringlisten unter einer Sekunde dauern (erst einlesen, dann sortieren und zuletzt Werte finden; ValueFromIndex[k] ist bei einer Iteration unlogisch).

[erik]

wenn ich ehrlich bin habe ich jetzt nicht unbedingt noch lust mich in r einzuarbeiten sondern würde das gern so zum laufen bekommen.

kommerzielle interessen gibt es nicht ich hab nur einmal mir lazarus angefangen und will es damit auch zuende bringen (muss ja irgendwie gehen)

zu der wahl von insert und valuefrom index

die listen sind ja chronologisch aufgebaut, daher muss ich beide (bzw die 4) listen ja auch durchlaufen um die entsprechenden messwerte zu erhalten, ich will ja nicht den messwert von 30 sekunden in dem einen protokoll mit dem von 60sek in dem anderen protokoll vergleichen und verrechnen, daher muss ich ja insert nehmen um den entsprechenden wert an der richtigen position einzufügen, add würde sie ja nur anhängen, gleiches gilt für valuefromindex @ richtigen wert auslesen

und die schleife iteriert nicht sondern vergleicht wie gesagt listen miteinander, es wird also kein wert angenähert sondern ein vorhandener wert (gleicher zeitpunt, aber unter umständen andere position in der liste aufgrund eines anderen messintervalls) soll ermittelt werden und abschließend aus allen werten der mittelwert gebildet (pro zeitpunkt)

die konvertierung kann ich leider nicht abstellen, da die messwerte in der db als string gespeichert sind

ich würde das gern als array probieren, wenn das wirklich so viel schneller ist --> gibt es die möglichkeit in array of string in ein array of float umzuwandeln ( also sowas wie in die richtung strtofloat(array) )? oder muss ich jeden wert einzeln umwandeln? würde ja wieder deutlich länger dauern. ebenfalls wäre es stark, wenn man den string gleich über assign oder so etwas dem array zuweisen könnte...

wie ich das array dynamisch erzeuge muss ich mir erstmal noch anschauen den aufbau muss man erstmal verstehen, zum glück sind es nicht so viele dimensionen

grüße erik

[martin_frb]

wenn die werte sortiert sind, oder sortierbar, dann waere ein Tree eine bessere loesung als eine liste.
- schnelleres finden
- und schnelleres einfuegen

Wenn es darum geht einen bestimmten wert in einer liste zu finden (wert aus der ersten liste, gesucht in der 2ten) dann kann eine hash table verwendet werden.

[mschnell]

"|0|,|1|,|2| ..." als string gespeichert (messwerte und zeit separat)
daher habe ich die stringlist verwendet, da ich die mit quotechar und delimitertext einlesen und dann abarbeiten konnte

Zum Einlesen ist das ja auch OK, aber die Einzel-Werte nicht als viele Strings speichern, sondern sofort in numerische Werte (Real oder - falls keine gebrochenen Werte auftreten können - noch besser Integer) wandeln und diese Werte in Arrays/Listen bearbeiten / ab speichern etc.

("EVA": Grundlagen der Datenverarbeitung wenn es auf Geschwindigkeit ankommt.)

-Michael

[Socke]

die listen sind ja chronologisch aufgebaut, daher muss ich beide (bzw die 4) listen ja auch durchlaufen um die entsprechenden messwerte zu erhalten, ich will ja nicht den messwert von 30 sekunden in dem einen protokoll mit dem von 60sek in dem anderen protokoll vergleichen und verrechnen, daher muss ich ja insert nehmen um den entsprechenden wert an der richtigen position einzufügen, add würde sie ja nur anhängen, gleiches gilt für valuefromindex @ richtigen wert auslesen

Wenn du zuerst die Daten zeitlich synchronisierst (alles herausschmeißt, was du nicht brauchst), kannst du die Verarbeitungslogik später einfacher gestalten.

Code: Alles auswählen

teiler:=round(strtofloat(tmplist2z.ValueFromIndex[1])/strtofloat(tmplist1z.ValueFromIndex[1]));
 
 for k:=0 to tmplist2z.Count-2 do
      begin
       j:=round(k*teiler);
       try
       tmplist2m.Insert(k,floattostr(strtofloat(tmplist1m.ValueFromIndex[(j)])+strtofloat(tmplist2m.ValueFromIndex[k])));
 
       except
       tmplist2m.Insert(k,(tmplist2m.ValueFromIndex[k]))
       end;
 
      end;

Dir ist schon klar, dass ein try-finally/except-Block vom Rechenaufwand sehr aufwändig ist?! Daher um die Schleife herum bauen.

wenn die werte sortiert sind, oder sortierbar, dann waere ein Tree eine bessere loesung als eine liste.
- schnelleres finden
- und schnelleres einfuegen

Wenn es darum geht einen bestimmten wert in einer liste zu finden (wert aus der ersten liste, gesucht in der 2ten) dann kann eine hash table verwendet werden.

Bäume verkürzen die Lese-Zeit durch eine verlängerte Einfüge-Zeit. Das Einfügen dauert also länger. In dieser Anwendung halte ich aber sortierte Listen für geeigneter, weil die Daten sequentiell erstellt werden. Da kann recht einfach die Position bestimmen.

[creed steiger]

Damit könntest du evtl. auch was anfangen,es ist eigentlich recht performant beim einlesen von CSV.
http://wiki.freepascal.org/CsvDocument" onclick="window.open(this.href);return false;

[mschnell]

Wenn er doch schon weiß, dass der Input nur aus Zahlen besteht (anscheinend sogar Integers ohne Komma), gibt es doch keinen Grund eine allgemeinere Methodik anzuwenden, als alle Werte beim Einlesen direkt in Zahlen zu konvertieren. Er soillte das Rumeiern lassen und das einfach ausprogrammieren und die Daten in sinnvollen kompakten Strukturen speichern (oder - wie bereits vorgeschlagen wurde - nicht selber programmieren und ein Statistik-Paket verwenden).

Wenn diese Grundvoraussetzung nicht gewollt ist, hat es wenig Zweck über sinnvolle Verarbeitungs-Methoden (wie Hash-Listen) zu diskutieren.

-Michael

[martin_frb]

wenn die werte sortiert sind, oder sortierbar, dann waere ein Tree eine bessere loesung als eine liste.
- schnelleres finden
- und schnelleres einfuegen

Wenn es darum geht einen bestimmten wert in einer liste zu finden (wert aus der ersten liste, gesucht in der 2ten) dann kann eine hash table verwendet werden.

Bäume verkürzen die Lese-Zeit durch eine verlängerte Einfüge-Zeit. Das Einfügen dauert also länger. In dieser Anwendung halte ich aber sortierte Listen für geeigneter, weil die Daten sequentiell erstellt werden. Da kann recht einfach die Position bestimmen.

"Bäume verkürzen die Lese-Zeit durch eine verlängerte Einfüge-Zeit." Der Satz ist sehr interessant. Aber ich nehme an du meinst verlängern?

Das stimmt auch wieder nur unter bestimmten Bedingungen.

Es ist ein Unterschied ob bei einer Stringliste am Ende eingefügt wird (append) oder in der Mitte.
In der Mitte heißt das bei *jedem* einfügen, der Speicher hinter der Position verschoben werden muss. Das kostet (gerade bei sehr grossen Listen) auch Zeit. (JA nur die String pointer, trotzdem)
Aber selbst beim append muss von Zeit zu Zeit der gesamte Speicher verschoben werden. Immer wenn die Kapazität der Liste vergroessert werden muss. Das ist allerdings selten.

Möglich das der Baum dann tatsächlich etwas länger braucht. Aber die Zeit holst du beim suchen locker wieder rein.

Je nach Anwendung kannst du natuerlich zum suchen auch eine Hash table bauen. (Wenn du nur exakte Werte suchst).

Code: Alles auswählen

for k:=0 to tmplist2z.Count-2 do
                begin
                for j:=k to tmplist1z.Count-2 do
                    begin
                     if tmplist2z.ValueFromIndex[k]=tmplist1z.ValueFromIndex[j]

Wenn beide Listen 10,000 Eintraege haben, dann sind das im schlimmsten Falle (2te liste hat *keine Treffer) 10,000*10,000 = 100,000,000 durchlaufe. Wenn die 2te liste die alle Werte der ersten enthaelt, sind es immer noch 50,000,000.

Mit einem Baum (in der Annahme die Werte sind sortierbar), sind es 10,000 * 14 (2^14=16K), also 140,000. Das ist 350 mal schneller. Selbst wenn jetzt jeder Schritt doppelt so lange dauern sollte, ist es noch 175 mal schneller.


Mit einer Hash table brauch die such (innere Schleife) nur einen Schritt. Ok da der hash nicht perfekt sein wird, ist es mehr. Am ende dürfte es mit einem Hash immer noch über 1000 mal so schnell sein.

[mschnell]

Ist doch eigentlich klar:

- Unsortiert (einfach hinten anhängen): schnelles Einschreiben, langsames Suchen, keine Verwaltungs-Struktur, Satz-Zahl nicht begrenzt.
- linear Sortiert (beim Einschreiben alle Nachfolger nach oben schieben): sehr langsames Einschreiben, schnelleres Suchen (binäre Suche), keine Verwaltungs-Struktur, Satz-Zahl nicht begrenzt.
- (Binär-) Bäume: schneller beim Einschreiben und Suchen als linear sortiert, aber höher Verwaltungs-Aufwand, Satz-Zahl nicht begrenzt.
- Hashing: oft die schnellste Methode, recht geringer Verwaltungs-Aufwand, die Geschwindigkeit beim Schreiben und Lesen hängt aber vom Daten-Inhalt und vom Füll-Grad ab, Satzzahl durch Größe der Hash-Tabelle begrenzt.

-Michael

[martin_frb]

Satzzahl durch Größe der Hash-Tabelle begrenzt.

Nur wenn ein "perfekter" hash erwartet wird. Und nur, wenn die tabelle nicht resized werden kann.
Andernfalls gibt es zwar Hashwerte mit mehren Eintragen, aber das lässt sich durchaus implementieren. Zwar gilt dann nicht mehr O(1) aber insgesamt ist die Performance trotzdem noch ähnlich gut