python程序的yield生成器返回迭代器。Julia中没有这个语法,用一个局部的Dict来代替。

N,M = 2,3

def successors((directions, blocked)):
    newBlocked = []
    for i,b in enumerate(blocked):
        if directions[i]<directions[i+1]:
            if not b:
                newBlocked2 = newBlocked+[False]+list(blocked[i+1:])
                if i>0: newBlocked2[i-1]=False
                yield (directions[:i]+(directions[i+1],directions[i])+directions[i+2:], 
                       tuple(newBlocked2))
            newBlocked.append(True)
        else:
            newBlocked.append(b)

start = ( (0,)*N+(1,)*M+(2,)*N+(3,)*M,    (False,)*(2*N+2*M-1))

perm2count = {start:1}

while perm2count:
    perm2newCount = {}
    for conf,freq in perm2count.items():
        for newConf in successors(conf):
            perm2newCount[newConf] = perm2newCount.get(newConf,0) + freq
    if not perm2newCount: print perm2count
    perm2count = perm2newCount

#With a very minor modification, the same code can also solve generalisations to polygons with more (or less) than 8 corners.
#Ns = map(int,sys.argv[1:])
#start = ( tuple([n for n,f in enumerate(Ns) for _ in range(f)]),(False,)*(sum(Ns)-1))

enumerate用一个局部变量作计数器代替。Julia数组的连接用vcat。判断是否空集用length函数代替。数组下标由0改为1。

N,M=2,3

#start1=Tuple{Array{Int32,1},BitArray{1}};
start1=(vcat(fill(0,N),fill(1,M),fill(2,N),fill(3,M)),falses(2*N+2*M-1))


perm2count = Dict{Tuple{Array{Int32},BitArray{1}},Int32}();
perm2count[start1]=1

function successors(directions::Array{Int32,1}, blocked::BitArray{1})
    yield1=Dict{Tuple{Array{Int32,1},BitArray{1}},Int32}();
    newBlocked = falses(2*N+2*M-1);
    i=0
    for b in blocked
        i=i+1
        if directions[i]<directions[i+1]
            if  ! b
                newBlocked2 = vcat(newBlocked[1:i-1],[false],blocked[i+1:end])
                if i>1  newBlocked2[i-1]=false end;
                yield1[vcat(directions[1:i-1],directions[i+1],directions[i],directions[i+2:end]), (newBlocked2)]=1
            end;
            newBlocked[i]=true;
        else
            newBlocked[i]=b;
        end;
    end;
    yield1;
end

while length(perm2count)!=0
    perm2newCount =Dict{Tuple{Array{Int32},BitArray{1}},Int32}();
    for (conf,freq) in perm2count
        for (newConf,v) in successors(conf[1],conf[2])
            perm2newCount[newConf] = get(perm2newCount,newConf,0) + freq
        end;
    end;
    if length(perm2newCount)==0 print(perm2count) end;
    perm2count = perm2newCount
end;

这样改写后的Julia程序与Python的性能差距有点大

D:\>a\timer d:\pypy\pypy a.py 2 4

Kernel Time  =     0.093 = 00:00:00.093 =   5%
User Time    =     1.606 = 00:00:01.606 =  88%
Process Time =     1.700 = 00:00:01.700 =  93%
Global Time  =     1.810 = 00:00:01.810 = 100%


julia> @time include("d:\\a.txt")
8.260901 seconds (42.49 M allocations: 1.045 GiB, 16.43%gc time)

如果把vcat改为copy!,速度提高了不少。

 #               newBlocked2 = vcat(newBlocked[1:i-1],[false],blocked[i+1:end])
newBlocked2= falses(2*N+2*M-1);
copy!(newBlocked2,1,newBlocked,1,i);
copy!(newBlocked2,i+1,blocked,i+1,2*N+2*M-1-i);
newBlocked2[i]=false;

 #               yield1[cat(1,directions[1:i-1],directions[i+1],directions[i],directions[i+2:end]), 
 #                      (newBlocked2)]=1
dir2=zeros(2*N+2*M);
copy!(dir2,directions);
dir2[i],dir2[i+1]=dir2[i+1],dir2[i] ;
yield1[dir2,newBlocked2]=1;
---改写cat(directions)
4.717739 seconds (14.79 M allocations: 567.525 MiB, 19.88% gc time)
---再改写newBlocked2 = vcat
3.585000 seconds (9.33 M allocations: 395.747 MiB, 22.44% gc time)

把Array{Int32}改为Array{Int8},反而空间和时间都增加了

4.350975 seconds (10.63 M allocations: 455.729 MiB, 17.68% gc time)

奇怪的是,把dir2=zeros(2*N+2*M);改为dir2=zeros(Int32,2*N+2*M);按理类型与directions一致了,又减少了空间(Float64->Int32),应该变快,结果却反而慢了很多。

7.799579 seconds (11.69 M allocations: 411.982 MiB, 10.38% gc time)