optimization - 记或不记

Question

... 就是那个问题。我一直在研究一种算法，该算法将向量数组作为输入，并且该算法的一部分重复选择向量对并评估这两个向量的函数，该函数不会随着时间而改变。在寻找优化算法的方法时，我认为这将是记忆化的一个好案例:与其一遍又一遍地重新计算相同的函数值，不如将其缓存并命中缓存。

在跳到代码之前，这里是我的问题的要点:我从内存中获得的好处取决于向量的数量，我认为这与重复调用的数量成反比，并且在某些情况下内存会完全降低性能。那么我的情况是否不足以内存？我是不是做错了什么，有没有更聪明的方法来优化我的情况？

这是一个简化的测试脚本，它非常接近真实的东西:

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

这是我正在观察的:
* 当 size 很小 (10) 时，memoization 的速度大约是原始版本的两倍，
* 当大小很大(1000)时，内存比原始版本多 15 倍，
* 当 f 代价高昂时，memoization 会改进

我的解释是，当尺寸较小时，我们有更多的重复计算，并且缓存得到了返回。

令我吃惊的是更大尺寸的巨大性能冲击，我不确定是什么原因造成的。我知道我可以稍微改进字典访问，例如使用结构键 - 但我没想到“天真的”版本表现得如此糟糕。

那么 - 我在做什么明显有问题吗？对于我的情况，内存是错误的方法吗？如果是，有更好的方法吗？

Answer 1

我认为内存是一种有用的技术，但它不是 Elixir 。在 dynamic programming 中非常有用它降低了算法的(理论)复杂性。作为一种优化，它可以(正如您可能期望的那样)产生不同的结果。

在您的情况下，当观察数量较少时，缓存肯定更有用(并且 f 计算成本更高)。您可以将简单的统计数据添加到您的内存中:

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)所以记忆化有很大的好处——函数f计算 100 倍，然后每个结果重复使用 9999 倍。

对于大size ，我得到类似 (632331, 1367669)所以f被多次调用，每个结果只被重用两次。在这种情况下，在(大)哈希表中分配和查找的开销要大得多。

作为次要优化，您可以预先分配 Dictionary并写 new Dictionary<_, _>(10000,HashIdentity.Structural) ，但在这种情况下似乎没有多大帮助。

为了使这种优化有效，我认为您需要了解有关 memoized 函数的更多信息。在您的示例中，输入非常有规律，因此记忆化可能没有意义，但是如果您知道该函数更经常使用某些参数值调用，则您可能只能内存这些常见参数。