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"
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_Create1Dlg
M