具有多个函数的 Julia 函数组合

Question

我有一个包含 100 个函数的向量，我想将它们组合在一起。我需要多次按顺序运行这 100 个函数，所以我认为组合它们会比创建嵌套循环更快，但是，我遗憾地错了。我尝试了reduce(∘，reverse(instructions))(input)，但花了相当长的时间。我开始计时，并惊讶地发现将任何大量函数组合在一起比简单地循环遍历函数列表并按顺序应用它们要慢得多。我拥有的所有 100 个函数都是恒定时间操作，但以下是我对其中任何一个函数的组合进行计时时得到的结果。

julia> @time reduce(∘, reverse(instructions[1:2]))(2019)
  0.000015 seconds (9 allocations: 448 bytes)
2041

julia> @time reduce(∘, reverse(instructions[1:5]))(2019)
  0.006597 seconds (4.43 k allocations: 212.517 KiB)
6951

julia> @time reduce(∘, reverse(instructions[1:10]))(2019)
  0.022688 seconds (31.01 k allocations: 1.405 MiB)
4935

julia> @time reduce(∘, reverse(instructions[1:20]))(2019)
  0.951510 seconds (47.97 k allocations: 2.167 MiB)
3894

julia> @time reduce(∘, reverse(instructions[1:21]))(2019)
  1.894370 seconds (60.45 k allocations: 2.715 MiB)
6242

julia> @time reduce(∘, reverse(instructions[1:22]))(2019)
  3.748505 seconds (50.59 k allocations: 2.289 MiB)
1669

julia> @time reduce(∘, reverse(instructions[1:23]))(2019)
  6.638699 seconds (65.98 k allocations: 2.982 MiB, 0.12% gc time)
8337

julia> @time reduce(∘, reverse(instructions[1:24]))(2019)
 12.456682 seconds (68.45 k allocations: 3.096 MiB)
6563

julia> @time reduce(∘, reverse(instructions[1:25]))(2019)
 31.712616 seconds (73.44 k allocations: 3.296 MiB)
8178

仅添加一个组合函数似乎会使运行时间增加一倍。重新运行所有这些代码会使其速度更快:

julia> @time reduce(∘, reverse(instructions[1:2]))(2019)
  0.000019 seconds (9 allocations: 448 bytes)
2041

julia> @time reduce(∘, reverse(instructions[1:5]))(2019)
  0.000021 seconds (12 allocations: 752 bytes)
6951

julia> @time reduce(∘, reverse(instructions[1:10]))(2019)
  0.000020 seconds (17 allocations: 1.359 KiB)
4935

julia> @time reduce(∘, reverse(instructions[1:20]))(2019)
  0.000027 seconds (27 allocations: 4.141 KiB)
3894

julia> @time reduce(∘, reverse(instructions[1:25]))(2019)
  0.000028 seconds (32 allocations: 6.109 KiB)
8178

但是如果我再添加一个，那么它需要上一个的两倍

julia> @time reduce(∘, reverse(instructions[1:26]))(2019)
 60.287693 seconds (68.03 k allocations: 3.079 MiB)
3553

因此，似乎所有时间都花在将函数编译在一起，而对于 100 个函数，它花费的时间比我多得多。以下结果证实了这一点:

julia> @time reduce(∘, reverse(instructions[1:27]))
  0.000041 seconds (99 allocations: 10.859 KiB)
#52 (generic function with 1 method)

julia> @time precompile(ans, (Int,))
117.783710 seconds (79.01 k allocations: 3.650 MiB)
true

这是怎么回事？我将按我想的顺序运行函数，但为什么这种减少需要这么长时间才能编译？深层嵌套的组合需要很长时间才能编译，这似乎是 ∘ 函数本身的失败。这让我感到非常惊讶，这似乎是 ∘ 的一个非常基本的用例。基本上，编译时间似乎是 O(2^n)，其中 n 是您要组合在一起的函数的数量。这看起来是个大问题

Answer 1

我意识到我使用的是旧版本的 Julia。在最新版本(1.3)上，速度要快得多。如果你达到数千个(编译 3000 个函数组合在一起需要几秒钟)，它仍然开始变慢，但似乎不再是 O(2^n)