Help speedup a brute-force solution

General Usage Performance
1

The following function calculates all possible subsets of a set 1:n such that all subsets are primes. This is only a brute-force algorithm to test a solution, so it’s too slow as expected. The number of allocations is huge because of too many short vectors generated from partitioning of an n-element vector. How can I improve upon this a bit? I tried multithreading and got a best-case of 2X speedup because this seems memory bound.

using Primes 
using Combinatorics

function mprime(k)
	v = 1
	n = 0 
	for i in k
		n += v*i
		v *= 10
	end  
	isprime(n)
end

function brute118(n)
    p = permutations(1:n) 
    r = partitions.(p) 
    s = Set{Vector{Vector{Int64}}}()
    for i in r 
    	for j in i
    		valid = true  
    		for k in j 
    			mprime(k) || (valid = false; break)
    		end
    		valid && push!(s,sort(j))
    	end 
    end 
    length(s)
end

n = 7
@time brute118(n)                                                            
  2.086856 seconds (45.65 M allocations: 2.937 GiB, 16.69% gc time)
1205
2

Can you use views?

3

Yes, I tried views, but it made no difference. I guess because the vectors are short (many are of length 1 already), the view is no lighter than the vector itself. I’m thinking of writing a version of partition that returns a vector of numbers directly instead of vector of vectors, it would be much faster.

1 Like
4

I would try to find where are these allocations and if they are in the functions maybe modify them to use views and other non-allocating paradigms

2 Likes
5

partitions generate new vectors on each iteration, so there is no way to avoid allocations. You can try to rewrite algorithm without using partitions (roll out your own allocation free implementation)

6

don’t get what this is saying, i think it’s not precise

7

to make slightly more clear what you are doing, your mprime is

mprime(k)=isprime(evalpoly(10,k))

8

and thus your code could be

mprime(k)=isprime(evalpoly(10,k))

function brute118(n)
    p = permutations(1:n) 
    r = partitions.(p) 
    s =[sort(j) for i in r, j in i if all(mprime,j)]
    length(s)
end
9

I would suggest to directly write a backtrack algorithm to generate your partitions. Like this, you can avoid allocations, and you can easily add pruning. (Whenever you build a subset of your partition, you can already check if it is prime, this will prune a significant portion of the search space).
Looking at your definition of mprime, you can also prune if the first element of your subset is 5 or an even number (if your subset contain more than 1 element)

2 Likes
10

I wrote my version of partition using recursion which is quite slow. But the problem is not speed here because I thought I will be able to generate significantly fewer candidates which are all primes. It turns out to be extremely difficult to intervene in the algorithm below because the subsets are built recursively and I can’t predict which subset will end up not being prime. Any ideas?

function partition(collection::AbstractVector{T}) where T
    length(collection) == 1 && return [[collection]]
    result = Vector{Vector{Vector{T}}}(undef,0)
    first = collection[1]
    for smaller in partition(collection[2:end])
        # insert `first` in each of the subpartition's subsets
        for n in eachindex(smaller)
            push!(result, [smaller[1:n-1]..., [first; smaller[n]], smaller[n+1:end]...])
        end
        # put `first` in its own subset
        push!(result, [[first],smaller...])
    end
    return result
end

println.(partition(1:3))
[[1, 2, 3]]
[[1], [2, 3]]
[[1, 2], [3]]
[[2], [1, 3]]
[[1], [2], [3]]
11

This is very nice and terse, but the comprehension complains about i is not defined.

12

Well, thank you all for your contributions, I learned from this a lot. Now when I think about it again, I realize that I was doing too many permutations prior to partitioning which resulted in too many repeated sets, most of them are not prime. Here I reversed that order and permuted only needed subsets. It is significantly faster now with few allocations.

using Primes 
using Combinatorics

mprime(k) = isprime(evalpoly(10,k))

function brute1180(n)
    total = 0
    for i in partitions(1:n)
        mul = 1
        for j in i
            mul *= sum(mprime, permutations(j))
            mul == 0 && break
        end 
        total += mul
    end 
    total
end

@btime brute1180(7)
  4.647 ms (77712 allocations: 6.37 MiB)
1205
1 Like
13

Sorry, it should have been

s =[sort(j) for i in r for j in i if all(mprime,j)]

3 Likes
14

You can still gain more time with good pruning rules.
Consider the following property (in base 10) :
if sum(k) = 0 mod 3 and k!=[3], then mprime(permutation(k)) = false for all permutation(k)
For the generation of partitions, if one of the subsets have this property, then you don’t need to generate all the partitions containing this subset. You can make your own algorithm for generating partitions or maybe adapt the ones from Combinatorics.
You can also prune a subset k of a partition if gcd(k) != 0 && ( length(k)>1 || !isprime(k[1]) )
Edit : When you have generated a subset of your partition, after checking the two previous conditions, you can also already list the prime permutations. Like this, if there is none, you can already prune this subset.

For the generation of the permutations, you can prune the permutations where the first element is 5 or an even number (in base 10).

2 Likes