fast array search with delphi

[bernhard_LA]

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 http://www.swissdelphicenter.ch/torr...de.php?id=1916 auf mein problem anwenden ...

[Neutral General]

Hallo,

Dann musst du das Array vorher sortieren.
Sonst kommst du nicht drumrum das ganze Array jedes mal zu durchsuchen.

[Uwe Raabe]

Zitat von Neutral General:

Dann musst du das Array vorher sortieren.

Und das Sortieren geht dank Generics in D2010+ auch recht einfach:

Delphi-Quellcode:

  
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));

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!).

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.

[bernhard_LA]

der code kommt von : http://cardhouse.com/computer/vectcode.htm, ist uralt, vermutlich noch tp5.5

das problem liegt in der procedure :

Delphi-Quellcode:

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;

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 .

[sx2008]

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.

[Uwe Raabe]

Der Algorithmus ist wirklich alles andere als effizient - sowohl in der Laufzeit, als auch im Speicherverbrauch.

[Bjoerk]

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;

[Uwe Raabe]

Zitat von Bjoerk:

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,

Das wird so nicht funktionieren, da SimplifyVector ja nicht nur Vektoren entfernt, sondern auch die angrenzenden Vektoren verbindet.

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.

[himitsu]

Man könnte aber auch eine generische TList verwenden, statt dem Array ... equivalent zu dem schongezeigten TArray.Sort<vector>

[bernhard_LA]

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



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;