红宝石阵列内部

红宝石阵列在内部如何实现（主要在CRuby中，但欢迎任何其他信息）？红宝石阵列内部

它们是可扩展的数组像C++向量还是它们是基于列表？移位/不移位和按索引访问元素的复杂性是什么？

来源

2011-09-05 Karoly Horvath

只需签出SVN depo并阅读源代码。 C程序员的实现并不是很难。 – texasbruce

它们是可增长的阵列，“增长到最后”。

shift是O(1)，unshift是O(n)和通过索引访问是O(1)。据我所知，这对所有的ruby实现都适用，但它绝对在MRI中。

来源

2011-09-05 15:32:14 sepp2k

我不确定移位总是O（N）。如果我没有记错，内存块的开始和第一个项目的索引分别进行跟踪，所以您可以通过递增firstItem索引来执行O（1）移位。如果你没有做过任何班次，那么不换档只有O（N）。 – AShelly

@AShelly：你似乎对'shift'是正确的（尽管它实际上并不追踪起始索引，而是使数组共享），但'unshift'肯定是'O（n）' - 它调用' memmove“，不管是什么。 – sepp2k

有人应该做一些基准测试。 –

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]

来源

2012-11-12 13:43:50

如果我错了，请纠正我，但这是否表明不移位具有二次时间复杂性？如果不移位是线性的，当你将n从100,000增加到200,000时，你不会指望花费翻倍的时间。由于n增加了2倍，完成算法所需的时间增加了4倍。操作次数与数据集平方的大小成正比。 – louism2

@ louism2 right ...我修正了O（N^2），并注意到unshift（）在Ruby2中是O（N），在Ruby1.9中是O（N^2）。 –

如果unshift是O（n），并且您将它称为n次，则需要O（n^2）次..另外，我想你想为一个趋势需要两个以上的数据点.. – olleicua

红宝石阵列内部

回答

相关问题