Zeitkritische Array-Prüfung

[BadenPower]

Hallo zusammen,

ich habe eine Steuerung, welche eigentlich seit Jahren zuverlässig läuft.

Es müssen zwei dynamische und sich ändernde 3-dimensonale Arrays permanent miteinander verglichen werden. Also jeder Wert des einen Array mit jedem Wert des anderen. Und dies ohne unnötigen Zeitverlust.
Die Routine muss true zurückgeben, wenn ein Wert des einen Arrays im anderen vorhanden ist wärend eine Bedingung nicht erfüllt ist.


Meine derzeitige Prüfroutine welche in einem separaten Thread läuft sieht so aus:

Delphi-Quellcode:

function RaiseAlert(): Boolean;
var
  liMapX,liMapY,liMapZ,liChaX,liChaY,liChaZ: Integer;
label
  GotoLabel;
begin

GotoLabel:

  while (ThrottleLoop) and not (Terminated) do
   begin
    for liMapX := 0 to Length(Map) - 1 do
     begin
      for liMapY := 0 to Length(Map[liMapX]) - 1 do
       begin
        for liMapZ := 0 to Length(Map[liMapX][liMapY]) - 1 do
         begin
          for liChaX := 0 to Length(Characteristics) - 1 do
           begin
            for liChaY := 0 to Length(Characteristics[liChaX]) - 1 do
             begin
              for liChaZ := 0 to Length(Characteristics[liChaX][liChaY]) - 1 do
               begin
                if Characteristics[liChaX][liChaY][liChaZ] = Map[liMapX][liMapY][liMapZ] then
                 begin
                  if (InjectionPass) then
                   begin
                    InjectionPass := false;
                    Goto GotoLabel;
                   end
                  else
                   begin
                    Result := true;
                    Exit;
                   end
                 end;
               end;
             end;
           end;
         end;
       end;
     end;

    RenewData(Map);

   end;
  Result := false;

end;

Geht das noch schneller?

Ich bin mir sicher, das einer der Power-User hier dies bestimmt kann.

[p80286]

Delphi-Quellcode:

i:=-1;
repeat
  inc(i,1)
until i>=length(A1) or ((A1[i]-A28[i]=0) and Bedingung);

Gruß
K-H

[BUG]

Irgendwie hab ich den Eindruck, das der Ansatz insgesamt vielleicht nicht so ideal ist.
Vielleicht kannst du ein paar Worte zum eigendlichen Problem verlieren?

Werden beide Arrays geändert? Werden die Daten nur bei Renew(Map) verändert oder passiert das nebenläufig/parallel? Wie groß sind die Array? Was steht da drin?

[Luckie]

Also spätestens wenn ich die dritter verschachtelte Schleife getippt und den Sprungbefehl eingebaut hätte, wäre mir was komisch vorgekommen. Also zumindest, dass da es irgendwie besser, schöner, eleganter gehen muss.

Eventuell wäre Rekursion ein Ansatz das Problem zu lösen.

[Dejan Vu]

Ich glaube, er meint 'schneller' und nicht 'schöner'.

Schneller geht es, wenn Du die 3D-Arrays als 1D-Array ansiehst, dann entfallen die Index-Berechnungen.
Falls 'Characteristics' (bzw. einer der beiden Arrays) nicht oder nur selten verändert wird, kannst Du die Werte in eine Dictionary oder ein Sortieres Array packen und dann wesentlich schneller suchen.

Aber ehrlich gesagt verstehe ich die Schleife nicht. Du suchst also nach dem ersten Treffer (Match). Wenn du ihn gefunden hast, suchst Du nochmal (Goto). Wenn Du dann wieder einen Treffer gefunden hast, springst Du raus mit 'true'... Himm ist 'ThrottleLoop' eine Funktion, die die Arrays verändert?

Gut, egal. Das Goto würden wir hier übrigens auch sehr elegant wegbekommen. Die paar nanosekunden die das dann länger braucht, sind angesichsts der eh sehr unperformanten Umsetzen imho zu vernachlässigen. Hier würde ich eher sauber arbeiten (inline lokale Prozedur mit 'exit' statt 'Goto') aber Du siehst das ja eh anders.

Also:

Delphi-Quellcode:

// Statt
for i:=0 to x do
  for j:=0 to y do
    for j:=0 to z do
      if a[i][j][k]...

// eher
const
  totalElements
Var
  Flattened : Array [0..totalElements-1] of integer absolute a;

...
  for i:=0 to totalElements do
    if Flattened[i]....

Falls sich 'Characteristics' sehr selten ändert, sortierst Du das (entrollte) Array und suchst dann jedes Element aus 'Map' per Binary Search.

Falls die Arrays sehr groß sind, ist eine Dictionary besser geeignet. Das müsste man ausprobieren.

[Luckie]

Ja. Aber ich musste feststellen, dass wenn für mich ein Code nicht schön aussieht, dass er dann auch meist falsch ist.

Zitat:

When I am working on a problem I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong.

R. Buckminster Fuller

[mensch72]

"Goto" hin oder her, wenn statische voll Arrays wegen der stets max. Speichergöße ausfallen, dann würde ich mit 2 zusätzlichen IndexPointerArrays arbeiten, welche beim Update der Daten in "RenewData(Map);" mit erzeugt werden... das Resultat ist dann schon "etwas schöner" und auch schneller

Nachfolgendes nur mal so als PyseudoCode, weil ev. ein paar "End" oder Pointer noch noch falsch

Code:

function RaiseAlert(): Boolean;
var
  liMap,liCha: Integer;
  pMapIdx,pChaIdx: ^<DataType>;
 
label
  GotoLabel;
begin

GotoLabel:

  while (ThrottleLoop) and not (Terminated) do
   begin
    pMapIdx:=@MapIdx[0];
    for liMap := 0 to Length(MapIdx) - 1 do
     begin
          pChaIdx:=@CharacteristicsIdx[0];
          for liCha := 0 to Length(CharacteristicsIdx) - 1 do
           begin
            if pChaIdx^ = pMapIdx^ then
             begin
              if (InjectionPass) then
               begin
                InjectionPass := false;
                Goto GotoLabel;
               end else begin
                Result := true;
                Exit;
               end;
              end;
             end;

            inc(pChaIdx);
           end;
         inc(pMapIdx);
        end;
     end;

    RenewData(Map);

   end;
  Result := false;

end;

[BadenPower]

Hallo zusammen,

Zitat von BUG:

Werden beide Arrays geändert? Werden die Daten nur bei Renew(Map) verändert oder passiert das nebenläufig/parallel? Wie groß sind die Array? Was steht da drin?

Beide Arrays sind "array of array of array of Cardinal" deren Werte sich fortlaufend parallel zur Prüfroutine ändern.

Die Größe der beiden Array variiert unterschiedlich, wobei sich Map im Bereich von 10*10*10 bis 100*100*100 und Characteristics sich meist zwischen 0*0*0 bis 200*200*200 befindet.

Zitat von Dejan Vu:

Aber ehrlich gesagt verstehe ich die Schleife nicht. Du suchst also nach dem ersten Treffer (Match). Wenn du ihn gefunden hast, suchst Du nochmal (Goto). Wenn Du dann wieder einen Treffer gefunden hast, springst Du raus mit 'true'... Himm ist 'ThrottleLoop' eine Funktion, die die Arrays verändert?

ThrottleLoop ist ein Zustand, also ein Boolean, welcher sich ändern kann. Ist "ThrottleLoop" false, dann wird die Prüfroutine abgebrochen und gibt false zurück sobald alle Durchgänge erledigt sind.

Wenn ich einen Treffer erhalte und "InjectionPass" ist true dann muss ich mit der Prüfung von vorne beginnen, da beim Zuweisen von false im Setter von "InjectionPass" weiter Aktionen ausgeführt werden. Hier kann es dann sein, dass sich die komplette Struktur der beiden Arrays ändert.

"InjectionPass" wird zur Laufzeit der Routine auch paralell geändert. Und nur wenn "InjectionPass" false ist und ein Treffer erzielt wird, dann muss die Prüfroutine abgebrochen und true zurückgegeben werden.

Habe ich keinen Treffer und "ThrottleLoop" ist immer noch true, dann wird RenewData(Map) benötigt um auf eine eventuell vorhandene neue Struktur des Map-Array reagieren zu können.

Zitat von Dejan Vu:

Falls 'Characteristics' (bzw. einer der beiden Arrays) nicht oder nur selten verändert wird, kannst Du die Werte in eine Dictionary oder ein Sortieres Array packen und dann wesentlich schneller suchen.

Scheidet aus, da sich die Werte permanent ändern.

Zitat von Dejan Vu:

Ich glaube, er meint 'schneller' und nicht 'schöner'.

Ja schneller und ich würde sogar auf das GOTO verzichten.

[Dejan Vu]

Alles klar. Du hast ja beschrieben, das das alles funktioniert...

D.h. nochmal: Sortierte Lookup o.ä. scheiden aus, da sich beide Array ständig und spontan ändern, richtig?
Unter O(n*m) wobei n=Länge 'Characteristics' und m=Länge 'Map' wirst Du dann nicht landen.

Was mich dabei nur noch wundert, ist das Du die Zugriffe auf diese Arrays offensichtlich nicht über Synchronisationsobjekte (Critical Section) schützt.

Mein Pseudocode-Ansatz wäre übrigens:

Delphi-Quellcode:

Function DataHasMatch : Boolean;
Begin
  for i:=0 to CharacteristicsDataCount-1 do
     for j:=0 to MapsDataCount - 1 do
       if Characteristics[i]=Maps[j] then exit(true);
   
  result := false;
end;

Procedure Execute;
begin
 while ThrottleLoop and not Terminated do begin
   repeat
      hasMatch := DataHasMatch;
      if hasMatch then InjectionPass := false;
    until InjectionPass or not hasMatch;

    if hasMatch then exit(true);
    RenewData(Map);
 end
end;

Ich glaube, das entspricht dem, was Du erklärt hast.

PS: Es ginge viel schneller, wenn das Verfahren auch dann funktioniert, wenn sich die Arrays während(!) der Prüfroutine nicht ändern (z.B. kann man sich vorstellen die beiden Arrays vor dem Prüfvorgang zu kopieren). Dann schreibst Du das größere der beiden Arrays in eine Dictionary und suchst anschließend alle Elemente des kleineren Arrays in der Dictionary.

Einfügen der Werte in eine Dictionary = O(n)
Suchen aller Werte in der Dictionarry = O(m)

Dein Verfahren wäre demnach O(n) und nicht mehr O(n*m).

[Uwe Raabe]

Zitat von BadenPower:

Beide Arrays sind "array of array of array of Cardinal"

Dann scheidet das Casten auf eine flache, eindimensionale Array-Struktur wohl aus. Die einzelnen Arrays können nämlich irgendwo im Speicher liegen und in den äußeren Arrays sind nur Pointer auf die jeweils inneren gespeichert.