Autor |
Beitrag |
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Do 10.07.14 14:42
Hallo,
vielleicht weiss ja einer von euch eine besonders schlaue Idee dafür, deshalb frage ich einfach mal.
Ich habe eine (ungeordnete) liste aus jeweils z.B. sieben (Ganzzahligen) Koordinaten mit einem dazugehörigem Wert (Oder auch mehreren, aber das sollte ja egal sein). Das ganze bildet quasi messpunkte in einem ("siebendimensionalem") Raum, wobei die abstände immer gleich, jedoch unbekannt sind. Daraus soll nun der User 5 Koordinaten festlegen und dann eine 2d-matrix der übrigen 2 in einem csv-artigem Format zum Import in gängige Analyseprogramme bekommen.
Momentan lese ich zunächst alle daten in ein array aus objekten der form
Quelltext 1:
| a, b, c, d, e, f, g, value: integer |
ein. Danach ermittele ich für alle koordinaten die kleinste "schrittweite", sowie minimum und maximum und erstelle dann ein array mit der größe [(max-min)/schrittweite].
Aus diesem array kann dann der nutzer Beliebige (oft auch mehrere) ebenen aussuchen und speichern.
das Ganze ist sehr unperformant, vorallem da die Liste auch schonmal über eine Million Elemente hat. Da dauert das ganze auch auf einem Gutem PC mit ausreichend Speicher, schneller CPU sowie SSD mehrere Minuten. Das Problem ist halt, dass es ungeordnet ist, sowie die Array-Größe vorher nicht bekannt ist. Deshalb muss ich mehrmals über die Liste iterieren.
Hätte jemand vielleicht eine Grobe Idee eines besseren Algorithmus (in Pseudococde oder text)?
lg Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 10.07.14 15:40
Hallo,
das ist sicher was für Xion
Du willst einen 2D Schnitt machen in einem 7 dim Raum.
Kann man nicht mit array of records arbeiten und die Werte seperat halten.
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10:
| tKoor : integer; tKoorRec = record koDim =array[0..6] of tKoor; koValue = Pointer; end; tMinMaxStep = record koorMin, koorMax, koorStep : tKoor; end; |
Das sind doch nur 1 Mio x 7*4+4 ( Zeiger auf Value(s) ) = 32 MB linear hintereinander da saust der Computer doch drüber, um eine Liste mit Trefferkoordinaten zu erzeugen.
Min,Max,Step wird doch pro Messreihe nur einmal ermittelt. Dann können doch beliebige Schnitte ausgesucht werden.
Ich glaube nicht, dass die Suche der Koordinaten bremst, eher die anschliessende Sortierung,
Gruß Horst
Für diesen Beitrag haben gedankt: Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 10.07.14 21:22
Hallo,
ist eine nichtssagende Aussage, für was
Für eine Tabelle ( schlecht) oder 1000 ( besser ).
Ich habe mal eine array mit 8^7 Werten angelegt (0..7,0..7,....,0..7).
Das wird in 86 ms nach minWert,Maxwert, minStep abgegrast.
Ich habe 7 Sortfelder angelgt und nach der jeweiliegen Dimension sortiert.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| Anzahl Messwerte 2097152 Erstellen 36 ms SortFelder erstellen 19 ms Mischen 214 ms Spannweite 86 ms Sortieren 3696 ms // 7 Felder a 8^7=2'097'152 Elemente Gesamt 4051 ms
real 0m4.064s user 0m4.036s sys 0m0.029s 10^ 7 dauert 21 Sekunden, also fast linear |
Aus der sortierten Feldern kann man leicht die verschiedenen möglichen Werte bestimmen, die der Benutzer ja braucht.
Das dauert alles viel zu lang.
Man kann doch per dictionary /Hash die verschiedenen Werte doch viel schneller bestimmen, ohne alles sortieren zu müssen.Anschliessend kann man ja die reduzierte Anzahl sortieren.
Ein simples Durchtesten von 0.. high(Messwerte) nach 5 fixen Dimensionen geht wohl auch so schnell, wie die Bestimmung der Spannweite also 86 ms
Gruß Horst
Für diesen Beitrag haben gedankt: Boldar
|
|
jfheins
Beiträge: 918
Erhaltene Danke: 158
Win 10
VS 2013, VS2015
|
Verfasst: Do 10.07.14 21:31
Ich brauchte zwei Minuten, aber glaube ich habe es verstanden...
Du bekommt 5 Werte als Referenz, und musst dir erstmal alle Werte (von Millionen) heraussuchen, bei denen diese gleich sind.
Wenn das der Flaschenhals ist, würde ich das ungefähr wie folgt beschleunigen: Die sieben Werte in ein packed record stopfen, und das in ein langes Array. (Ich nehme zumindest mal an, dass deine Daten so ähnlich vorliegen...)
Dann Bastelst du dir eine Maske, mit den Bits die du auf Gleichheit prüfen möchtest. Du allozierst ein Ergebnisarray, das nochmal genau so groß ist, wie die Ausgangsdatenmenge. Schließlich machst du sowas in der Richtung:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37:
| var ResultIndex, i, j, ItemResult: Integer; PItem, PMask, PPattern: Pointer; Source, Result: Array of MyRecord; Mask, Pattern: MyRecord; begin setlength(Result, Length(Source)); Mask.a = $FFFFFFFF; Mask.b = $FFFFFFFF; Mask.c = $00000000; Mask.d = $FFFFFFFF; Mask.e = $00000000; Mask.f = $FFFFFFFF; Mask.g = $FFFFFFFF; for i := 0 to High(Source) do begin PItem = @Source[i]; PMask = @Mask; PPattern = @Pattern; for j = 0 to 7 begin ItemResult = ItemResult or ((PPattern^ xor PItem^) and PMask^); Inc(PPattern); Inc(PMask); Inc(PItem); end if ItemResult = 0 then begin Result[ResultIndex] = Source[i]; Inc(ResultIndex); end end setlength(Result, ResultIndex); end |
Danach sollte die Datenmenge wesentlich kleiner sein, und der Rest müsste ziemlich flott gehen.
Das ist jetzt aber nur so hingetippt. Mehrere Minuten darf sowas auf gar keinen Fall dauern...
Für diesen Beitrag haben gedankt: Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 10.07.14 21:49
Hallo,
mit einer Maske hatte ich mir auch schon gedacht, aber ich habe es jetzt anders gelöst.
Ich erstelle ein Tupel, welche Dimension und welcher Wert.
Das saust nur so dahin.( 8 ms für 64 Werte aus 2 Mio , OK nicht eingetragen, aber das ist ja kein Akt)
Aber das Problem ist eher die Bestimmung der Anzahl der verschiedenen Werte je Dimension.
Deshalb der Vorschlag dictionary für jede Dimension.
Gruß Horst
Hier für 10^ 7 . Die 100 passenden sind in 35 ms gefunden.
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:
| Erstellen 178 ms SortFelder erstellen 92 ms Mischen 1115 ms Spannweite 388 ms 0 9 1 0 9 1 0 9 1 0 9 1 0 9 1 0 9 1 0 9 1 Gefundene 100 Suchen 35 ms |
Einloggen, um Attachments anzusehen!
Für diesen Beitrag haben gedankt: Boldar
|
|
Xion
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: Fr 11.07.14 12:56
Mal ein paar Gedanken zur algorithmischen Seite:
Da die Daten nicht sortiert sind, müssen in jedem Fall alle von Platte gelesen werden. Das ist höchst wahrscheinlich der teuerste Teil (inkl. Parsing) des Programms. Interessant wäre ein Profiling deines Programms, an welcher Stelle nun eigentlich die Zeit verbraucht wird (Import/Suche/Export). Ich gehe fast davon aus, dass 95% der Zeit für Import/Export benötigt werden.
Interessant wäre nun, wie oft sich die Daten ändern, bzw. das Verhältnis von neuen Daten zu Nutzerabfragen. Wenn die Daten sich nur selten ändern wäre eine Datenbank wohl das einfachste mit jeweils einem Index pro Koordinate. Effiziente Datenstrukturen und Suchverfahren gibt es dann gratis.
In einer unsortierten/unstrukturierten Liste nach den vorgegebenen Koordinaten zu suchen geht ebenfalls nicht besser als einfach alle durchzugucken. Allerdings sollten 1 Million * 5 Vergleiche eher im Bereich von wenigen Sekunden als Minuten liegen.
So wie dein Problem klingt hast du eine maximal dicht besetzte Matrix vor dir. Eine einfache 7D Matrix (bzw. selbst linearisiert) wäre daher wohl das einfachste und effizienteste zu erzeugen. Export ist damit schnellstmöglich (export matrix[a,b,*,d,*,f,g]), weil du garnichts suchen musst. Ist deine Matrix hinreichend dicht besetzt, ist es auch speichertechnisch sehr effizient (keine zusätzlichen Pointer, implizite Speicherung der Koordinaten). In Data Warehouses das Mittel der Wahl für sehr performante, sehr effiziente Verwaltung riesiger Datenmengen.
Um die Werte in Matrixform zu speichern, musst du 2x über deine Daten gehen. Erst die Schrittweite und Offset bestimmen (d.h. min und max) und dann deine Daten in das Array eintragen. Beides in einem Schritt ist nicht möglich, da du die Matrixzellen nicht bestimmen kannst ohne die Schrittweite zu kennen.
Auch hier: Wird das Programm mehrmals für die gleichen Daten benutzt, dann lohnt es sich, min/max oder gleich die 7D-Matrix zu speichern.
Die Bestimmung von min/max pro Koordinate ist exakt nur als Durchlauf aller Werte möglich. Du brauchst also 7*2*1 Million Vergleiche. Das dauert etwas, aber keine Minuten.
Willst du nur sehr wenige Schnitte berechnen, ginge es auch noch anders. Du liest deine Werte "blind" in eine 7D-Matrix ein und verwaltest pro Dimension eine Hashtabelle, welche Koordinate du in welche Zeile eingetragen hast. Das führt aber zu teuren Einfüge- und Such-Operationen und ich bin mir unsicher, ob das wirklich den einen Durchlauf für min/max Suche ausgleichen kann, denn Hashtabellen bilden auch einen Overhead.
Mein Fazit:
Faule Variante: Datenbank benutzen. Macht aber nur Sinn bei vielen Anfragen pro Datensatz, weil das Bilden der Datenbankindexe teuer ist.
Effiziente Variante: 7D-Matrix erzeugen mit zweimaligem Durchlauf durch die Daten. Macht aber nur Sinn, wenn deine Matrix dicht genug besetzt ist. Dann in jedem Fall maximal performant, auch für wenige Anfragen.
Einmal-Variante: Wenn du nur einmal einen Schnitt für deine Daten berechnen willst, dann binde den Filter direkt in den Import der Datei ein. Minimalen Speicherbedarf.
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
Für diesen Beitrag haben gedankt: Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 12.07.14 09:02
Hallo,
ich war wohl schwer von Kappee.
Ich habe mich gefragt, was der Vorteil der Bestimmung der Spannweite der Daten ist.
Boldar sortiert durch Zählen im zweiten Durchgang.
Aber die Schrittweite macht nur Sinn , wenn man weiß, dass der Abstand zweier Elemente auch k*Schrittweite ist.
Dann kann Boldar auf ein Feld [0..Endwert-Startwert) DIV Schrittweite] gehen und im zweiten Durchlauf das Vorkommen des jeweiligen Elementes hochzählen.
In einem dritten Durchgang könnte man dann ganz leicht eine aufsteigende sortierte Liste der Positionen der Werte erzeugen, so groß wir die Anzahl Elemente.
Dann würde es auch richtig schnell mit der Suche der Elemente mit 5 gleichen Koordinaten.
Ich gehe bald davon aus, dass die Speicherung und Anordnung der Daten das wirkliche Problem Boldars ist.
Gruß Horst.
Für diesen Beitrag haben gedankt: Boldar
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Di 15.07.14 03:59
Also, puuuh...
Vielen Dank erstmal für die vielen schnellen Antworten zu solch einem ja doch etwas speziellem Thema.
Ich bastele gerade mal an einer ersten Programmversion und werde dann mal Benchmarks machen, denke aber ich werde da auf dauer Xions Idee aufgreifen und eine Datenbank benutzen, in SQL bin ich da bewandert genug dass dann alles von der Datenbank machen zu lassen, und ich denke mal ich werde das performance-technisch eh nicht viel besser von Hand hinbekommen als ein darauf optimiertes DBMS.
Xions Idee war auf jedenfall richtig: Bis vor kurzem landete jeder Eintrag in einer eigenen Datei, da nahm das einlesen von der Platte natürlich enorme Zeit ein, aber auch nach umstieg auf (eine) xml-Datei immerhin noch die Hälfte - aber wir reden hier ja auch von einer Datei mit mehreren Millionen Zeichen, da stockt selbst Notepad++ beim einlesen (Ich hab die Datei mal angehängt)
Ich werde mich nochmal melden, sobald ich ein wenig rumprobiert habe.
Vielen Dank und lg
Boldar
Edit: mal überschlagen: selbst bei ~1kk Einträgen bleibt der Speicherbedarf ja im einstelligem mb-Bereich, d.h. durchaus noch in dem Bereich, wo problemlos Blöcke reservierbar sind. D.h. Speicher wird nicht das problem sein.
|
|
jaenicke
Beiträge: 19276
Erhaltene Danke: 1741
W11 x64 (Chrome, Edge)
Delphi 11 Pro, Oxygene, C# (VS 2022), JS/HTML, Java (NB), PHP, Lazarus
|
Verfasst: Di 15.07.14 16:56
Boldar hat folgendes geschrieben : | aber wir reden hier ja auch von einer Datei mit mehreren Millionen Zeichen, da stockt selbst Notepad++ beim einlesen (Ich hab die Datei mal angehängt) |
Das ging bei mir mit knapp 200 Millionen Zeichen (knapp 400 MiB als Unicode) in einem Registry-Export inkl. Parsing und Anzeige in einer VirtualTreeView in rund 4-5 Sekunden...
So kostspielig ist das eigentlich nicht, auch wenn XML natürlich einiges an Zusatzaufwand erfordert.
Für diesen Beitrag haben gedankt: Boldar
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Do 24.07.14 11:17
Also,
Ich bin jetzt soweit:
Das ist meine Klasse:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48:
| type TMesspunkt = record inttime, iterations: integer; value: int64; end; type TIntArray = array [0..1] of integer;
T9DPunkt = record x, y, z, p1, p2, px, py, pz, value: Int64; inttime, iterations: integer; class operator implicit (a: T9DPunkt):T9DPunktEx; class operator implicit (a: T9DPunktEx):T9DPunkt; class operator implicit (a: T9DPunkt):string; class operator Multiply (a: T9DPunkt; b: T9x9Matrix): T9DPunkt; class operator add (a, b: T9DPunkt):T9DPunkt; class operator subtract (a, b: T9DPunkt):T9DPunkt; public function sqr:T9DPunktEx; function sqrt:T9DPunktEx; function cubic:T9DPunktEx; function absp:T9DPunkt; end;
type TMessung = class private filename: string; points: TObjectList; strl: TStringlist; planes: array of array of array of array of array of array of array of array of TMesspunkt; planebase: T9DPunkt; l: T9DPunkt; function scalepoint (p: TMesspunkt):int64; public dx, dy, dz, dp1, dp2, dpx, dpy, dpz: TObjectList; icount, jcount: integer; planemin, planemax, planescalemin, planescalemax: int64; candraw: boolean; plane: array of array of TMesspunkt; scaleinttime: boolean; procedure loadfromfile (filename: string; pb1: TProgressbar); procedure toarray (pb1: TProgressbar); procedure toPlane (basepoint: T9DPunkt; dimension: T9Dbool); function getPoint (i, j: integer; basepoint: T9DPunkt; dimension: T9Dbool): TMesspunkt; function getbasePoint(i, j: integer; basepoint: T9DPunkt; dimension: T9Dbool): T9DPunkt; function getLength (basepoint: T9DPunkt; dimension: T9Dbool): TIntArray; function getcolor (i, j: integer): TColor; function getvalue (i, j: integer):int64; constructor create(); end; |
Damit lade ich die Datei in eine Liste:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126:
| procedure TMessung.loadfromfile(filename: string; pb1: TProgressbar); var i, startindex: integer; var s: string; var start: cardinal; var iterations, inttime, x, y, z, p1, p2, px, py, pz, value, mset, mvalue: integer; var mname, mcoord, comment, user, bquery, error: AnsiString; var posa: T9DPunkt; begin strl := TStringlist.Create; points := TObjectList.Create; strl.LoadFromFile(FileName); iterations:=0; inttime:=0; x:=0; y:=0; z:=0; p1:=0; p2:=0; px:=0; py:=0; pz:=0; value:=0; if (not assigned(strl)) then exit; if (strl.Count<5) then exit; pb1.Min:=0; pb1.Max:=strl.Count; pb1.Position:=0; bquery :=''; for I := 1 to strl.Count -2 do begin s := Trim(strl[i]); if (s.StartsWith('<points>')) then begin startindex := i; break; end; end; for I := startindex to strl.Count-2 do begin pb1.Position := i; if (i mod 10)=0 then begin application.ProcessMessages; end; s := Trim(strl[i]); if s.StartsWith('<iterations') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); iterations:=strtoint(trim(s)); end; if s.StartsWith('<inttime') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); inttime:=strtoint(trim(s)); end; if s.StartsWith('<x') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); x:=strtoint(trim(s)); end; if s.StartsWith('<y') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); y:=strtoint(trim(s)); end; if s.StartsWith('<z') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); z:=strtoint(trim(s)); end; if s.StartsWith('<p1') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); p1:=strtoint(trim(s)); end; if s.StartsWith('<p2') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); p2:=strtoint(trim(s)); end; if s.StartsWith('<px') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); px:=strtoint(trim(s)); end; if s.StartsWith('<py') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); py:=strtoint(trim(s)); end; if s.StartsWith('<pz') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); pz:=strtoint(trim(s)); end; if s.StartsWith('<value') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); value:=strtoint(trim(s)); end; if s.StartsWith('<p') then begin iterations:=0; inttime:=0; x:=0; y:=0; z:=0; p1:=0; p2:=0; px:=0; py:=0; pz:=0; value:=0; end; if s.StartsWith('</p>') then begin posa.x := x; posa.y := y; posa.z := z; posa.p1:= p1; posa.p2:= p2; posa.px:= px; posa.py:= py; posa.pz:= pz; posa.inttime := inttime; posa.iterations := iterations; posa.value := value; self.points.Add(T9DObject.create(posa)); end;
end; pb1.Position:=0; end; |
Damit lade ich die Liste in ein array:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157: 158: 159: 160: 161: 162: 163: 164: 165: 166: 167: 168: 169: 170: 171: 172: 173: 174: 175: 176: 177: 178: 179: 180: 181: 182: 183: 184: 185: 186: 187: 188: 189: 190: 191: 192: 193: 194: 195: 196: 197: 198: 199: 200: 201: 202: 203: 204: 205: 206:
| procedure TMessung.toarray(pb1: TProgressbar); var I, i2, i3: Integer; p, p2, pd, min, max, step: T9DPunkt; aval: int64; counter: integer; found: boolean; apoint: TMesspunkt; begin dx := TObjectlist.Create(true); dy := TObjectlist.Create(true); dz := TObjectlist.Create(true); dp1 := TObjectlist.Create(true); dp2 := TObjectlist.Create(true); dpx := TObjectlist.Create(true); dpy := TObjectlist.Create(true); dpz := TObjectlist.Create(true); min.x := maxint;min.y := maxint;min.z := maxint; min.p1:= maxint;min.p2:= maxint; min.px:= maxint;min.py:= maxint;min.pz:= maxint; max.x := 0;max.y := 0;max.z := 0; max.p1:= 0;max.p2:= 0; max.px:= 0;max.py:= 0;max.pz:= 0; step.x := maxint;step.y := maxint;step.z := maxint; step.p1:= maxint;step.p2:= maxint; step.px:= maxint;step.py:= maxint;step.pz:= maxint; pb1.Max := points.Count; pb1.Min := 0; pb1.Position := 0; counter :=0; for I := 0 to points.Count-1 do begin if (i mod 10)=0 then begin application.ProcessMessages; end; p := (points[i] as T9DObject).p; if (p.x < min.x) then min.x := p.x; if (p.y < min.y) then min.y := p.y; if (p.z < min.z) then min.z := p.z; if (p.p1< min.p1)then min.p1:= p.p1; if (p.p2< min.p2)then min.p2:= p.p2; if (p.px< min.px)then min.px:= p.px; if (p.py< min.py)then min.py:= p.py; if (p.pz< min.pz)then min.pz:= p.pz;
if (p.x > max.x) then max.x := p.x; if (p.y > max.y) then max.y := p.y; if (p.z > max.z) then max.z := p.z; if (p.p1> max.p1)then max.p1:= p.p1; if (p.p2> max.p2)then max.p2:= p.p2; if (p.px> max.px)then max.px:= p.px; if (p.py> max.py)then max.py:= p.py; if (p.pz> max.pz)then max.pz:= p.pz;
found := false; for i3:=0 to dx.count-1 do begin aval := (dx[i3] as TValue).data; if p.x = aval then begin found:=true;break; end else if (abs(aval-p.x ))<step.x then step.x :=(abs(aval-p.x )); end; if not found then dx.Add(TValue.create(p.x)); found := false; for i3:=0 to dy.count-1 do begin aval := (dy[i3] as TValue).data; if p.y = aval then begin found:=true;break; end else if (abs(aval-p.y ))<step.y then step.y :=(abs(aval-p.y )); end; if not found then dy.Add(TValue.create(p.y)); found := false; for i3:=0 to dz.count-1 do begin aval := (dz[i3] as TValue).data; if p.z = aval then begin found:=true;break; end else if (abs(aval-p.z ))<step.z then step.z :=(abs(aval-p.z )); end; if not found then dz.Add(TValue.create(p.z)); found := false; for i3:=0 to dp1.count-1 do begin aval := (dp1[i3] as TValue).data; if p.p1 = aval then begin found:=true;break; end else if (abs(aval-p.p1))<step.p1 then step.p1:=(abs(aval-p.p1)); end; if not found then dp1.Add(TValue.create(p.p1)); found := false; for i3:=0 to dp2.count-1 do begin aval := (dp2[i3] as TValue).data; if p.p2 = aval then begin found:=true;break; end else if (abs(aval-p.p2))<step.p2 then step.p2:=(abs(aval-p.p2)); end; if not found then dp2.Add(TValue.create(p.p2)); found := false; for i3:=0 to dpx.count-1 do begin aval := (dpx[i3] as TValue).data; if p.px = aval then begin found:=true;break; end else if (abs(aval-p.px))<step.px then step.px:=(abs(aval-p.px)); end; if not found then dpx.Add(TValue.create(p.px)); found := false; for i3:=0 to dpy.count-1 do begin aval := (dpy[i3] as TValue).data; if p.py = aval then begin found:=true;break; end else if (abs(aval-p.py))<step.py then step.py:=(abs(aval-p.py)); end; if not found then dpy.Add(TValue.create(p.py)); found := false; for i3:=0 to dpz.count-1 do begin aval := (dpz[i3] as TValue).data; if p.pz = aval then begin found:=true;break; end else if (abs(aval-p.pz))<step.pz then step.pz:=(abs(aval-p.pz)); end; if not found then dpz.Add(TValue.create(p.pz)); pb1.Position := pb1.Position+1; end; l.x :=dx.Count ;l.y :=dy.Count ;l.z :=dz.Count ; l.p1:=dp1.Count;l.p2:=dp2.Count; l.px:=dpx.Count;l.py:=dpy.Count;l.pz:=dpz.Count; setlength (planes, dx.Count, dy.Count, dz.Count,dp1.Count,dp2.Count,dpx.Count,dpy.Count,dpz.Count); for I := 0 to points.Count-1 do begin p := (points[i] as T9DObject).p; apoint.inttime := p.inttime; apoint.iterations:=p.iterations; apoint.value := p.value; pd := p - min; planes [pd.x div step.x, pd.y div step.y, pd.z div step.z, pd.p1 div step.p1, pd.p2 div step.p2, pd.px div step.px, pd.py div step.py, pd.pz div step.pz]:= apoint; end; pb1.position:=0; end; |
und damit das Array in eine Fläche
Delphi-Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25:
| procedure TMessung.toPlane(basepoint: T9DPunkt; dimension: T9Dbool); var i, j: integer; var lng: TIntarray; var svalue: int64; begin candraw:=false; i:=0;j:=0; planemin := maxint; planemax:=0; planescalemin := maxint; planescalemax:=0; lng := getLength(basepoint, dimension); icount := lng[0];jcount := lng[1]; setlength(plane, icount, jcount); for i := 0 to icount-1 do for j := 0 to jcount-1 do begin plane[i, j]:=self.getpoint(i, j, basepoint, dimension); svalue := self.scalepoint(plane[i, j]); if plane[i, j].value>planemax then planemax := plane[i, j].value; if plane[i, j].value<planemin then planemin := plane[i, j].value; if svalue>planescalemax then planescalemax := svalue; if svalue<planescalemin then planescalemin := svalue; end; if planemin=planemax then inc(planemax); candraw:=true; end; |
Die ersten zwei Schritte dauern nun noch relativ lange, wenn da jemandem noch optimierungen insbesondere der String-bearbeitung sowie der schrittweite-bestimmung einfallen, Wäre das gut.
Ausserdem stellt sich mir die Frage, inwiefern sich hier paralellisierung lohnt und wie man das angeht. Das Zielsystem verfügt über 8 (echte) Kerne. Ich arbeite mit Delphi XE3, ich habe das project mal angehängt, und werde gleich noch Beispieldaten anhängen.
lg Boldar
Edit: Ich denke mal, man könnte einiges an Performance gewinnen, wenn man die Listen dx, dy... dpz anders implementiert, sodass man eine schnellere Methode hat, herauszufinden ob das element existiert. Evtl. kann man da auch mit Inline-asm noch was rausholen?
Einloggen, um Attachments anzusehen!
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Do 24.07.14 20:24
Hallo,
nur eine kleine Frage:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20:
| <root> <filename>Messung</filename> <Startx>0</Startx> <Starty>0</Starty> <Startz>0</Startz> <Startpx>0</Startpx> <Startpy>0</Startpy> <Startpz>0</Startpz> <Stepx>100</Stepx> <Stepy>100</Stepy> <Stepz>30</Stepz> <Steppx>100</Steppx> <Steppy>100</Steppy> <Steppz>100</Steppz> <Stepsx>100</Stepsx> <Stepsy>100</Stepsy> <Stepsz>2</Stepsz> <Stepspx>1</Stepspx> <Stepspy>1</Stepspy> <Stepspz>1</Stepspz> |
Wozu Step bestimmen, wenn alles vorgegeben ist?
x startet mit 0 stepx = 100 Steppx = 100 -> Start bei 0 Schrittweite 100 und das 100 mal von 0 .. 9900// [0..99]*100
Ich dachte die Daten seinen unsortiert, oder hast Du eine Beispielausgabe angehängt?
Wenn Du es beim Einlesen eilig hast nimm doch was von jaenicke:
SJ MMF File Reader 0.2 - Schneller Textdatei Reader
Dann kannst Du einfach zeileweise einlesen.
Quelltext 1: 2: 3: 4: 5:
| statt s := Trim(strl[i]); eben FileReader.Readln(s); s := trim(s); |
Warum arbeitest Du mit zweimal mit Substring und nicht Pos, PosEx und copy,
Aber ich glaube, alles jedesmal durchzukauen, obwohl man schon was gefunden hat ( Du findest "<inttime>" testest aber munter alle Möglichkleiten weiter durch.
Dann kann man mit einer dummy Schleife, die nur einmal durchlaufen wird, umgehen ( BREAK ersetzt GOTO )
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52:
| s := Trim(strl[i]); if s.StartsWith('<iterations') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); iterations:=strtoint(trim(s)); end; if s.StartsWith('<inttime') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); inttime:=strtoint(trim(s)); end; if s.StartsWith('<value') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); value:=strtoint(trim(s)); BREAK; end; if s.StartsWith('<p') then begin s := Trim(strl[i]); REPEAT if s.StartsWith('<iterations') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); iterations:=strtoint(trim(s)); BREAK; end; if s.StartsWith('<inttime') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); inttime:=strtoint(trim(s)); BREAK; end; if s.StartsWith('<value') then begin s:=s.Substring(s.IndexOf('>')+1); s:= s.Substring(0, s.IndexOf('<')); value:=strtoint(trim(s)); BREAK; end; UNTIL TRUE; if s.StartsWith('<p') then begin |
Ich kann mir nicht vorstellen, dass die Daten aka ein Messwert nicht chronologisch und koordinatenmäßig sortiert sind.
Ich will sagen, dass der Aufbau der Daten immer:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| <p> <iterations>1</iterations> <inttime>50</inttime> <x>6200</x> <y>900</y> <z>0</z> <p1>0</p1> <p2>0</p2> <px>0</px> <py>0</py> <value>0</value> </p> |
in dieser Reihenfolge ist und man deshalb nur einen Messwert immer gleich verarbeiten kann.
1.Zeile = iterations ,wenn nicht dann Fehler
2.Zeile = IntTime ,wenn nicht dann Fehler
etc..
Also zumindest 10 Zeilen im Aufbau konstant sind.
Gruß Horst
EDIT
Wie lange dauert das Einlesen überhaupt bei Dir , 100'000 Messwerte/ s ??
Für diesen Beitrag haben gedankt: Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 25.07.14 10:16
Hallo,
eine Variante zum Einlesen speziell Deiner Daten:
Das sind fast 300000 Punkte/s oder Messwerte/s, wenn die Datei schon im Cache ist.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: 152: 153: 154: 155: 156: 157:
| program TestStrToInt; {$Apptype Console} uses sysutils,strUtils,classes;
type t9DPunkt = record x,y,z, p1,p2, px,py,pz, intTime,iterations, value : Integer; end;
T9DObject = class(TObject) p: T9DPunkt; constructor create (pp: T9DPunkt); end;
var T0,T1: tDateTime; strl : TStringList; points : TList;
constructor T9DObject.create(pp: T9DPunkt); begin inherited create; self.p := pp; end;
procedure ExtractS(var s: AnsiString; const Suchtext:AnsiString); var sBegin,SEnd: integer; begin sBegin := length(Suchtext)+2+1; sEnd := PosEx('<',s,sBegin); s := trim(copy(s,sBegin,sEnd-SBegin)); end;
procedure loadfromfile(filename: string); var i, startindex : integer; var s: string;
var posa: T9DPunkt; begin strl := TStringlist.Create; points := TList.Create; strl.LoadFromFile(FileName); if (not assigned(strl)) then exit; if (strl.Count<5) then exit; for I := 1 to strl.Count -2 do begin s := Trim(strl[i]); if Pos(s,'<points>') = 1 then begin startindex := i; break; end; end; for I := startindex to strl.Count-2 do begin s := Trim(strl[i]); With posa do begin IF Pos('<',s) = 1 then begin case s[2] of 'i': begin IF Pos('inttime',s)=2 then begin ExtractS(s,'inttime'); inttime:=strtoint(s); end; IF Pos('iterations',s)=2 then begin ExtractS(s,'iterations'); iterations:=strtoint(s); end; end; 'p' : case s[3] of '1' : begin ExtractS(s,'p1'); p1:=strtoint(s); end; '2' : begin ExtractS(s,'p2'); p2:=strtoint(s); end; 'x' : begin ExtractS(s,'px'); pz:=strtoint(s); end; 'y' : begin ExtractS(s,'py'); py:=strtoint(s); end; 'z' : begin ExtractS(s,'pz'); pz:=strtoint(s); end; else end; 'v' :IF Pos('value',s)= 2 then begin ExtractS(s,'value'); value:=strtoint(s); end; 'x' :begin ExtractS(s,'x'); x:=strtoint(s); end; 'y' :begin ExtractS(s,'y'); y:=strtoint(s); end; 'z' :begin ExtractS(s,'z'); z:=strtoint(s); end; else end; end; end; if Pos('<p',s)=1 then with posa do begin iterations:=0; inttime:=0; x:=0; y:=0; z:=0; p1:=0; p2:=0; px:=0; py:=0; pz:=0; value:=0; end; if Pos('</p>',s)=1 then begin points.Add(T9DObject.create(posa)); end; end; end;
begin T0 := time; loadfromfile('test.xml.txt'); T1 := time; writeln('Laufzeit ',(T1-T0)*86400000.0:0:0,'ms'); writeln('Anzahl Zeilen ',strl.count); Writeln('Anzahl Punkte ',points.count); strl.free; Points.free; end. |
Gruß Horst
EDIT
Turbo Delphi schafft das dann in 28 ms
Zuletzt bearbeitet von Horst_H am Fr 25.07.14 17:13, insgesamt 1-mal bearbeitet
Für diesen Beitrag haben gedankt: Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Fr 25.07.14 16:42
Hallo,
gute Güte , ich habe es für TurboDelphi geändert.
Der Casus cnactus beim einlesen ist ausschliesslich! diese völlig unsinnige Verwendung der Progressbar.
Ohne Progressbar lädt Delphi das in 30 ms, mit (alle 10 Zeilen ) in 664 ms= 95,5% der Rechenzeit nur für die Fortschrittsanzeige.
Vielleicht sollte man lieber gettickcount nutzen und alle 10000 Zeilen mal testen ob 250 ms seit dem letzten Progressbar-neuzeichnen vergangen sind, damit sich dann auch lohnt.
s.StartsWith und s.??? kennt Turbo delphi nicht
Mit strings ist Freepascal etwas lahm...
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38:
| implementation
uses strUtils;
procedure TMessung.loadfromfile(filename: string; pb1: TProgressbar); ... for I := startindex to strl.Count-2 do begin if i MOD 32768 =0 then begin pb1.Position := i; application.ProcessMessages; end; s := Trim(strl[i]); repeat if Pos('<iterations',s)=1 then begin sBegin := Pos('>',s)+1; sEnd := PosEx('<',s,sBegin); s := copy(s,sBegin,sEnd-sBegin); iterations:=strtoint(trim(s)); BREAK; end; ..... if Pos('<value' ,s)=1 then begin sBegin := Pos('>',s)+1; sEnd := PosEx('<',s,sBegin); s := copy(s,sBegin,sEnd-sBegin); value:=strtoint(trim(s)); end; until true; if Pos('<p' ,s)=1 then begin ... |
Gruß Horst
P.S:
Das Repeat break bringt nur ~6 ms schlecht messbar mit so wenig Daten ( die hätte man eher packen sollen ...)
Für diesen Beitrag haben gedankt: Boldar
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Di 29.07.14 17:43
Hallo,
jetzt wollte ich mal jaenicke SJ MMF File Reader 0.2 - Schneller Textdatei Reader testen, aber Pustekuchen:
Quelltext 1: 2:
| 3145731 229832 19149 {Text Zeile Vorher =} "<px>0</px>" 3145729 3285939 1048576 |
Statt 20000 Messwerte sind es 19149 und es wird abgebrochen bei Position 3145731 von 3285939. Die vorhergehende Position war 3145729.Das entspricht Zeile 229832.
BufferSize ist 1024*1024 = 1048576.
FileReader.Readln(s) liest immer einen Leerstring.
Also innerhalb dieser Zeilen:
Quelltext 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12:
| <p> <iterations>1</iterations> <inttime>50</inttime> <x>4800</x> <y>9100</y> <z>30</z> <p1>0</p1> <p2>0</p2> <px>0</px> <py>0</py> <value>0</value> </p> |
Position Vorher = 3145729 = 3*BufferSize+1.
Es sieht so aus, als würde das #13#10 der Position vorher genau auf der Buffergrenze gelegen haben.
Gruß Horst
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103:
| uses strUtils,SJMmfFileReader,main; function ExtractSToInt(var s:AnsiString; const Suchtext:AnsiString):integer; var sBegin,SEnd: integer; begin sBegin := length(Suchtext)+2 +1; sEnd := PosEx('<',s,sBegin); s :=copy(s,sBegin,sEnd-SBegin); result := StrToInt(trim(s)); end;
procedure TMessung.loadfromfile1(filename: string; pb1: TProgressbar); label WegHier; var Reader :TSJMmfFileReader; var T1,T0: TDateTime; var s,altS: Ansistring; var BufposZuvor : Int64; var i:integer; var posa: T9DPunkt; begin T0:= Time; Reader :=TSJMmfFileReader.Create(filename); points := TObjectList.Create; i := 0; while Reader.Position<Reader.Size do begin Reader.readln(s); s := Trim(s); if Pos('<points>' ,s)=1 then break; inc(i); end;
main.Form2.mout.Clear; while Reader.Position<Reader.Size do begin BufposZuvor:= Reader.Position; altS := s; Reader.readln(s); s := Trim(s); if length(s)< 3 then begin main.Form2.mout.lines.add(Format('%d %d %d "%s"',[Reader.Position,i,Points.COunt,altS])); main.Form2.mout.lines.Add(Format('%d %d',[BufposZuvor,reader.BufferSize])); application.ProcessMessages; GOTO WegHier; end;
With posa do begin IF s[1] = '<' then begin case s[2] of '/': Begin if Pos('</p>',s)=1 then self.points.Add(T9DObject.create(posa)) else IF Pos('</points>',s)=1 then GOTO WegHier end; 'i': begin IF Pos('inttime',s)=2 then inttime:= ExtractSToInt(s,'inttime') Else IF Pos('iterations',s)=2 then iterations:= ExtractSToInt(s,'iterations'); end; 'p' : case s[3] of '>' : FillChar(posa,SizeOf(posa),#0); '1' : p1 := ExtractSToInt(s,'p1'); '2' : p2 := ExtractSToInt(s,'p2'); 'x' : px := ExtractSToInt(s,'px'); 'y' : py := ExtractSToInt(s,'py'); 'z' : pz := ExtractSToInt(s,'pz'); else end; 'v' :IF Pos('value',s)= 2 then value:=ExtractSToInt(s,'value'); 'x' : x:=ExtractSToInt(s,'x'); 'y' : y:=ExtractSToInt(s,'y'); 'z' : z:=ExtractSToInt(s,'z'); else end; end; end; inc(i); end; WegHier: T1 := time; PointsCnt := Points.Count; showmessage (Format('Ladezeit %0.0f ms %d %d',[LadeZeit*86400000.0,PointsCnt,i]));
pb1.Position:=0; reader.free; Ladezeit := T1-t0; end; |
EDIT:
Wenn man Buffersize um 64KB reduziert werden 20000 Zeilen eingelesen.Aber das ist ja keine Hilfe..
|
|
Boldar
Beiträge: 1555
Erhaltene Danke: 70
Win7 Enterprise 64bit, Win XP SP2
Turbo Delphi
|
Verfasst: Sa 02.08.14 19:18
Horst_H hat folgendes geschrieben : | Hallo,
gute Güte , ich habe es für TurboDelphi geändert.
Der Casus cnactus beim einlesen ist ausschliesslich! diese völlig unsinnige Verwendung der Progressbar.
Ohne Progressbar lädt Delphi das in 30 ms, mit (alle 10 Zeilen ) in 664 ms= 95,5
er Rechenzeit nur für die Fortschrittsanzeige.
Vielleicht sollte man lieber gettickcount nutzen und alle 10000 Zeilen mal testen ob 250 ms seit dem letzten Progressbar-neuzeichnen vergangen sind, damit sich dann auch lohnt.
s.StartsWith und s.??? kennt Turbo delphi nicht
Mit strings ist Freepascal etwas lahm...
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38:
| implementation
uses strUtils;
procedure TMessung.loadfromfile(filename: string; pb1: TProgressbar); ... for I := startindex to strl.Count-2 do begin if i MOD 32768 =0 then begin pb1.Position := i; application.ProcessMessages; end; s := Trim(strl[i]); repeat if Pos('<iterations',s)=1 then begin sBegin := Pos('>',s)+1; sEnd := PosEx('<',s,sBegin); s := copy(s,sBegin,sEnd-sBegin); iterations:=strtoint(trim(s)); BREAK; end; ..... if Pos('<value' ,s)=1 then begin sBegin := Pos('>',s)+1; sEnd := PosEx('<',s,sBegin); s := copy(s,sBegin,sEnd-sBegin); value:=strtoint(trim(s)); end; until true; if Pos('<p' ,s)=1 then begin ... |
Gruß Horst
P.S:
Das Repeat break bringt nur ~6 ms schlecht messbar mit so wenig Daten ( die hätte man eher packen sollen ...) |
Tatsächlich ... Hatte das früher gecheckt und bemerkt, dass die Progressbar keinen unterschied macht, da war der Rest wohl noch zu langsam... irgendwie ist dann das Progressbar updaten aus der Modulo-If-klausel rausgerutscht.
hab das jetzt geändert und bin zusammen mit den Vorschlägen von Horst_H soweit optimiert, dass selbst die größten vorstellbaren daten (eine 500mb Datei) in ~20s gehen.
Vielen dank an alle, die sich hier Mühe gemacht haben!
Edit:
Xion hat folgendes geschrieben : | Mal ein paar Gedanken zur algorithmischen Seite:
Da die Daten nicht sortiert sind, müssen in jedem Fall alle von Platte gelesen werden. Das ist höchst wahrscheinlich der teuerste Teil (inkl. Parsing) des Programms. Interessant wäre ein Profiling deines Programms, an welcher Stelle nun eigentlich die Zeit verbraucht wird (Import/Suche/Export). Ich gehe fast davon aus, dass 95
er Zeit für Import/Export benötigt werden.
Interessant wäre nun, wie oft sich die Daten ändern, bzw. das Verhältnis von neuen Daten zu Nutzerabfragen. Wenn die Daten sich nur selten ändern wäre eine Datenbank wohl das einfachste mit jeweils einem Index pro Koordinate. Effiziente Datenstrukturen und Suchverfahren gibt es dann gratis. -->Ja, das einlesen verbraucht etwa die Hälfte der zeit
In einer unsortierten/unstrukturierten Liste nach den vorgegebenen Koordinaten zu suchen geht ebenfalls nicht besser als einfach alle durchzugucken. Allerdings sollten 1 Million * 5 Vergleiche eher im Bereich von wenigen Sekunden als Minuten liegen.
So wie dein Problem klingt hast du eine maximal dicht besetzte Matrix vor dir. Eine einfache 7D Matrix (bzw. selbst linearisiert) wäre daher wohl das einfachste und effizienteste zu erzeugen. Export ist damit schnellstmöglich (export matrix[a,b,*,d,*,f,g]), weil du garnichts suchen musst. Ist deine Matrix hinreichend dicht besetzt, ist es auch speichertechnisch sehr effizient (keine zusätzlichen Pointer, implizite Speicherung der Koordinaten). In Data Warehouses das Mittel der Wahl für sehr performante, sehr effiziente Verwaltung riesiger Datenmengen.
Um die Werte in Matrixform zu speichern, musst du 2x über deine Daten gehen. Erst die Schrittweite und Offset bestimmen (d.h. min und max) und dann deine Daten in das Array eintragen. Beides in einem Schritt ist nicht möglich, da du die Matrixzellen nicht bestimmen kannst ohne die Schrittweite zu kennen.
Auch hier: Wird das Programm mehrmals für die gleichen Daten benutzt, dann lohnt es sich, min/max oder gleich die 7D-Matrix zu speichern. --> Das ist halt der Punkt - Min/Max bestimmung ist einfach einmal durchgehen. Für die Schrittweite muss ich aber für jeden Punkt die Differenz zu jedem anderem berechnen, da die Werte ja unsortiert sein können. D.h. quadratische laufzeit.
Die Bestimmung von min/max pro Koordinate ist exakt nur als Durchlauf aller Werte möglich. Du brauchst also 7*2*1 Million Vergleiche. Das dauert etwas, aber keine Minuten.
Willst du nur sehr wenige Schnitte berechnen, ginge es auch noch anders. Du liest deine Werte "blind" in eine 7D-Matrix ein und verwaltest pro Dimension eine Hashtabelle, welche Koordinate du in welche Zeile eingetragen hast. Das führt aber zu teuren Einfüge- und Such-Operationen und ich bin mir unsicher, ob das wirklich den einen Durchlauf für min/max Suche ausgleichen kann, denn Hashtabellen bilden auch einen Overhead.
Mein Fazit:
Faule Variante: Datenbank benutzen. Macht aber nur Sinn bei vielen Anfragen pro Datensatz, weil das Bilden der Datenbankindexe teuer ist. -->Eben, da dauert das Einlesen schon zu lange
Effiziente Variante: 7D-Matrix erzeugen mit zweimaligem Durchlauf durch die Daten. Macht aber nur Sinn, wenn deine Matrix dicht genug besetzt ist. Dann in jedem Fall maximal performant, auch für wenige Anfragen. -->Methode der Wahl
Einmal-Variante: Wenn du nur einmal einen Schnitt für deine Daten berechnen willst, dann binde den Filter direkt in den Import der Datei ein. Minimalen Speicherbedarf. |
|
|
Horst_H
Beiträge: 1653
Erhaltene Danke: 243
WIN10,PuppyLinux
FreePascal,Lazarus
|
Verfasst: Sa 02.08.14 21:19
Hallo,
gut, das es jetzt funktioniert.Mal eine Variante mit normalem Textfile, weil eine Stringliste ja auch Platz und Zeit braucht.
Deine Beispieldatei wurde SJFileReader in 500 ms( 36 ms 2.ter Durchgang ) eingelesen und Textfile waren es 550 ms ( 39 ms 2.ter Durchgang ).
Strlist dauert 46 ms im 2.ten Durchgang. Ich habe nur zwei gleiche Dateien unterschiedlichen Namens, und neustarten wollte ich nicht.
Hier in messung.pas die ersten Zeilen
Du kannst ja dann selbst einen Vergleich starten.
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148:
| implementation
{$IFDEF ShowLastLines} main, {$EndIf} strUtils;
function ExtractSToInt(var s:AnsiString; const Suchtext:AnsiString):integer; var sBegin,SEnd: integer; begin sBegin := length(Suchtext)+2 +1; sEnd := PosEx('<',s,sBegin); s :=copy(s,sBegin,sEnd-SBegin); result := StrToInt(trim(s)); end;
procedure TMessung.loadfromfile(filename: string; pb1: TProgressbar); {$IFDEF ShowLastLines} type datrec = record rcnt, pCnt: cardinal; st : string; end;
const cRows = 20; var tempDat : array[0..cRows-1] of datRec; ldx:integer; {$ENDIF}
var posa: T9DPunkt; Reader :textfile; inBuf : array of byte; s: Ansistring; T1,T0: TDateTime; rowcnt:integer;
begin T0:= Time; Assign(Reader,filename); setlength(InBuf,64*1024); SetTextBuf(Reader,InBuf[0],length(InBuf)); try reset(Reader); except showmessage ('Datei laesst sich nicht oeffnen '); end; points := TObjectList.Create; rowcnt := 0; while Not(EOF(Reader)) do begin readln(Reader,s); s := Trim(s); if Pos('<points>' ,s)=1 then break; inc(rowcnt); end;
while Not(EOF(Reader)) do begin readln(Reader,s);
IF length(s)< 3 then BREAK; inc(rowcnt);
{$IFDEF ShowLastLines} with tempDat[ldx] do begin rCnt := rowcnt; pCnt:= Points.Count; st := s; end; inc(ldx); IF ldx>= cRows then ldx:= 0; {$ENDIF}
s := Trim(s); With posa do begin IF s[1] = '<' then begin case s[2] of '/': Begin if Pos('</p>',s)=1 then self.points.Add(T9DObject.create(posa)) else IF Pos('</points>',s)=1 then BREAK; end; 'i': begin IF Pos('inttime',s)=2 then inttime:= ExtractSToInt(s,'inttime') Else IF Pos('iterations',s)=2 then iterations:= ExtractSToInt(s,'iterations'); end; 'p' : case s[3] of '>' : FillChar(posa,SizeOf(posa),#0); '1' : p1 := ExtractSToInt(s,'p1'); '2' : p2 := ExtractSToInt(s,'p2'); 'x' : px := ExtractSToInt(s,'px'); 'y' : py := ExtractSToInt(s,'py'); 'z' : pz := ExtractSToInt(s,'pz'); else end; 'v' :IF Pos('value',s)= 2 then value:=ExtractSToInt(s,'value'); 'x' : x:=ExtractSToInt(s,'x'); 'y' : y:=ExtractSToInt(s,'y'); 'z' : z:=ExtractSToInt(s,'z'); else end; end; end; end;
T1 := time; {$IFDEF ShowLastLines} with main.Form2.mout.Lines do begin clear; For rowcnt := 0 to cRows-1 do with tempDat[rowcnt] do Add(Format('ZeilNr %d Messwerte %d "%s"',[rcnt,pCnt,st])); Add(''); end; {$ENDIF} PointsCnt := Points.Count; pb1.Position:=0; CloseFile(reader); Ladezeit := T1-t0;
showmessage(Format('Ladezeit %0.0f ms %d %d',[LadeZeit*86400000.0,PointsCnt,rowcnt])); end; |
Gruß Horst
|
|
|