Эффективное создание набора всех слов длины n из алфавита в Julia - PullRequest
Новая
       10

Эффективное создание набора всех слов длины n из алфавита в Julia

3 голосов
/ 06 мая 2020

Подобные вопросы уже были размещены на этом веб-сайте, но ни один из них не касается языка Julia. Я уже реализовал рабочую версию алгоритма и ищу c оптимизаций для конкретного языка.

Вот код, который я написал на Julia: 

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

Хотя этот код работает так, как задумано, он довольно медленный и потребляет много памяти.

Я попытался немного оптимизировать его, избегая повторного вычисления S(a, n-1) несколько раз: 

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

Однако проблема нехватки памяти сохраняется. Есть ли способ оптимизировать этот код, чтобы сделать его более эффективным с точки зрения памяти?

1 Ответ

4 голосов
/ 06 мая 2020

Я думаю, что следующее делает то, что вы хотите. 

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

Это лучше во многих отношениях. Во-первых, он создает итератор, поэтому почти не использует памяти. Во-вторых, он является стабильным по типу, тогда как написанная вами версия создает массивы с eltype Any, что делает код, который его использует, нестабильным.

Более того, это намного быстрее. 

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)

Обратите внимание, что даже когда вы собираете результат, чтобы получить тот же ответ (массив), он все равно более чем в 400 раз быстрее и выделяет гораздо меньше памяти.

...