ruby ​​array internals

Question

Làm thế nào các mảng ruby ​​được thực thi nội bộ (chủ yếu trong CRuby, nhưng bất kỳ thông tin nào khác được hoan nghênh)?

Chúng có thể phát triển các mảng như vectơ C++ hay chúng dựa trên danh sách? Sự phức tạp của sự dịch chuyển/unshift và truy cập một phần tử theo chỉ mục là gì?

Answer 1

Chúng là mảng có thể phát triển "tăng trưởng ở cuối".

shift là O(1), unshift là O(n) và truy cập theo chỉ mục là O(1). Theo hiểu biết tốt nhất của tôi, điều này đúng với tất cả các triển khai ruby, nhưng nó chắc chắn có trong MRI.

Answer 2

unshift là O (N^2) trong ruby1.9 của tôi.

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