![]() |
fast array search with delphi
mein code sieht ungefähr so aus :
Delphi-Quellcode:
vector = record
prev: integer; sx,sy: word; ex,ey: word; next: integer; status: boolean; end; V : array of vector; /// ... im array befinden sich ~ 1 mio vectoren ich benötige eine ultra schnelle suche um mir alle Vector-indices auszugeben die : zb. sx:= 34 und sy:= 50 haben oder eine Suche für : ex:= 45; ey:=50; eine Suche über alle Elemnte in meinem array ist nicht akzeptabel. kann man etwas wie ![]() |
AW: fast array search with delphi
Hallo,
Dann musst du das Array vorher sortieren. Sonst kommst du nicht drumrum das ganze Array jedes mal zu durchsuchen. |
AW: fast array search with delphi
Zitat:
Delphi-Quellcode:
Dummerweise ist die Sortierung immer nur auf eine Suchanfrage beschränkt (hier sy,sy). Wenn man nach ex,ey suchen möchte, muss eine andere Sortierung vorliegen. Als Lösung aus diesem Dilemma bietet sich eine Indizierung des Vector-Arrays an. Man macht dann einen Index für sx,sy und einen für ex,ey. Sinnvollerweise baut man da gleich die entsprechenden Klassen, die das Ganze kapseln (die globalen Variablen waren hoffentlich nur als Beispiel gedacht!).TArray.Sort<vector>(V, TDelegatedComparer<vector>.Create( function(const Left, Right: vector): Integer begin result := CompareValue(Left.sx, Right.sx); if result = EqualsValue then result := CompareValue(Left.sy, Right.sy); end)); Du bekommst allerdings Probleme, wenn sich die Daten in den Vektoren (oder das Vector-Array selbst) ständig ändern. Dann müsste die Sortierung jedesmal mitgeführt werden. Ohne eine umfassendere Beschreibung des eigentlichen Problems ist da eine belastbare Antwort schwierig. |
AW: fast array search with delphi
der code kommt von :
![]() das problem liegt in der procedure :
Delphi-Quellcode:
bei einer bitmap mit 4000x4000 pixel und ggf. 1 mio black pixel( Vnun) dauert die procedure simplifyvector ~ 1e6 * 1e6 operationen ... gleichbedeutend mit einem blue screen .
procedure simplifyvector;
var m,m2: integer; begin for m := 1 to Vnum do for m2 := m + 1 to Vnum do begin if equalvectors(m,m2) then removevectors(m,m2); end; end; |
AW: fast array search with delphi
Das Hauptproblem ist einen guten und effizienten Algorithmus für die Vektorisierung zu finden.
Nicht ohne Grund kann Vektorisierungssoftware über 2000 Euro kosten. Würde man das Bild in 8 * 8 Kacheln unterteilen und dann jede Kachel einzeln in Vektoren überführen, dann könnte man viel Zeit sparen. Anschliessend müsste man die richtungsgleichen Vektoren an den Grenzen vereinigen. |
AW: fast array search with delphi
Der Algorithmus ist wirklich alles andere als effizient - sowohl in der Laufzeit, als auch im Speicherverbrauch.
|
AW: fast array search with delphi
Ich habe mir den Algorithmus auch mal näher angeschaut.
Die zeitintensive procedure simplifyvector kann entfallen, wenn addsquarevector vorher auf equalpoints prüft und nur nicht vorhandene Werte in die V-Liste aufnimmt, also nur, wenn IndexOfVector minus 1 ist.
Delphi-Quellcode:
function IndexOfVector (const sx, sy, ex, ey: integer): integer;
var M: integer; begin Result:= -1; for M:= 1 to VNum do if equalpoints (sx, sy, V[M].sx, V[M].sy) then if equalpoints (ex, ey, V[M].ex, V[M].ey) then begin Result:= M; Break; end; end; |
AW: fast array search with delphi
Zitat:
Die Methode AddSquareVector erzeugt ja gerade eine verkette Liste von vier Vektoren, die ein Quadrat um den schwarzen Punkt bilden. Liegen zwei schwarze Punkte nebeneinander, werden die überlappenden beiden Vektoren entfernt und die beiden Quadrate zu einem Rechteck verbunden (jetzt sechs Vektoren). Das geht dann so weiter, bis die schwarzen Flächen von Ketten vieler kurzer Vektoren umschlossen sind. Im dritten Schritt werden dann die kolinearen Vektoren zusammengefasst. |
AW: fast array search with delphi
Man könnte aber auch eine generische TList verwenden, statt dem Array ... equivalent zu dem schongezeigten TArray.Sort<vector>
|
AW: fast array search with delphi
ich bin dabei eine LookUptabelle für die matching-vektoren zu bauen, leider geht
VLookUp = array of array of TIntgerlist nicht, da ich im ersten Schritt setlength(VLookUp, imagesize_x, imagesize_y); bei einem Bild mit 2000 x 2000 pixel 4 mio IntegerListen im Speicher anlegen müsste ... mein Plan : SimplifyVectorEXT benötigt 4E6 *~ 4E3 zugriffe , immerhin um den Faktor 1000x schneller :-D procedure SimplifyVectorEXT; var m, m2: integer; begin for m....... for m2 := getbestminrange(m) to getbestmaxrange(m) // ich muss nur +- 1 Zeile absuchen !!!! begin if EqualVectors(m, m2) then RemoveVectors(m, m2); end; end; |
AW: fast array search with delphi
Zitat:
|
AW: fast array search with delphi
Delphi-Quellcode:
Ob so aber tatsächlich eine Zeitersparnis entsteht, müßte man erst ausprobieren.:gruebel:function equalpoints(p1x, p1y, p2x, p2y: integer): boolean; begin Result:= ((p1x = p2x) and (p1y = p2y)); end; function IndexOfVector(const sx, sy, ex, ey: integer): integer; var M: integer; begin Result:= 0; for M:= 1 to VNum-1 do if equalpoints (sx, sy, V[M].sx, V[M].sy) then if equalpoints (ex, ey, V[M].ex, V[M].ey) then begin Result:= M; Break; end; end; procedure removevector(mm, mm2: integer); var P, N: integer; begin P:= V[mm].prev; V[P].next:= V[mm2].next; N:= V[mm2].next; V[N].prev:= P; end; procedure removevectors(M, M2: integer); begin removevector(M, M2); removevector(M2, M); V[M].status:= -1; V[M2].status:= -1; end; procedure addsquarevector(J, K: integer); var M: integer; begin Vnum:= Vnum + 1; V[Vnum].prev:= Vnum + 3; V[Vnum].sx:= J; V[Vnum].sy:= K; V[Vnum].ex:= J + 1; V[Vnum].ey:= K; V[Vnum].next:= Vnum + 1; V[Vnum].status:= 0; M:= IndexOfVector (V[Vnum].sx, V[Vnum].sy, V[Vnum].ex, V[Vnum].ey); if M <> 0 then begin removevectors(M, Vnum); Vnum:= Vnum - 1 end; Vnum:= Vnum + 1; V[Vnum].prev:= Vnum - 1; V[Vnum].sx:= J + 1; V[Vnum].sy:= K; V[Vnum].ex:= J + 1; V[Vnum].ey:= K + 1; V[Vnum].next:= Vnum + 1; V[Vnum].status:= 0; M:= IndexOfVector (V[Vnum].sx, V[Vnum].sy, V[Vnum].ex, V[Vnum].ey); if M <> 0 then begin removevectors(M, Vnum); Vnum:= Vnum - 1 end; Vnum:= Vnum + 1; V[Vnum].prev:= Vnum - 1; V[Vnum].sx:= J + 1; V[Vnum].sy:= K + 1; V[Vnum].ex:= J; V[Vnum].ey:= K + 1; V[Vnum].next:= Vnum + 1; V[Vnum].status:= 0; M:= IndexOfVector (V[Vnum].sx, V[Vnum].sy, V[Vnum].ex, V[Vnum].ey); if M <> 0 then begin removevectors(M, Vnum); Vnum:= Vnum - 1 end; Vnum:= Vnum + 1; V[Vnum].prev:= Vnum - 1; V[Vnum].sx:= J; V[Vnum].sy:= K + 1; V[Vnum].ex:= J; V[Vnum].ey:= K; V[Vnum].next:= Vnum - 3; V[Vnum].status:= 0; M:= IndexOfVector (V[Vnum].sx, V[Vnum].sy, V[Vnum].ex, V[Vnum].ey); if M <> 0 then begin removevectors(M, Vnum); Vnum:= Vnum - 1 end; end; |
AW: fast array search with delphi
Nimm eine (modifizierte) Hashmap, als Schlüssel
Delphi-Quellcode:
Alles andere ist lahme Kinderk****e (wenn man auf Gleichheit prüfen will).
IntToStr(x)+','+IntToStr(y);
Hashmaps erlauben normalerweise (soweit ich weiß), keine doppelten Schlüssel, da müsste man mal schauen, ob es mit Bordmitteln geht, oder ob man sich etwas zusammenbasteln muss. Am bei weitem Schnellsten ist es in jedem Fall, denn es können auch 100.000.000 Einträge sein: Eine Hashmap ist immer gleich schnell, sofern sie nicht extrem übervoll ist. |
AW: fast array search with delphi
Zitat:
HashMaps erlauben schon doppelte Schlüssel. Je nach Bucketfaktor. (Zumindest in Java) Aber das ist kein Problem, da dann lediglich die Elemente im Bucket mit dem Search-Value verglichen werden. HashMap ist auf jeden Fall eine gute Idee hierfür. Sehr performant. |
AW: fast array search with delphi
Wenn es um Flächen geht, die mit Vektoren umschlossen werden sollen, könnte ein Blick auf den 'Convex Hull' Algorithmus helfen, der auf dem Flächenrand liegende Punkteschar so sortiert, das man hinterher eine Linie durch die Punkte ziehen kann und das resultierende Polygon tatsächlich die Fläche umschließt.
Hier nimmt man sich einfach alle Punkte, sortiert die nach "Convex Hull", zieht Vektoren durch die Punkte und verlängert einzelne Vektoren so lange, wie sich die Steigung nicht signifikant ändert. Da die Vektoren schon sortiert vorliegen, sodaß sich berührende Vektoren nebeneinander liegen (außer der erste und der letzte der Liste :-) ), muss man nicht suchen. Das sollte schon recht flott sein. Bleibt nur noch das Problem, unterschiedliche Flächen als solche zu erkennen und die zu einer Fläche gehörende Punkteschar vor der o.g. Methode zu isolieren. |
AW: fast array search with delphi
Zitat:
Stringoperationen und sinnlose Konvertierungen sind doch K***e. Eine einfache sortierte Liste über die Records, mit einer ordentlichen Suchroutine sind doch vollkommen ausreichend. PS: FredlFesl Eine Hashmap/List ist hier garnicht verlangt, da die X-Y-Koorinaten nur in den Tag-Property der einzelnen Komponenten drinsteht. :zwinker:
Delphi-Quellcode:
für zwei maximal 16-Bit-Werete
Tag := (x shl 16) or y;
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 22:47 Uhr. |
Powered by vBulletin® Copyright ©2000 - 2025, Jelsoft Enterprises Ltd.
LinkBacks Enabled by vBSEO © 2011, Crawlability, Inc.
Delphi-PRAXiS (c) 2002 - 2023 by Daniel R. Wolf, 2024 by Thomas Breitkreuz