具有许多函数的 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)