Насколько эффективны методы push!() И append!() В Julia?

В этой странице говорится, что методы push!() и append!() очень эффективны.

Мой вопрос в том, насколько они эффективны?

А именно,

Если один знает размер конечного массива, еще быстрее перенаправить его или увеличить его с помощью append!()/push!(), будет так же эффективно?

Теперь рассмотрим случай, когда один не знает размер последнего массива. Например, объединение нескольких массивов в один большой массив (назовем его A).

Два способа достичь этого:

append!() - для каждого массива A, размер которого не был предварительно выделен.
Первые суммы размеров каждого массива, чтобы найти окончательный размер объединенного массива A. Затем предварительно выделите A и скопируйте содержимое каждого массива.

Какой из них был бы более эффективным в этом случае?

Ответ 1

Ответ на такой вопрос обычно: "это зависит". Например, какой массив размера вы пытаетесь сделать? Каков элемент-тип массива?

Но если вы только после эвристики, почему бы не запустить простой тест скорости? Например, следующий фрагмент:

function f1(N::Int)
    x = Array(Int, N)
    for n = 1:N
        x[n] = n
    end
    return(x)
end

function f2(N::Int)
    x = Array(Int, 0)
    for n = 1:N
        push!(x, n)
    end
    return(x)
end

f1(2)
f2(2)

N = 5000000000
@time f1(N)
@time f2(N)

предполагает, что использование push! примерно в 6 раз медленнее, чем предварительное выделение. Если вы использовали append! для добавления больших блоков с меньшими шагами, множитель почти наверняка будет меньше.

При интерпретации этих чисел сопротивляйтесь реакции коленного рефлекса "Что!? в 6 раз медленнее!?". Это число должно быть помещено в контексте того, насколько важно построить массив для всей вашей программы/функции/подпрограммы. Например, если построение массива содержит только 1% времени выполнения вашей процедуры (для большинства типичных процедур построение массива будет составлять намного меньше 1%), то, если ваша процедура выполняется в течение 100 секунд, 1 секунда тратится на массивы зданий, Умножьте это на 6, чтобы получить 6 секунд. 99 секунд + 6 секунд = 105 секунд. Таким образом, использование push! вместо предварительного выделения увеличивает время выполнения всей вашей программы на 5%. Если вы не работаете в высокочастотной торговле, вы, вероятно, не будете заботиться об этом.

Для себя, мое обычное правило таково: если я могу заранее распределить, то я предварительно распределю. Но если push! упрощает кодирование, с меньшей вероятностью появления ошибок и меньшим количеством попыток предварительно определить размер соответствующего массива, я использую push! без второй мысли.

Заключительное примечание: если вы хотите посмотреть на особенности работы push!, вам нужно будет вникать в подпрограммы C, поскольку источник julia просто обертывает ccall.

ОБНОВЛЕНИЕ: ОП задает в комментариях разницу между push! и операцией типа array(end+1) = n в MATLAB. Я недавно не кодировал MATLAB, но я сохраняю копию на своей машине, так как код для всех моих старых документов находится в MATLAB. Моя текущая версия R2014a. Я понимаю, что в этой версии MATLAB добавление в конец массива будет перераспределять весь массив. Напротив, push! в Julia работает, насколько мне известно, так же, как списки в .NET. Память, выделенная для вектора, динамически добавляется в блоки при увеличении размера вектора. Это значительно уменьшает объем перераспределения, который необходимо выполнить, хотя я понимаю, что некоторое перераспределение по-прежнему необходимо (я с удовольствием исправляюсь по этому вопросу). Поэтому push! должен работать намного быстрее, чем добавлять в массив в Matlab. Таким образом, мы можем запустить следующий код MATLAB:

N = 10000000;
tic
x = ones(N, 1);
for n = 1:N
    x(n) = n;
end
toc


N = 10000000;
tic
x = [];
for n = 1:N
    x(end+1) = n;
end
toc

Я получаю:

Elapsed time is 0.407288 seconds.
Elapsed time is 1.802845 seconds.

Итак, примерно 5-кратное замедление. Учитывая чрезвычайную не-строгость, применяемую в методологии синхронизации, может возникнуть соблазн сказать, что это эквивалентно делу Джулии. Но подождите, если мы снова запустим упражнение в Julia с N = 10000000, тайминги составляют 0,01 и 0,07 секунды. Явное различие в величине этих чисел с номерами MATLAB вызывает у меня очень нервничающее отношение к заявлению о том, что на самом деле происходит под капотом, и является ли законным сравнивать 5-кратное замедление в MATLAB с 6-кратным замедлением в Юлия. В принципе, я сейчас из глубины. Возможно, кто-то, кто знает больше о том, что делает MATLAB на самом деле под капотом, может предложить больше понимания. Что касается Джулии, я не очень похож на C-кодер, поэтому я сомневаюсь, что я получу очень много информации о том, как искать источник (который является общедоступным, в отличие от MATLAB).

Ответ 2

push! всегда будет медленнее, чем вставка в предварительно выделенный массив, если не по какой-либо другой причине, чем push! (1) вставляет элемент так же, как когда вы делаете это вручную, и (2) увеличивает длину массива. Две операции не могут быть быстрее, чем одна, когда одна из них является частью двух.

Однако, как отмечалось в других ответах, разрыв часто не настолько велик, что его беспокоит. Внутри (в прошлый раз, когда я проверил код), Джулия использует стратегию "рост за фактором-2", так что вам нужны только перераспределения log2(N).

Если вы заранее знаете размер массива, вы можете устранить перераспределение с помощью sizehint!. Поскольку вы можете легко проверить себя, это не исключает штраф производительности относительно вставки в предварительно выделенный массив, но он может уменьшить его.