Moin,
wer kennt es nicht. Man hat eine Funktion die irgendetwas stochastisch berechnet (Monte-Carlo) und relativ lange braucht.
Diese Funktion möchte man aber im Idealfall "oft" aufrufen (ggf. in einer anderen Funktion, die ebenfalls stochastisch arbeitet, usw usw). Im Endeffekt resultiert das in Abermillionen von Funktionsaufrufen, die sehr schnell sehr viel Zeit in Anspruch nehmen.
Aber es gibt Abhilfe: Ein sich selbst füllender Puffer der Funktionswerte an einigen Stützstellen speichert und dann linear interpoliert (mit Unsicherheitsangabe).
Vermutlich habe ich darin noch ein Paar Bugs versteckt, aber für meine bisherigen Anwendungsfälle hat es funktioniert, daher gibts jetzt ne "mini-UDF". Wie bei allen Methoden ist es wichtig "sinnvolle" Parameter zu wählen, ansonsten läuft sich der Algorithmus tot (mit Failsave -> MaxIter) oder produziert vollkommen falsche Ergebnisse (z.B. wenn man nur 10 Stützstellen verwendet, obwohl man eigentlich mindestens 100 braucht, oder wenn man eine Genauigkeit von 0.01 haben möchte, obwohl die Funktionswerte die Größenordnung 100 und eine große Streuung haben). Was die Ungenauigkeitsangabe im Returnwert angeht möchte ich meine Hand nicht ins Feuer legen. Da sich der Mittelwert ja mit jedem neuen Sample ändert und die vorherigen Varianzen nicht angepasst werden können (man will ja nicht "alles" speichern) ist dieser Wert nur "ungefähr richtig".
Die Verwendung ist glaube ich intuitiv ersichtlich wenn man das Beispiel anschaut. FFB heißt "FuzzyFunctionBuffer"
AutoIt
Global Const $__FFB_MIN_SAMPLES = 17
; Beispielfunktion mit langer Rechenzeit die "nicht genau" arbeitet:
; Stochastisches abschätzen vom Volumen einer Kugel mir Radius $r
Func myFunc($r)
Local Const $k = 1000
Local $n = 0, $r2 = $r ^ 2
For $i = 0 To $k - 1 Step 1
$n += Random(-$r, $r) ^ 2 + Random(-$r, $r) ^ 2 + Random(-$r, $r) ^ 2 < $r2
Next
Return $n / $k * (2 * $r) ^ 3
EndFunc ;==>myFunc
; Naiver Ansatz:
; Einfach Mittelwert bilden über N Versuche (hier mit N = 100)
; Probleme:
; - Wie genau ist das denn jetzt?
; - Wenn ich die Funktionswerte mehrfach brauche muss ich mich selbst um das Puffern kümmern.
; - Wenn ich "ähnliche" Funktionswerte brauche muss die Funktion komplett neu ausgewertet werden.
Local $t = TimerInit()
For $i = 80 To 90 Step 1
Local $v = 0
For $j = 0 To 99 Step 1
$v += myFunc($i / 100)
Next
$v /= 100
ConsoleWrite('r = ' & StringFormat('% 5.3f', $i / 100) & ' -> Vol = ' & StringFormat('% 6.4f', $v) & ' err = ' & StringFormat('% 6.4f', $v-4/3*(($i/100)^3)*3.141592654) & @CRLF)
Next
ConsoleWrite('Time: ' & TimerDiff($t) & @CRLF)
ConsoleWrite(@CRLF)
;~ ; Ansatz mit Lookup-Table & linearer Interpolation
Local $FFB = _FFB_Create1D(myFunc, 0, 5, 100)
Local $t = TimerInit()
For $i = 80 To 90 Step 1
Local $v = _FFB_Call1D($FFB, $i / 100, 0.01)
ConsoleWrite('r = ' & StringFormat('% 5.3f', $i / 100) & ' -> Vol = ' & StringFormat('% 6.4f +- % 6.4f', $v[0], $v[1]) & ' err = ' & StringFormat('% 6.4f', $v[0] - 4 / 3 * (($i / 100) ^ 3) * 3.141592654) & @CRLF)
Next
ConsoleWrite('Time: ' & TimerDiff($t) & @CRLF)
ConsoleWrite(@CRLF)
; Der Trick ist jetzt, dass der LUT jetzt aufgebaut ist. Braucht man die Funktionswerte erneut ist das relativ schnell
; Auch für Funktionswerte die nicht "exakt" da liegen wo man schonmal gesampled hat. Je mehr sich der LUT füllt, desto schneller wird er.
Local $t = TimerInit()
For $i = 80 To 90 Step 1
Local $x = $i / 100 + Random(-0.05, 0.05)
Local $v = _FFB_Call1D($FFB, $x, 0.01)
ConsoleWrite('r = ' & StringFormat('% 5.3f', $x) & ' -> Vol = ' & StringFormat('% 6.4f +- % 6.4f', $v[0], $v[1]) & ' err = ' & StringFormat('% 6.4f', $v[0] - 4 / 3 * ($x ^ 3) * 3.141592654) & @CRLF)
Next
ConsoleWrite('Time: ' & TimerDiff($t) & @CRLF)
ConsoleWrite(@CRLF)
Func _FFB_Call1D(ByRef $FFB, $x, $nAccuracy = 0.01, $iIterMax = 100)
Local $iSteps = UBound($FFB) - 1
Local $k = ($x - $FFB[$iSteps][1]) / $FFB[$iSteps][2] * ($iSteps - 1)
Local $i = Int($k), $ix = ($i / ($iSteps - 1) * $FFB[$iSteps][2] + $FFB[$iSteps][1]) ; Unterer Slot
Local $j = $i + 1, $jx = ($j / ($iSteps - 1) * $FFB[$iSteps][2] + $FFB[$iSteps][1]) ; Oberer Slot
Local $alpha = $k - $i ; $alpha = Prozentsatz vom darüberliegenden Slot
Local $f = $FFB[$iSteps][0], $v = 0, $t = 0
If $i >= 0 And $i < $iSteps Then
If $FFB[$i][2] < $__FFB_MIN_SAMPLES Then
Local $p[]
For $_ = 0 To $__FFB_MIN_SAMPLES - 1 Step 1
$p[$_] = $f($ix)
$FFB[$i][0] += $p[$_]
Next
$FFB[$i][0] /= $__FFB_MIN_SAMPLES
For $_ = 0 To $__FFB_MIN_SAMPLES - 1 Step 1
$FFB[$i][1] += ($p[$_] - $FFB[$i][0]) ^ 2
Next
$FFB[$i][2] = $__FFB_MIN_SAMPLES
EndIf
$t = 0
While Sqrt($FFB[$i][1]) / ($FFB[$i][2] - 1) > $nAccuracy
$v = $f($ix)
$FFB[$i][0] = ($FFB[$i][0] * $FFB[$i][2] + $v) / ($FFB[$i][2] + 1)
$FFB[$i][1] += ($v - $FFB[$i][0]) ^ 2
$FFB[$i][2] += 1
$t += 1
If $t >= $iIterMax Then ExitLoop
WEnd
EndIf
If $j >= 0 And $j < $iSteps Then
If $FFB[$j][2] < $__FFB_MIN_SAMPLES Then
Local $p[]
For $_ = 0 To $__FFB_MIN_SAMPLES - 1 Step 1
$p[$_] = $f($jx)
$FFB[$j][0] += $p[$_]
Next
$FFB[$j][0] /= $__FFB_MIN_SAMPLES
For $_ = 0 To $__FFB_MIN_SAMPLES - 1 Step 1
$FFB[$j][1] += ($p[$_] - $FFB[$j][0]) ^ 2
Next
$FFB[$j][2] = $__FFB_MIN_SAMPLES
EndIf
$t = 0
While Sqrt($FFB[$j][1]) / ($FFB[$j][2] - 1) > $nAccuracy
$v = $f($jx)
$FFB[$j][0] = ($FFB[$j][0] * $FFB[$j][2] + $v) / ($FFB[$j][2] + 1)
$FFB[$j][1] += ($v - $FFB[$j][0]) ^ 2
$FFB[$j][2] += 1
$t += 1
If $t >= $iIterMax Then ExitLoop
WEnd
EndIf
Local $Ret[]
If Abs($alpha) < 1E-3 Then
$Ret[0] = $FFB[$i][0]
$Ret[1] = Sqrt($FFB[$i][1] / ($FFB[$i][2] - 1))
ElseIf Abs($alpha - 1) < 1E-3 Then
$Ret[0] = $FFB[$j][0]
$Ret[1] = Sqrt($FFB[$j][1] / ($FFB[$j][2] - 1))
Else
$Ret[0] = $FFB[$i][0] * (1 - $alpha) + $FFB[$j][0] * $alpha
$Ret[1] = (Sqrt($FFB[$i][1]) / ($FFB[$i][2] - 1)) * (1 - $alpha) + (Sqrt($FFB[$j][1]) / ($FFB[$j][2] - 1)) * $alpha
EndIf
Return $Ret ; [0] = Wert, [1] = Unsicherheit
EndFunc ;==>_FFB_Call1D
Func _FFB_Create1D($xFunc, $fMinInclusive = 0, $fMaxInclusive = 1, $iSteps = 100)
Local $_[$iSteps + 1][3]
$_[$iSteps][0] = $xFunc
$_[$iSteps][1] = $fMinInclusive
$_[$iSteps][2] = $fMaxInclusive - $fMinInclusive
; [0] = Mittelwert
; [1] = VarianzSumme
; [2] = NumSamples
Return $_
EndFunc ;==>_FFB_Create1DEdit: Hier noch eine Überarbeitung mit quadratischer Interpolation (so kann man den LUT etwas kleiner wählen, oder man möchte eine sehr weiche Kurve. Die gab es bei der linearen Version nicht).
AutoIt
#include <Array.au3>
Global Const $__FFB_MIN_SAMPLES = 17
Global Const $__FFB_NUM_MAXITER = 100
; Anwendungsfall: Funktionswerte entstören
Func myFunc($r)
Return Sin($r) + Random() / 3 ; sin ist im Bereich -1 bis 1, mit 1/3 plusminus rauschen ist das schon ziemlich viel.
EndFunc ;==>myFunc
Local $FFB = _FFB_Create1D(myFunc, -10, 10, 100) ; Hat 100 Slots zwischen -10 und 10
For $i In __FFB_Range('[', -3.141, 3.141, ']', 200) ; Die 200 Samples brauchen nur ca. 33 Slots. Durch die quadratische Interpolation kommt trotzdem eine gute Kurve heraus.
Local $v = _FFB_Call1D($FFB, $i[1], 0.0005, 1e9, 100000) ; Wenn man es wirklich ganz genau haben will. (0.0005 Sigma, da will man schon 3 richtige Nachkommastellen haben)
ConsoleWrite(StringFormat('% 5.3f', $i[1]) & ', ' & StringFormat('% 6.4f', $v[0]) & @CRLF)
Next
_ArrayDisplay($FFB) ; Nachschauen was im LUT eigentlich drin steht.
Func _FFB_Train1D(ByRef $FFB, $nAbsAccuracy = 1e9, $nRelAccuracy = 1e9)
Local $iSteps = UBound($FFB) - 1
Local $fMin = $FFB[$iSteps][1]
Local $fMax = $FFB[$iSteps][2] + $FFB[$iSteps][1]
Local $bTargetMet = True, $v = 0
Do
$bTargetMet = True
For $i In __FFB_Range('[', $fMin, $fMax, ']', $iSteps)
$v = _FFB_Call1D($FFB, $i[1], $nAbsAccuracy, $nRelAccuracy)
If $v[1] > $nAbsAccuracy Then $bTargetMet = False
If $v[0] > 1E-9 And $v[1] / $v[0] > $nRelAccuracy Then $bTargetMet = False
Next
Until $bTargetMet
EndFunc ;==>_FFB_Train1D
Func _FFB_Call1D(ByRef $FFB, $x, $nAbsAccuracy = 1e9, $nRelAccuracy = 1e9, $iIterMax = $__FFB_NUM_MAXITER, $bQuadraticInterpolation = True)
Local $iSteps = UBound($FFB) - 1, $s5 = $iSteps - 5, $s5d = $s5 / $FFB[$iSteps][2]
Local $k = ($x - $FFB[$iSteps][1]) * $s5d + 2, $ik = Int($k) ; Slots: [ik-1, ik, ik+1, ik+2] <- diese 4 sind immer vorhanden.
Local $alpha = $k - $ik ; $alpha = Prozentsatz vom darüberliegenden Slot
Local $f = $FFB[$iSteps][0], $v = 0, $t = 0
For $i = $ik - 1 To $ik + 2 Step 1 ; from -1 to 2 -> Für 4 Slots.
Local $ix = ($i - 2) / $s5d + $FFB[$iSteps][1]
If $FFB[$i][2] < $__FFB_MIN_SAMPLES Then
Local $p[]
For $_ = 0 To $__FFB_MIN_SAMPLES - 1 Step 1
$p[$_] = $f($ix)
$FFB[$i][0] += $p[$_]
Next
$FFB[$i][0] /= $__FFB_MIN_SAMPLES
For $_ = 0 To $__FFB_MIN_SAMPLES - 1 Step 1
$FFB[$i][1] += ($p[$_] - $FFB[$i][0]) ^ 2
Next
$FFB[$i][2] = $__FFB_MIN_SAMPLES
EndIf
$t = 0
While Sqrt($FFB[$i][1]) / ($FFB[$i][2] - 1) > $nAbsAccuracy Or ($FFB[$i][0] > 1E-9 And Sqrt($FFB[$i][1]) / ($FFB[$i][2] - 1) / $FFB[$i][0] > $nRelAccuracy)
$v = $f($ix)
$FFB[$i][0] = ($FFB[$i][0] * $FFB[$i][2] + $v) / ($FFB[$i][2] + 1)
$FFB[$i][1] += ($v - $FFB[$i][0]) ^ 2
$FFB[$i][2] += 1
$t += 1
If $t >= $iIterMax Then ExitLoop
WEnd
Next
Local $Ret[]
If $bQuadraticInterpolation Then
Local $ixa = ($ik - 3) / $s5d + $FFB[$iSteps][1], $ixb = ($ik - 2) / $s5d + $FFB[$iSteps][1], $ixc = ($ik - 1) / $s5d + $FFB[$iSteps][1], $ixd = $ik / $s5d + $FFB[$iSteps][1]
Local $P3L = __FFB_Func3P($ixa, $FFB[$ik - 1][0], $ixb, $FFB[$ik - 0][0], $ixc, $FFB[$ik + 1][0])
Local $P3H = __FFB_Func3P($ixb, $FFB[$ik - 0][0], $ixc, $FFB[$ik + 1][0], $ixd, $FFB[$ik + 2][0])
$Ret[0] = ($P3L[0] * $x^2 + $P3L[1] * $x + $P3L[2]) * (1 - $alpha) + ($P3H[0] * $x^2 + $P3H[1] * $x + $P3H[2]) * $alpha
Else
$Ret[0] = $FFB[$ik][0] * (1 - $alpha) + $FFB[$ik + 1][0] * $alpha
EndIf
$Ret[1] = (Sqrt($FFB[$ik][1]) / ($FFB[$ik][2] - 1)) * (1 - $alpha) + (Sqrt($FFB[$ik + 1][1]) / ($FFB[$ik + 1][2] - 1)) * $alpha
Return $Ret ; [0] = Wert, [1] = Unsicherheit
EndFunc ;==>_FFB_Call1D
Func _FFB_Create1D($xFunc, $fMinInclusive = 0, $fMaxInclusive = 1, $iSteps = 100, $nBorderEpsilon = 1E-6)
$fMinInclusive -= $nBorderEpsilon
$fMaxInclusive += $nBorderEpsilon
Local $_[$iSteps + 1][3]
$_[$iSteps][0] = $xFunc
$_[$iSteps][1] = $fMinInclusive
$_[$iSteps][2] = $fMaxInclusive - $fMinInclusive
; [i][0] = Mittelwert
; [i][1] = VarianzSumme
; [i][2] = NumSamples
Return $_
EndFunc ;==>_FFB_Create1D
Func __FFB_Range($sLeft = '[', $fMin = 0, $fMax = 1, $sRight = ']', $iSteps = 10)
Local $a[$iSteps], $_[2], $l = $sLeft = '[' ? 0 : 1, $s = ($fMax - $fMin) / ($iSteps - 1 + ($sRight = ']' ? 0 : 1) + $l)
For $i = 0 To $iSteps - 1 Step 1
$_[0] = $i
$_[1] = ($i + $l) * $s + $fMin
$a[$i] = $_
Next
Return $a
EndFunc ;==>__FFB_Range
Func __FFB_Func2P($x0, $y0, $x1, $y1)
Local $_[] ; f(x) = ax + b
$_[0] = ($y1 - $y0) / ($x1 - $x0)
$_[1] = $y0 - $_[0] * $x0
Return $_
EndFunc
Func __FFB_Func3P($x0, $y0, $x1, $y1, $x2, $y2)
Local $_[] ; f(x) = ax² + bx + c
$_[0] = ($x2 * ($y1 - $y0) + $x1 * ($y0 - $y2) + $x0 * ($y2 - $y1)) / (($x0 - $x1) * ($x0 - $x2) * ($x1 - $x2)) ; a
$_[1] = (($y1 - $y0) + $_[0] * ($x0 ^ 2 - $x1 ^ 2)) / ($x1 - $x0) ; b
$_[2] = $y0 - $_[0] * $x0 ^ 2 - $_[1] * $x0 ; c
Return $_
EndFunclg
M