![]() |
Delphi-Version: 2007
Zeitkritische Array-Prüfung
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:
Geht das noch schneller?
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; Ich bin mir sicher, das einer der Power-User hier dies bestimmt kann. |
AW: Zeitkritische Array-Prüfung
Delphi-Quellcode:
Gruß
i:=-1;
repeat inc(i,1) until i>=length(A1) or ((A1[i]-A28[i]=0) and Bedingung); K-H |
AW: Zeitkritische Array-Prüfung
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? |
AW: Zeitkritische Array-Prüfung
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. |
AW: Zeitkritische Array-Prüfung
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:
Falls sich 'Characteristics' sehr selten ändert, sortierst Du das (entrollte) Array und suchst dann jedes Element aus 'Map' per Binary Search.
// 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 die Arrays sehr groß sind, ist eine Dictionary besser geeignet. Das müsste man ausprobieren. |
AW: Zeitkritische Array-Prüfung
Ja. Aber ich musste feststellen, dass wenn für mich ein Code nicht schön aussieht, dass er dann auch meist falsch ist.
Zitat:
:wink: |
AW: Zeitkritische Array-Prüfung
"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; |
AW: Zeitkritische Array-Prüfung
Hallo zusammen,
Zitat:
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:
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:
|
AW: Zeitkritische Array-Prüfung
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:
Ich glaube, das entspricht dem, was Du erklärt hast.
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; 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). |
AW: Zeitkritische Array-Prüfung
Zitat:
|
Alle Zeitangaben in WEZ +1. Es ist jetzt 19:57 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