Mat*_*ias 5 optimization f# memoization
... 就是那个问题.我一直在研究一种算法,该算法将一组矢量作为输入,并且算法的一部分重复选择矢量对并评估这两个矢量的函数,这些函数不随时间变化.看看优化算法的方法,我认为这对于memoization来说是一个很好的例子:不是一遍又一遍地重新计算相同的函数值,而是懒惰地缓存它并点击缓存.
在跳转到代码之前,这里是我的问题的要点:我从memoization获得的好处取决于向量的数量,我认为这与重复调用的数量成反比,并且在某些情况下,memoization会完全降低性能.那么我的情况不足以进行记忆化吗？我做错了什么,是否有更聪明的方法来优化我的情况？
这是一个简化的测试脚本,它与真实的东西非常接近:
open System
open System.Diagnostics
open System.Collections.Generic
let size = 10 // observations
let dim = 10 // features per observation
let runs = 10000000 // number of function calls
let rng = new Random()
let clock = new Stopwatch()
let data =
[| for i in 1 .. size ->
[ for j in 1 .. dim -> rng.NextDouble() ] |]
let testPairs = [| for i in 1 .. runs -> rng.Next(size), rng.Next(size) |]
let f v1 v2 = List.fold2 (fun acc x y -> acc + (x-y) * (x-y)) 0.0 v1 v2
printfn "Raw"
clock.Restart()
testPairs |> Array.averageBy (fun (i, j) -> f data.[i] data.[j]) |> printfn "Check: %f"
printfn "Raw: %i" clock.ElapsedMilliseconds
我创建了一个随机向量(数据)列表,一个随机的索引集合(testPairs),并在每对上运行f.
这是备忘版本:
let memoized =
let cache = new Dictionary<(int*int),float>(HashIdentity.Structural)
fun key ->
match cache.TryGetValue(key) with
| true, v -> v
| false, _ ->
let v = f data.[fst key] data.[snd key]
cache.Add(key, v)
v
printfn "Memoized"
clock.Restart()
testPairs |> Array.averageBy (fun (i, j) -> memoized (i, j)) |> printfn "Check: %f"
printfn "Memoized: %i" clock.ElapsedMilliseconds
以下是我观察到的:*当尺寸小(10)时,记忆的速度大约是原始版本的两倍,*当尺寸大(1000)时,记忆的时间比原始版本多15倍,*当f很昂贵时,memoization改善了事情
我的解释是,当尺寸很小时,我们有更多的重复计算,并且缓存会得到回报.
让我感到惊讶的是大尺寸的巨大性能影响,我不确定是什么导致它.我知道我可以改进字典访问,例如使用结构键 - 但我没想到"天真"版本的表现如此糟糕.
那么 - 我在做什么显然是错的？记忆是我的情况的错误方法,如果是,是否有更好的方法？
我认为记忆是一种有用的技术,但它不是一颗银弹.它在动态编程中非常有用,它降低了算法的(理论上)复杂性.作为优化,它可以(正如您可能预期的那样)具有不同的结果.
在您的情况下,当观察数量较少时(和f更昂贵的计算),缓存肯定更有用.您可以在memoization中添加简单的统计信息:
let stats = ref (0, 0) // Count number of cache misses & hits
let memoized =
let cache = new Dictionary<(int*int),float>(HashIdentity.Structural)
fun key ->
let (mis, hit) = !stats
match cache.TryGetValue(key) with
| true, v -> stats := (mis, hit + 1); v // Increment hit count
| false, _ ->
stats := (mis + 1, hit); // Increment miss count
let v = f data.[fst key] data.[snd key]
cache.Add(key, v)
v
对于小的size,我得到的数字是这样的(100, 999900),因为fmemoization 有很大的好处 - 函数计算100x然后每个结果重复使用9999x.
对于大的size,我得到的东西像(632331, 1367669)这样f被称为很多次,每次结果被重用两次即可.在这种情况下,(大)哈希表中的分配和查找开销要大得多.
作为次要优化,您可以预先分配Dictionary和写入new Dictionary<_, _>(10000,HashIdentity.Structural),但在这种情况下似乎没有多大帮助.
为了使这种优化更有效,我认为您需要了解有关memoized函数的更多信息.在您的示例中,输入是非常规则的,因此在memoization中可能没有任何意义,但如果您知道该函数通常使用某些参数值调用,则您可能只能为这些常见参数进行memoize.
当您应该使用记忆时，Tomas的答案非常有用。这就是在您的情况下记忆是如此缓慢的原因。
听起来您正在调试模式下进行测试。在Release中再次运行测试，您将获得更快的记录结果。在调试模式下，元组可能会严重影响性能。我添加了一个散列版本以进行比较以及一些微优化。
发布
Raw
Check: 1.441687
Raw: 894
Memoized
Check: 1.441687
Memoized: 733
memoizedHash
Check: 1.441687
memoizedHash: 552
memoizedHashInline
Check: 1.441687
memoizedHashInline: 493
memoizedHashInline2
Check: 1.441687
memoizedHashInline2: 385
除错
Raw
Check: 1.409310
Raw: 797
Memoized
Check: 1.409310
Memoized: 5190
memoizedHash
Check: 1.409310
memoizedHash: 593
memoizedHashInline
Check: 1.409310
memoizedHashInline: 497
memoizedHashInline2
Check: 1.409310
memoizedHashInline2: 373
资源
open System
open System.Diagnostics
open System.Collections.Generic
let size = 10 // observations
let dim = 10 // features per observation
let runs = 10000000 // number of function calls
let rng = new Random()
let clock = new Stopwatch()
let data =
[| for i in 1 .. size ->
[ for j in 1 .. dim -> rng.NextDouble() ] |]
let testPairs = [| for i in 1 .. runs -> rng.Next(size), rng.Next(size) |]
let f v1 v2 = List.fold2 (fun acc x y -> acc + (x-y) * (x-y)) 0.0 v1 v2
printfn "Raw"
clock.Restart()
testPairs |> Array.averageBy (fun (i, j) -> f data.[i] data.[j]) |> printfn "Check: %f"
printfn "Raw: %i\n" clock.ElapsedMilliseconds
let memoized =
let cache = new Dictionary<(int*int),float>(HashIdentity.Structural)
fun key ->
match cache.TryGetValue(key) with
| true, v -> v
| false, _ ->
let v = f data.[fst key] data.[snd key]
cache.Add(key, v)
v
printfn "Memoized"
clock.Restart()
testPairs |> Array.averageBy (fun (i, j) -> memoized (i, j)) |> printfn "Check: %f"
printfn "Memoized: %i\n" clock.ElapsedMilliseconds
let memoizedHash =
let cache = new Dictionary<int,float>(HashIdentity.Structural)
fun key ->
match cache.TryGetValue(key) with
| true, v -> v
| false, _ ->
let i = key / size
let j = key % size
let v = f data.[i] data.[j]
cache.Add(key, v)
v
printfn "memoizedHash"
clock.Restart()
testPairs |> Array.averageBy (fun (i, j) -> memoizedHash (i * size + j)) |> printfn "Check: %f"
printfn "memoizedHash: %i\n" clock.ElapsedMilliseconds
let memoizedHashInline =
let cache = new Dictionary<int,float>(HashIdentity.Structural)
fun key ->
match cache.TryGetValue(key) with
| true, v -> v
| false, _ ->
let i = key / size
let j = key % size
let v = f data.[i] data.[j]
cache.Add(key, v)
v
printfn "memoizedHashInline"
clock.Restart()
let mutable total = 0.0
for i, j in testPairs do
total <- total + memoizedHashInline (i * size + j)
printfn "Check: %f" (total / float testPairs.Length)
printfn "memoizedHashInline: %i\n" clock.ElapsedMilliseconds
printfn "memoizedHashInline2"
clock.Restart()
let mutable total2 = 0.0
let cache = new Dictionary<int,float>(HashIdentity.Structural)
for i, j in testPairs do
let key = (i * size + j)
match cache.TryGetValue(key) with
| true, v -> total2 <- total2 + v
| false, _ ->
let i = key / size
let j = key % size
let v = f data.[i] data.[j]
cache.Add(key, v)
total2 <- total2 + v
printfn "Check: %f" (total2 / float testPairs.Length)
printfn "memoizedHashInline2: %i\n" clock.ElapsedMilliseconds
Console.ReadLine() |> ignore
| 归档时间： |
|
| 查看次数： |
594 次 |
| 最近记录： |