提高Julia中的性能并获得向量的最大args

Question

我一直在和来自Python的朱莉娅玩。我写了一些代码来解决这个难题。我在用蛮力的方法。代码在Python中运行需要一段时间（~30分钟），但在Julia中仍然需要大约3分钟。我确信这有点难看，因为我还在学习这门语言。我查看了优化器页面，在函数中输入了数据类型，并避免了全局变量。

using Primes

function mymax(state::Vector{Vector{Int64}})
    maxval,maxi,maxj=0,0,0
    for (i,row) in enumerate(state)
        for (j,val) in enumerate(row)
            if val>maxval
                maxval,maxi,maxj = val,i,j
            end
        end
    end
    return maxval,maxi,maxj
end

function neighbors(state::Vector{Vector{Int64}})
    prev,i,j = mymax(state)
    ip = Primes.isprime(prev+1)
    newstates=Vector{Vector{Vector{Int}}}()
    for (di,dj) = [(-1,0),(1,0),(0,1),(0,-1)]
        ni,nj = i+di,j+dj
        (ni<1 || nj<1 || ni>length(state) || nj>length(state[1])) && continue
        (state[ni][nj]!=0) && continue
        if field[ni][nj]==ip
            newstate=deepcopy(state)
            newstate[ni][nj]=prev+1
            push!(newstates,newstate)
        end
    end
    return newstates
end

function goal(state::Vector{Vector{Int64}})
    return sum(sum(state))==2080
end

function search(start_state::Vector{Vector{Int64}},field::Vector{Vector{Int64}})
    path = [start_state]
    level=0
    solutions = Vector{Vector{Vector{Int}}}()
    while true
        (length(path)==0) && (return solutions)
        println("***")
        println(level)
        println(length(path))
        println(mymax(path[end]))
        level+=1
        newpath = Vector{Vector{Vector{Int}}}()
        for p in path
            for n in neighbors(p)
                (goal(n)) && (push!(solutions,n))
                push!(newpath,n)
            end
        end
        path=deepcopy(newpath)
    end
end

field = [[1,0,0,0,1,0,0,0],
         [0,1,0,1,0,0,0,1],
         [1,0,0,0,0,0,1,0],
         [0,0,0,1,0,0,0,1],
         [0,0,1,1,1,0,0,0],
         [0,0,0,0,0,1,0,0],
         [1,0,0,0,1,0,1,0],
         [0,0,0,0,0,1,0,1]]

 start = [[0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,2,0,0,0,0],
          [0,0,0,1,0,0,0,0],
          [0,0,0,0,0,0,0,0],
          [0,0,0,0,0,0,0,0]]

solns = search(start,field)
print("Solutions found ")
println(length(solns))
for soln in solns
    display(soln)
end

与此相关的三个问题：

>

肯定有更好的方法来做函数mymax。我找到了一些关于阿格马克斯的建议，但这给我带来了一个大麻烦。它似乎返回总和最大的行的位置（在我的开始变量中工作，但不是一般！）

Vector{Vector{blah blah blah是正确的数据结构吗？或者我应该使用更优化的结构吗？@time返回这个：181.230324秒（214.55m分配：31.388gib，14.44%gc时间）。这似乎是很多分配，但我不确定如何诊断这个问题？

其他加快速度的技巧和窍门。我意识到我必须打开编译模式，这很有帮助！它仍然比我编写的Python代码快得多，所以这可能只是一个很大的问题空间（将成为一个很好的Euler项目问题！）。但我怀疑像我这样的新手是否编写过任何接近优化的代码。我知道这有点模糊，但我记得大约十年前，当我学习Python并被告知矢量化时。我知道这不适用于朱莉娅，但如果知道我没有错过任何重大的东西，那就太好了。

注意：我刚刚检查过，Python版本需要30分钟才能运行。因此，朱莉娅大约有10倍的进步，这当然值得拥有！然而，如果朱莉娅能有100倍的进步，我也不会感到惊讶。

Answer 1

感谢@PrzemyslawSzufel的评论。我用矩阵而不是向量的向量重新编写了代码。这只是来自python的语法问题。然后Findmax以更合理的方式运行（argmax等也是如此）。

using Primes

function neighbors(state::Matrix{Int64})
    prev,ij = findmax(state)
    ip = Primes.isprime(prev+1)
    newstates=Vector{Matrix{Int64}}()
    for dij = [CartesianIndex(-1,0),CartesianIndex(1,0),CartesianIndex(0,1),CartesianIndex(0,-1)]
        nij = ij+dij
        (nij[1]<1 || nij[2]<1 || nij[1]>size(state)[1] || nij[2]>size(state)[2]) && continue
        (state[nij]!=0) && continue
        if field[nij]==ip
            newstate=deepcopy(state)
            newstate[nij]=prev+1
            push!(newstates,newstate)
        end
    end
    return newstates
end

function goal(state::Matrix{Int64})
    return sum(state)==2080
end

function search(start_state::Matrix{Int64},field::Matrix{Int64})
    path = [start_state]
    level=0
    solutions = Vector{Matrix{Int}}()
    while true
        (length(path)==0) && (return solutions)
        println("***")
        println(level)
        println(length(path))
        println(findmax(path[end]))
        level+=1
        newpath = Vector{Matrix{Int}}()
        for p in path
            for n in neighbors(p)
                (goal(n)) && (push!(solutions,n))
                push!(newpath,n)
            end
        end
        path=deepcopy(newpath)
    end
end

field = [1 0 0 0 1 0 0 0;
         0 1 0 1 0 0 0 1;
         1 0 0 0 0 0 1 0;
         0 0 0 1 0 0 0 1;
         0 0 1 1 1 0 0 0;
         0 0 0 0 0 1 0 0;
         1 0 0 0 1 0 1 0;
         0 0 0 0 0 1 0 1]
start = [0 0 0 0 0 0 0 0;
          0 0 0 0 0 0 0 0;
          0 0 0 0 0 0 0 0;
          0 0 0 0 0 0 0 0;
          0 0 0 2 0 0 0 0;
          0 0 0 1 0 0 0 0;
          0 0 0 0 0 0 0 0;
          0 0 0 0 0 0 0 0]

solns = search(start,field)
print("Solutions found ")
println(length(solns))
for soln in solns
    display(soln)
end

这在17秒内找到了解决方案（因此，又有了10倍的改进，我们达到了我所期望的100倍python）。

运行@time搜索（开始，字段）会得到17.244326秒（58.45m分配：13.356gib，28.92%的gc时间）。

把这个答案看作是对我的发现的纪念，希望其他人会觉得它有用。如果您有更好的解决方案或更多要添加的内容，请随时添加。