我有一些python代码,我试图移植到Julia学习这种可爱的语言.我在python中使用了生成器.移植后,在我看来(此时此刻)Julia在这个区域真的很慢!
我将部分代码简化为本练习:
想想4x4棋盘.找到每一个N-move长路,国际象棋王可以做到.在这个练习中,国王不允许在一条路径中的同一位置跳跃两次.不要浪费记忆 - >制作每条路径的发电机.
算法非常简单:
如果我们用数字签署每个位置:
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]]
蟒蛇
递归函数(生成器),它从点列表或(生成器......)的生成器放大给定路径:
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
我们可以看到有905776个长度为10的路径:
sum(1 for i in paths(10))
Out[89]: 905776
JULIA (此代码是由@gggg我们的讨论过程中创建这里)
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)
朱莉娅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
问题(S):
我们Julians正在这样说:重要的是要注意基准代码不是为绝对最大性能而编写的(计算recursion_fibonacci(20)的最快代码是常量文字6765).相反,基准测试用于测试每种语言中实现的相同算法和代码模式的性能.
在这个基准测试中,我们使用相同的想法.对于封闭到生成器的数组而言,只需简单循环 (没有numpy,numba,pandas或其他c-written和编译的python包)
假设朱莉娅的发电机非常慢吗？
我们可以做些什么才能让它变得非常快？
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
这要快得多.
朱莉娅比Python"更好的表现"并不神奇.其中大部分直接源于这样一个事实,即Julia可以弄清楚函数中每个变量的类型,然后为这些特定类型编译高度专业化的代码.这甚至适用于许多容器中的元素和像发电机这样的迭代物; 朱莉娅经常提前知道元素的类型.Python几乎不能轻易地(或者在很多情况下)进行这种分析,因此它的优化专注于改进动态行为.
为了让Julia的生成器提前知道它们可能生成哪种类型,它们封装了有关它们执行的操作和它们在类型中迭代的对象的信息:
julia> (1 for i in 1:16)
Base.Generator{UnitRange{Int64},getfield(Main, Symbol("##27#28"))}(getfield(Main, Symbol("##27#28"))(), 1:16)
奇怪##27#28的是,简单返回的匿名函数的类型1.当生成器到达LLVM时,它知道足以执行大量优化:
julia> function naive_sum(c)
s = 0
for elt in c
s += elt
end
s
end
@code_llvm naive_sum(1 for i in 1:16)
; Function naive_sum
; Location: REPL[1]:2
define i64 @julia_naive_sum_62385({ { i64, i64 } } addrspace(11)* nocapture nonnull readonly dereferenceable(16)) {
top:
; Location: REPL[1]:3
%1 = getelementptr inbounds { { i64, i64 } }, { { i64, i64 } } addrspace(11)* %0, i64 0, i32 0, i32 0
%2 = load i64, i64 addrspace(11)* %1, align 8
%3 = getelementptr inbounds { { i64, i64 } }, { { i64, i64 } } addrspace(11)* %0, i64 0, i32 0, i32 1
%4 = load i64, i64 addrspace(11)* %3, align 8
%5 = add i64 %4, 1
%6 = sub i64 %5, %2
; Location: REPL[1]:6
ret i64 %6
}
可能需要一分钟来解析那里的LLVM IR,但你应该能够看到它只是提取UnitRange(getelementptr和load)的端点,从彼此中减去它们(sub)并添加一个来计算总和而没有单个循环.
在这种情况下,它对朱莉娅有效:paths(10)有一个非常复杂的类型!你正在迭代地将那个生成器包装在过滤器中并展平并且还有更多的生成器.事实上,它变得如此复杂,朱莉娅只是放弃试图弄清楚并决定与动态行为一起生活.而且在这一点上,它不再具有超越Python的固有优势 - 实际上专注于许多不同的类型,因为它递归遍历对象将是一个明显的障碍.你可以通过观察看到这一点@code_warntype start(1 for i in paths(10)).
我对朱莉娅性能的经验法则是,避免分配的类型稳定的,去开发的代码通常在C的2倍之内,而动态,不稳定或向量化的代码在Python/MATLAB /其他更高级别的数量级内语言.通常它有点慢,因为其他更高级别的语言非常难以优化他们的情况,而Julia的大部分优化都集中在类型稳定的方面.这种深层嵌套的构造将您置于动态阵营中.
那么朱莉娅的发电机非常慢吗？本质上不是这样; 只是当它们变得如此深深地嵌套时,你就会遇到这种糟糕的情况.
不遵循相同的算法（并且不知道Python这样做的速度有多快），但是使用以下代码，Julia对于长度= 10的解决方案基本上是相同的，并且对于长度= 16的解决方案更好
\n\nIn [48]: %timeit sum(1 for path in paths(10)) \n1.52 s \xc2\xb1 11.4 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each) \n\njulia> @time sum(1 for path in pathsr(10)) \n 1.566964 seconds (5.54 M allocations: 693.729 MiB, 16.24% gc time) \n905776 \n\nIn [49]: %timeit sum(1 for path in paths(16)) \n19.3 s \xc2\xb1 15.7 ms per loop (mean \xc2\xb1 std. dev. of 7 runs, 1 loop each) \n\njulia> @time sum(1 for path in pathsr(16)) \n 6.491803 seconds (57.36 M allocations: 9.734 GiB, 33.79% gc time) \n343184 \n这是代码。我昨天刚刚了解了任务/频道，所以可能可以做得更好：
\n\nconst 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], \\\n[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]];\n\nfunction enlarger(num::Int,len::Int,pos::Int,sol::Array{Int64,1},c::Channel)\n if pos == len\n put!(c,copy(sol))\n elseif pos == 0\n for j=0:num\n sol[1]=j\n enlarger(num,len,pos+1,sol,c)\n end\n close(c)\n else\n for i in NEIG[sol[pos]+1]\n if !in(i,sol[1:pos])\n sol[pos+1]=i\n enlarger(num,len,pos+1,sol,c)\n end\n end\n end\nend\n\nfunction pathsr(len)\n c=Channel(0)\n sol = [0 for i=1:len]\n @schedule enlarger(15,len,0,sol,c)\n (i for i in c)\nend\n| 归档时间： |
|
| 查看次数： |
825 次 |
| 最近记录： |