I am trying to speed up the function that make partition of 1:n into equivalence classes according to boolfn
. I need the partition to be sorted, so using SimplePartition.jl or DataStructures.jl may not be optimized (since disjoint set structure are not sorted, and later sorting caused a lot of overhead).
function computePartition(n::Int, boolfn)
indices = collect(1:n)
part = Vector{Int}[] # can this be optimized, knowing that length(part) <= n?
it = 0
while !isempty(indices)
it += 1
class = [indices[1]]
append!(class, [j for j in indices[2:end] if boolfn(indices[1], j)]) # can this be speed up?
push!(part, class)
filter!(k->!(k in class), indices)
end
return part
end
My algorithm is not parallelizable at the level of the while loop. However,
[j for j in indices[2:end] if boolfn(indices[1], j)]
may be speed up because the computation can be parallelized. Does Julia parallel the array comprehension?