rubyarrays内部

如何在内部实现ruby数组（主要在CRuby中，但欢迎任何其他信息）？

它们是可扩展的数组，如c ++向量还是基于列表？ shift / unshift和按索引访问元素的复杂性是什么？

Answer 1

它们是可“生长在最后”的可生长arrays。

shift是O(1) ， unshift是O(n) ，索引访问是O(1) 。 据我所知，这适用于所有ruby实现，但它绝对适用于MRI。

Answer 2

unshift在我的ruby1.9中是O（N ^ 2）。

 $ /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]