garbage-collection - 在 Julia 中高效优雅地迭代集合和数字的并集

Question

我遇到了一个问题，即必须在 Julia 中对集合和数字的并集进行数百万次迭代。我遇到过两种解决方案:一种优雅但低效，另一种高效但不优雅。

MWE:考虑以下三个函数，给定一组整数和另一组整数，计算联合中元素的总和:

function f(a::Set{Int64}, b::Int64)::Int64
    return sum(union(a, b))
end

function g(a::Set{Int64}, b::Int64)::Int64
    s = sum(a)
    if !in(b, a) s += b end
    return s
end

现在，让我们考虑以下对函数 f 和 g 的调用(下面的输出表示两个函数预编译后的行为):

julia> a = Set{Int64}(rand(-10000000 : 10000000, 10000000))
julia> b = maximum(a) + 1

julia> @benchmark f(a, b)
BenchmarkTools.Trial: 15 samples with 1 evaluation.
 Range (min … max):  325.095 ms … 348.911 ms  ┊ GC (min … max): 0.00% … 4.64%
 Time  (median):     333.346 ms               ┊ GC (median):    0.17%
 Time  (mean ± σ):   337.121 ms ±   8.365 ms  ┊ GC (mean ± σ):  2.14% ± 2.38%

  █     ▁          ▁█ ▁▁                    █    ▁   ▁    █   ▁  
  █▁▁▁▁▁█▁▁▁▁▁▁▁▁▁▁██▁██▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁█▁▁▁▁█▁▁▁█▁▁▁▁█▁▁▁█ ▁
  325 ms           Histogram: frequency by time          349 ms <

 Memory estimate: 144.00 MiB, allocs estimate: 11.

julia> @benchmark g(a, b)
BenchmarkTools.Trial: 76 samples with 1 evaluation.
 Range (min … max):  65.334 ms …  69.013 ms  ┊ GC (min … max): 0.00% … 0.00%
 Time  (median):     66.057 ms               ┊ GC (median):    0.00%
 Time  (mean ± σ):   66.216 ms ± 595.005 μs  ┊ GC (mean ± σ):  0.00% ± 0.00%

        ▄  ▂▂▂ ▄ █   ▆                                          
  ▄▁▁▁▁▄█▁████▄█▆██▄▄██▆█▁▁▁▆▁▆█▁▄▁▄▁█▆▁▄▁▁▁▄▁▄▁▁▁▁▁▁▁▁▁▁▁▁▄▁▄ ▁
  65.3 ms         Histogram: frequency by time         67.9 ms <

 Memory estimate: 0 bytes, allocs estimate: 0.

如您所见，函数 g 在 GC 和时间方面都更高效，但函数体也更丑陋。

问题:有没有办法在实现g性能的同时，实现函数f的优雅？更具体地说，我正在考虑一些允许迭代这样的联合而无需分配新集合的东西

我尝试了这两种实现，为了提高效率，我目前保留类似于函数 g 的实现

Answer 1

如果你只是想要一个更简洁的 g() 版本，请考虑

h(a, b) = sum(a) + b * !(b in a)

它使用 bool 值 !(b in a) 如果为假则为 0，如果为真则为 1 的事实。任何向集合中添加 b 都会检查 a 中的 b 以防止出现重复元素，如果集合的大小处于其内存分配的边缘(虽然不是在这里)，偶尔将 b 添加到 a 将触发自动分配。