Julia - 王者之道(发电机性能)

Question

我有一些 python 代码，我试图将其移植到 Julia 来学习这种可爱的语言。我在 python 中使用了生成器。移植后，在我看来(此刻)Julia 在这方面真的很慢!

我将部分代码简化为这个练习:

想想 4x4 棋盘。找到国际象棋国王能做到的每一条 N 步长路。在这个练习中，国王不允许在一条路径的同一位置跳跃两次。不要浪费内存 -> 为每条路径创建一个生成器。

算法非常简单:

如果我们用数字签署每个位置:

0  1  2  3
4  5  6  7
8  9  10 11
12 13 14 16

点 0 有 3 个邻居(1、4、5)。我们可以为每个点的每个邻居找到一个表:

NEIG = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]]

Python

递归函数(生成器)，它从点列表或(...)点生成器放大给定路径:

def enlarge(path):
    if isinstance(path, list):
        for i in NEIG[path[-1]]:
            if i not in path:
                yield path[:] + [i]
    else:
        for i in path:
            yield from enlarge(i)

给出给定长度的每条路径的函数(生成器)

def paths(length):
    steps = ([i] for i in range(16))  # first steps on every point on board
    for _ in range(length-1):
        nsteps = enlarge(steps)
        steps = nsteps
    yield from steps

我们可以看到长度为 10 的路径有 905776 条:

sum(1 for i in paths(10))
Out[89]: 905776

Julia ( this code 是由 @gggg 在我们的讨论期间创建的 here )

const NEIG_py = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]];
const NEIG = [n.+1 for n in NEIG_py]
function enlarge(path::Vector{Int})
    (push!(copy(path),loc) for loc in NEIG[path[end]] if !(loc in path))
end
collect(enlarge([1]))
function enlargepaths(paths)
    Iterators.Flatten(enlarge(path) for path in paths)
end
collect(enlargepaths([[1],[2]]))
function paths(targetlen)
    paths = ([i] for i=1:16)
    for newlen in 2:targetlen
        paths = enlargepaths(paths)
    end
    paths
end
p = sum(1 for path in paths(10))

基准

在 ipython 中我们可以计时:

python 3.6.3:

%timeit sum(1 for i in paths(10))
1.25 s ± 15.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

Julia 0.6.0

julia> @time sum(1 for path in paths(10))
  2.690630 seconds (41.91 M allocations: 1.635 GiB, 11.39% gc time)
905776

Julia 0.7.0-DEV.0

julia> @time sum(1 for path in paths(10))
  4.951745 seconds (35.69 M allocations: 1.504 GiB, 4.31% gc time)
905776

问题:

我们朱利安人是saying this :需要注意的是，基准测试代码并不是为了绝对最大性能而编写的(计算 recursion_fibonacci(20) 最快的代码是常量文字 6765)。相反，编写基准测试是为了测试在每种语言中实现的相同算法和代码模式的性能。

在此基准测试中，我们使用相同的想法。对于包含在生成器中的数组的循环来说很简单。 (没有来自 numpy、numba、pandas 或其他 c 编写和编译的 python 包)

假设 Julia 的生成器非常慢，对吗？

我们可以做些什么来让它变得非常快？

Answer 1

const NEIG_py = [[1, 4, 5], [0, 2, 4, 5, 6], [1, 3, 5, 6, 7], [2, 6, 7], [0, 1, 5, 8, 9], [0, 1, 2, 4, 6, 8, 9, 10], [1, 2, 3, 5, 7, 9, 10, 11], [2, 3, 6, 10, 11], [4, 5, 9, 12, 13], [4, 5, 6, 8, 10, 12, 13, 14], [5, 6, 7, 9, 11, 13, 14, 15], [6, 7, 10, 14, 15], [8, 9, 13], [8, 9, 10, 12, 14], [9, 10, 11, 13, 15], [10, 11, 14]];
const NEIG = [n.+1 for n in NEIG_py];

function expandto(n, path, targetlen)
    length(path) >= targetlen && return n+1
    for loc in NEIG[path[end]]
        loc in path && continue
        n = expandto(n, (path..., loc), targetlen)
    end
    n
end

function npaths(targetlen)
    n = 0
    for i = 1:16
        path = (i,)
        n = expandto(n, path, targetlen)
    end
    n
end

基准(执行一次 JIT 编译后):

julia> @time npaths(10)
  0.069531 seconds (5 allocations: 176 bytes)
905776

这要快得多。