On Wednesday, June 25, 2014 2:27:18 PM UTC+2, Mauro wrote:
> Could you pass a storage array to the function? Like so:
Thanks for your tips, Mauro. Thanks to Jason and Steven, too.
> - do as you did/above
I wrapped the the subsetsum function, providing a storage array as you
suggested and applying push! to it. This doubled speed compared to using an
inner function -- as Steven predicted --, and it was faster than utilizing
a global variable.
For those interested I append the code I finally used.
> - if you have an idea of the number of solutions, use
> `sizehint(sol, numsols)`. Or do sizehints in big junks.
No, I don't. I have done tests with randomly generated weights: There were
thousands and thousands of solutions where beforehand you'd wonder whether
there are any at all. These combinatorial things can be surprising.
> - run the computation twice, once to compute the number of solutions,
> the second time around to fill the `sol` array.
Using a global variable appears to take double time, so running the
subsetsum algorithm twice will likely not bring a definite benefit.
> No idea which one is fastest.
Here are some rough measurements I did with different approaches:
- Using inner function: 0.00065 secs
- Using global variable: 0.00048
- Using storage array: 0.00032
I feel this is really fast compared to my experiences in other languages
and systems.
function subsetsum(target::Int, weights::Array{Int, 1})
# check if weights are nondecreasing integers
n = length(weights)
x = fill(false, n)
X = Array{Bool, 1}[]
sss_inner(target, n, weights, x, 0, 1, sum(weights), X)
return X
end
function sss_inner(m::Int, n::Int, w::Array{Int,1}, x::Array{Bool,1},
s::Int, k::Int, r::Int, X::Array{Array{Bool,1},1})
global X
x[k] = true
if s + w[k] == m
push!(X, x[1:k])
else
if s + w[k] + w[k+1] <= m
sss_inner(m, n, w, x, s+w[k], k+1, r-w[k], X)
end
end
if s + r - w[k] >= m && s + w[k+1] <= m
x[k] = false
sss_inner(m, n, w, x, s, k+1, r-w[k], X)
end
end
# Example
julia> m = 2014;
julia> w = Int64[u^2 for u in 1:2:isqrt(m)];
julia> X = subsetsum(m, w);
julia> w[find(X[1])]
6-element Array{Int64,1}:
1
9
25
49
81
1849
julia> sum(w[find(X[1])])
2014
