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

:wink:

[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:

Zitat von BUG (Beitrag 1284248)

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:

Zitat von Dejan Vu (Beitrag 1284277)

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:

Zitat von Dejan Vu (Beitrag 1284277)

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:

Zitat von Dejan Vu (Beitrag 1284277)

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:

Zitat von BadenPower (Beitrag 1284285)

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.

[Dejan Vu]

Kommt drauf, wie man es liest. Aber wenn es wirklich dynamische Arrays sind, hast Du recht.

Ich frag mich dann nur, wie das dann eigentlich funktioniert, wenn sich die Arrays parallel irgendwo spontan ändern... :gruebel: Vielleicht ist das doch ein fester Speicherbereich.

Wenn der Code, der die Arrays neu schreibt, auch vom TE ist, kann er da eigentlich die Dictionary gleich erstellen.

[himitsu]

Zitat:

Dann scheidet das Casten auf eine flache, eindimensionale Array-Struktur wohl aus.

Nein, direkt ausfallen tut es nicht.

Die maximale Größe ist bekannt und man kann da Array immer mit der maximalen Größe definieren, auch wenn nicht alles verwendet wird. (31 MB sind ja nicht wirklich ein schlimmer Speicherverbrauch > 201*201*201*4)
Man kann auch die 3-dimensionale Struktur auf ein 1-gimensionales Array abbilden.

Delphi-Quellcode:

Arr[x + y*Length(Ax) + z*Length(Ay)*Length(Ax)]

Da hier Alles mit Allem verglichen wird, dann kann man das extrem optimieren, indem man beide Arrays soriert, denn dann kann man das Suchmuster so optimieren, daß die Vergleichsoperationen minimiert werden, da man hier parallel durch die Arrays laufen kann, und so nur ähnliche Werte vergleichen muß, was sich bis hin zu O(Max(m, n)) aka O(Max(Mx*My*Mz, Cx*Cy*Cz)) optimieren lässt. (nicht eingerechnet der Aufwand für den Aufbau und das Sortieren der Vergleichdaten)

Zitat:

Ich frag mich dann nur, wie das dann eigentlich funktioniert, wenn sich die Arrays parallel irgendwo spontan ändern...

Solange sich nur der Inhalt ändert, aber nicht die Größe, dann könnte es gehen, aber dennoch kann es probleme geben, wenn zeitgleich auf den selben Speicherbereich zugegriffen wird.

[Uwe Raabe]

Zitat:

Zitat von himitsu (Beitrag 1284295)

Zitat:

Dann scheidet das Casten auf eine flache, eindimensionale Array-Struktur wohl aus.

Nein, direkt ausfallen tut es nicht.

Ein

Delphi-Quellcode:

array of array of array

ist ein dynamisches Array und da liegen die einzelnen Zeilen nie hintereinander - schon allein deswegen nicht, weil der Speicher für die interne Verwaltung immer vor dem ersten Element liegt.

Wenn aber eine neue Deklaration für das Array im Rahmen des Möglichen und Erwünschten liegt, dann kann man ja auch gleich ein eindimensionales Array deklarieren und für den indizierten Zugriff eigene Getter und Setter deklarieren.

[Sir Rufo]

Das Problem mit den Arrays ist doch, dass die sich in der Länge ändern können und dann war es dass mit dem linearen Array (bzw. man braucht eine riesige Umkopieraktion).

Wäre da nicht eine Klasse besser, die dieses 3D-Konstrukt beherbergt? Da könnte man dann so einiges kapseln und sichern und auch auf Änderungen reagieren.

Delphi-Quellcode:

TData<T> = class
public
  property Value[x,y,z:Integer] : T read GetValue write SetValue;
end;

Den Zugriff kann man dann über ein Dictionary abbilden

Delphi-Quellcode:

TDataPoint = record
  x, y, z : integer;
end;

FData : TDictionary<TDataPoint,T>;

Und für die Statistik nimmt man sich ein weiteres Dictionary

Delphi-Quellcode:

FStat : TDictionary<T,Integer>;

Der Setter nimmt nun den alten Wert aus der Statistk und fügt den neuen Wert ein. Zum Vergleichen benötigt man nur noch die Statistik.

Ist ein DataPoint nicht im Dictionary, dann gibt es als Wert

Delphi-Quellcode:

Default(T)

zurück und wenn

Delphi-Quellcode:

Default(T)

gesetzt wird, dann wird der Eintrag aus dem Dictionary entfernt.

[Dejan Vu]

Zitat:

Zitat von himitsu (Beitrag 1284295)

Man kann auch die 3-dimensionale Struktur auf ein 1-gimensionales Array abbilden.

Delphi-Quellcode:

Arr[x + y*Length(Ax) + z*Length(Ay)*Length(Ax)]

...Da hier Alles mit Allem verglichen wird, dann kann man das extrem optimieren, indem man beide Arrays sortiert,

Steht doch alles schon da. Und eine Dictionary ist immer noch schneller als eine sortierte Liste.

Zitat:

O(Max(m, n))

Das gibt es nicht. O ist hier O(n).

Zitat:

... aber dennoch kann es probleme geben, wenn zeitgleich auf den selben Speicherbereich zugegriffen wird.

Das meinte ich ja (neben dem gar nicht so dynamischen Array).

Wenn es denn dynamische Arrays sind, würde ich an den Stellen ansetzen, die diese Arrays erzeugen und dort einfach ein 'Array of Cardinal' anlegen.

[himitsu]

Zitat:

Zitat von Uwe Raabe (Beitrag 1284297)

Ein

Delphi-Quellcode:

array of array of array

ist ein dynamisches Array und da liegen die einzelnen Zeilen nie hintereinander - schon allein deswegen nicht, weil der Speicher für die interne Verwaltung immer vor dem ersten Element liegt.

Ich hab nichts Anderes behauptet. :zwinker:

Wenn man die maximale Größe kennt, dann könnte man das auch statisch deklarieren und verwendet dann halt nur den ersten Teil der Felder.
Und selbst bei Größenänderung der genutzten Anteile muß man nichtmal was umkopieren, da sich nichts verschiebt. :stupid:


Einziger Nachteil bleibt im Zugriff/Casten auf das eindimensionale Array, denn entwerder man vergleich immer alles oder man muß Teile überspringen. (bei Letzterem kann man sich den eindimensionalen Zugriff auch sparen und bleibt bei Mehrdimensional)