Efficiently generating the set of all words of length n from an alphabet in Julia

user_7183044 0
Viewed 54

While similar questions have already been posted on this website, none of them deal with the Julia language. I have already implemented a working version of the algorithm, and am looking for language-specific optimisations.

Here is the code I've written in Julia:

S(a::Array, n::Int64)::Array{Array} = n == 0 ? [[]] : vcat([push!.(deepcopy(S(a, n-1)), α) for α in a]...)

Although this code works as intended, it is quite slow and consumes a lot of memory.

I've tried optimising it slightly by avoiding recomputing S(a, n-1) several times:

S(a::Array, n::Int64)::Array{Array} = n == 0 ? [[]] : (arr::Array{Array} -> vcat([push!.(deepcopy(arr), α) for α in a]...))(S(a, n-1))

The issue of memory ineffciency, however, persists. Is there any way in which I can optimise this code to make it more memory efficient?

julia optimization arrays
1 Answers

I think the following does what you want.

using Base.Iterators
T(a,n) = product(repeated(a,n)...)

This is better in several ways. Firstly, it produces an iterator, so uses roughly no memory. Second, it is type stable, whereas the version you wrote produces arrays with eltype Any, which will make code that uses it type unstable.

Furthermore, it is much faster. 

julia> @time S([1,2,3,4,5,6,7,8,9], 6);
  1.767797 seconds (16.22 M allocations: 1.315 GiB, 20.28% gc time)

julia> @time T([1,2,3,4,5,6,7,8,9], 6);
  0.000013 seconds (17 allocations: 576 bytes)

julia> @time collect(T([1,2,3,4,5,6,7,8,9], 6));
  0.004837 seconds (20 allocations: 24.328 MiB)

Note that even when you collect the result to get the same answer (an array), it still is over 400x faster and allocates much less memory.

user_51413280
Related