Каково время работы shift / unshift в массиве ruby?

Question

Кто-нибудь знает, насколько эффективны shift и unshift в массиве ruby?

Удаление из начала массива и необходимость перемещения каждого элемента в памяти может стать очень неэффективным.Я предполагаю, что ruby ​​делает это каким-то другим способом.

Любая информация о следующем будет полезна:
- Алгоритмическое время выполнения
- Реализация
- Общая эффективность
- Будет сдвиг / отмена сдвига бытьдопустимо использовать для очереди (в чем-то вроде C ++ это не будет)

Спасибо!

Answer 1

В более старых версиях Ruby (до ~ 2012 г.) unshift была операцией O (n). Тем не менее, оптимизация была добавлена ​​в этот коммит и , выпущенный в Ruby 2.0.0 , что делает unshift амортизированным O (1) , что означает, что это в среднем гарантировано, что O (1), но отдельная операция может быть O (n). Это то же время, что и shift.

В этом посте по обмену CS Stack есть хорошее объяснение того, как это работает и как вы получаете амортизированное время выполнения O (1) (это примерно vector::push_back в C ++, но работает так же ).

Answer 2

Вы можете перейти по здесь и посмотреть исходный код C метода unshift (просто нажмите на блок описания).Это очень ясно: увеличить объем памяти, если у нас уже недостаточно, переместить текущее содержимое массива, скопировать переданные аргументы в свободное место в начале нашего блока памяти.Так что O(n) для unshift.

Answer 3

Я обнаружил, что самый простой и наиболее точный способ ответить на этот вопрос - проверить его.

require 'benchmark'

Benchmark.bm do |x|
    iterations = 10000000
    x.report("push") {
        a = []
        iterations.times do a.push(10) end
    }
    x.report("unshift") {
        a = []
        iterations.times do a.unshift(10) end
    }
    a = []
    iterations.times do a.push(10) end
    x.report("shift") {
        iterations.times do a.shift() end
    }
    a = []
    iterations.times do a.push(10) end
    x.report("pop") {
        iterations.times do a.pop() end
    }
end

В моей системе с запущенной версией ruby ​​2.0.0 это возвращает результаты:

             user     system      total        real
push     0.880000   0.030000   0.910000 (  0.917213)
unshift  0.920000   0.090000   1.010000 (  1.026208)
shift    0.780000   0.030000   0.810000 (  0.810293)
pop      0.710000   0.000000   0.710000 (  0.724865)

Кажется, что push, pop, shift и unshift занимают примерно одинаковое количество времени.

Повторный запуск этого кода с другими значениями для iterations дает мне результатыэта шкала пропорционально сумме, которую я изменил iterations.Это означает, что независимо от значения iterations каждая операция всегда занимает в среднем одно и то же время, а это означает, что время выполнения каждой операции не зависит от длины массива и поэтому имеет время выполнения O(1).

Я бы сказал, что это будет приемлемо для использования в качестве очереди.

Answer 4

Согласно этой статье , похоже, что она вообще не смещается, просто увеличивает указатель и возвращает его.Так что с точки зрения эффективности это смехотворно эффективно (O (1)).Однако в статье упоминается потенциальная утечка памяти, которая может присутствовать или не присутствовать в более поздних выпусках.