紅寶石陣列內部

紅寶石陣列在內部如何實現（主要在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

紅寶石陣列內部

回答

相關問題