Подтвердить что ты не робот

Внутренние элементы рубинового массива

Как внедряются рубиновые массивы (в основном в CRuby, но любая другая информация приветствуется)?

Являются ли они растущими массивами, как вектор С++, или они основаны на списках? Какова сложность сдвига/смещения и доступа к элементу по индексу?

Ответ 1

Это растущие массивы, которые "растут в конце".

shift O(1), unshift есть O(n), а доступ по индексу O(1). Насколько мне известно, это справедливо для всех реализаций Ruby, но это определенно делает в MRI.

Ответ 2

unshift - это O (N ^ 2) в моем ruby1.9.

$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.push(i);}'
        0.03 real         0.02 user         0.00 sys
$ /usr/bin/time ruby -e 'n=100000;l=[];(1..n).each{|i| l.unshift(i);}'
        3.15 real         3.11 user         0.01 sys
$ /usr/bin/time ruby -e 'n=200000;l=[];(1..n).each{|i| l.unshift(i);}'
       12.96 real        12.85 user         0.03 sys
$ ruby -v
ruby 1.9.3p194 (2012-04-20 revision 35410) [x86_64-darwin11.3.0]