В Julia, более ли эффективно вырастить кортеж спереди или сзади? - PullRequest
Новая
       13

В Julia, более ли эффективно вырастить кортеж спереди или сзади?

5 голосов
/ 27 марта 2020

Если у меня есть рекурсивная функция, которая создает кортеж, где в каждой функции она создает новый кортеж, добавляя / добавляя элемент к кортежу, лучше ли увеличивать его по направлению вперед или назад? Это имеет значение? Является ли один из них проще для компилятора, даже если он в конечном итоге выполняет то же самое?

Возьмите эту глупую функцию в качестве примера и представьте, что мне все равно, будут ли числа увеличиваться или уменьшаться (так как я всегда можно настроить вызывающий код так, чтобы он работал в любом случае): 

julia> function tuple_one_through_n(n, t=())::Tuple
           if n === 0
               t
           else
               tuple_one_through_n(n-1, (n, t...))
           end
       end
tuple_one_through_n (generic function with 2 methods)

julia> tuple_one_through_n(5)
(1, 2, 3, 4, 5)

Есть ли основания предпочитать брызги t до n или после? Спасибо!

РЕДАКТИРОВАТЬ: Для большего контекста: мы добавляем кортежи подобным образом, потому что мы фактически используем это как неизменяемую трассировку функции, а создание нового кортежа путем добавления является потокобезопасным, поэтому он работает, даже если мы порождаем новые задачи: каждая задача получит свой собственный растущий след стека, который отслеживает всех вызывающих.

Я думаю, что лучшим вариантом, вероятно, будет что-то вроде неизменного PersistentVector из https://github.com/JuliaCollections/FunctionalCollections.jl/blob/master/README.md, но для самого простого первого прохода я просто использовал кортежи, и мне было интересно, есть ли какая-либо причина отдавать предпочтение тому или иному заказу. :) Поскольку у некоторых людей, вероятно, есть действительный вариант использования для выращивания кортежей, я подумал, что спросить.

Ответы [ 3 ]

4 голосов
/ 27 марта 2020

Это вызовет динамическую отправку c и будет настолько медленным, что ответ на вопрос не будет иметь значения. И если все это разворачивается, то это, очевидно, также не имеет значения, поскольку будет сгенерировано то же выражение.

Кортеж кажется неправильным для использования здесь (увеличение его до длины n будет равно O (n ^ 2) в общем)

2 голосов
/ 27 марта 2020

Используйте Vector с, а не Tuple с. Tuple s являются неизменными, что на практике означает, что они должны быть воссозданы с каждым шагом l oop. Добавьте элемент в конец Array. Рассмотрим следующий пример: 

function array_one_through_n(n, t=Int[])
   if n == 0
       t
   else
      append!(t,n)
      array_one_through_n(n-1, t)
  end
end

А теперь тесты: 

julia> @btime tuple_one_through_n(20);
  495.855 ns (18 allocations: 1.97 KiB)

julia> @btime array_one_through_n(20);
  280.345 ns (5 allocations: 624 bytes)

Обратите внимание, что процентная разница будет увеличиваться с увеличением n.

Last, но не в последнюю очередь. Если это возможно, предварительно выделите Vector для результатов, а не непрерывно расширяйте его. Рассмотрим код: 

function array_one_through_n_pre(n, t=Vector{Int}(undef, n))
   if n == 0
       t
   else
      t[n]=n
      array_one_through_n_pre(n-1, t)
  end
end

А теперь тест (еще в 3 раза быстрее): 

julia> @btime array_one_through_n_pre(20);
  73.456 ns (1 allocation: 240 bytes)
0 голосов
/ 28 марта 2020

Спасибо @KristofferCarlsson и @PrzemyslawSzufel за ваши ответы. Да, разбиваться на такие кортежи - плохая идея в любом направлении; Я просто ленился.

Вероятно, правильная структура данных для чего-то вроде этого - просто связанный список, который прекрасно работает и поддерживает ветвление из нескольких потоков, каждый из которых разделяет историю до ветвления, что точно что я хотел. Я просто go с этим. Спасибо! 

julia> struct Node
          n::Int
          next::Union{Nothing,Node}
       end

julia> function tuple_one_through_n(n, t=nothing)::Node
           if n === 0
               t
           else
               tuple_one_through_n(n-1, Node(n, t))
           end
       end
tuple_one_through_n (generic function with 2 methods)

julia> using BenchmarkTools

julia> @btime tuple_one_through_n(10)
  87.694 ns (10 allocations: 320 bytes)
Node(1, Node(2, Node(3, Node(4, Node(5, Node(6, Node(7, Node(8, Node(9, Node(10, nothing))))))))))```
...