Karoly Horvath
Karoly Horvath

Reputation: 96306

ruby array internals

How are ruby arrays internally implemented (mainly in CRuby, but any other info is welcomed)?

Are they growable arrays like a c++ vector or are they list based? What's the complexity of shift/unshift and accessing an element by index?

Upvotes: 14

Views: 2306

Answers (2)

sepp2k
sepp2k

Reputation: 370425

They're growable arrays which "grow at the end".

shift is O(1), unshift is O(n) and accessing by index is O(1). To the best of my knowledge this holds true for all ruby implementations, but it definitely does in MRI.

UPDATE: After this answer was originally written, Ruby was enhanced to make unshift amortized O(1). The enhanced array is in Ruby 2.0.0 and later, making shift, unshift, push, and pop all O(1) or amortized O(1).

Upvotes: 18

Tsuneo Yoshioka
Tsuneo Yoshioka

Reputation: 7874

unshift is O(N^2) in my 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]

Upvotes: 1

Related Questions