fast array search with delphi

[Bjoerk]

Delphi-Quellcode:

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;

Ob so aber tatsächlich eine Zeitersparnis entsteht, müßte man erst ausprobieren.

[FredlFesl]

Nimm eine (modifizierte) Hashmap, als Schlüssel IntToStr(x)+','+IntToStr(y); Alles andere ist lahme Kinderk****e (wenn man auf Gleichheit prüfen will).
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.

[Woyzeck]

Zitat von FredlFesl:

Nimm eine (modifizierte) Hashmap, als Schlüssel IntToStr(x)+','+IntToStr(y); Alles andere ist lahme Kinderk****e (wenn man auf Gleichheit prüfen will).
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.

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.

[FredlFesl]

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.

[himitsu]

Zitat von FredlFesl:

Nimm eine (modifizierte) Hashmap, als Schlüssel IntToStr(x)+','+IntToStr(y); Alles andere ist lahme Kinderk****e (wenn man auf Gleichheit prüfen will).
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.

Hashmap ja, aber wenn, dann mit einem 64 Bit-Index (falls ihm Word für die beiden Axen reicht, dann auch ein LongWord aka 2*Word)
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.

Tag := (x shl 16) or y; für zwei maximal 16-Bit-Werete