Improve performance in Julia and get maximum args of a vector

user_3084178 0
Viewed 63

I've been playing around with Julia coming from Python. I wrote some code to figure out all the solutions to this puzzle. I'm doing a pretty brute force sort of method. The code takes a while (~30 min) to run in Python, but in Julia still takes about 3 minutes. I'm sure this is a little ugly as I'm still learning the language. I looked at the optimizer page and put in the data types in the function and avoided globals.

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

Three questions related to this:

  1. There must be a better way to do the function mymax. I found suggestions for argmax, but that caused a whole rabbit hole for me. It seems to return the position of the row whose sum is largest (which worked in my start variable, but not in general!)

  2. Is Vector{Vector{ blah blah the right data structure? Or is there some more optimized structure I should be using? @time returned this: 181.230324 seconds (214.55 M allocations: 31.388 GiB, 14.44% gc time). That seems like a lot of allocations, but I'm not sure how to diagnose this?

  3. Other tips and tricks for getting this faster. I realized that I had to switch on Compiled Mode, which helped! It's still way faster than the Python code I wrote, so maybe this is just a big problem space (would make a good Euler Project problem!). But I doubt that a newb like me has written anything close to optimized code. I know this is a little vague, but I remember a decade or so ago when I was learning Python and being told about vectorization. I know that doesn't apply to Julia, but it would be nice to know I'm not missing anything huge.

Note: I just checked, and the Python version takes 30 minutes to run. So Julia is about a 10-fold improvement, which is certainly worth having! However, I wouldn't be surprised if a 100-fold improvement is possible moving to Julia.

julia optimization
1 Answers

Thanks to @PrzemyslawSzufel's comments. I re-wrote the code with matrix rather than vector of vectors. This was just a syntax issue coming from python. Findmax then behaves in a more reasonable way (as does argmax etc).

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

This finds the solutions in 17 seconds (so another 10-fold improvement getting us to the 100x python I was expecting).

Running @time search(start,field) gives 17.244326 seconds (58.45 M allocations: 13.356 GiB, 28.92% gc time).

Consider this answer a memorialization of my discovery in the hope someone else finds it useful. If you have a better solution or more to add, please feel free to add it.

user_30841780
Related