ruby array internals

Question

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?

Just checkout the SVN depo and read the source code. The implementation is not really hard for a C programmer. — SwiftMango
– SwiftMango, Commented Nov 12, 2012 at 13:46

Old Pro · Accepted Answer · 2019-01-03 05:30:34Z

18

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).

edited Jan 3, 2019 at 5:30

Old Pro

25.8k8 gold badges65 silver badges115 bronze badges

answered Sep 5, 2011 at 15:32

sepp2k

372k56 gold badges687 silver badges687 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

AShelly Over a year ago

I'm not sure shift is always O(N). If I recall correctly, the beginning of the memory block and the index of the first item are tracked separately, so you can do an O(1) shift by incrementing the firstItem index. Unshift is only O(N) if you havent done any shifts.

sepp2k Over a year ago

@AShelly: You seem to be right about shift (though it does not actually keep track of the starting index, but instead makes the array shared), but unshift definitely is O(n) - it calls memmove on the array no matter what.

olleicua Over a year ago

unshift appears to be O(1) in ruby 2.2

Tsuneo Yoshioka · Accepted Answer · 2014-09-17 00:54:51Z

1

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]

edited Sep 17, 2014 at 0:54

answered Nov 12, 2012 at 13:43

Tsuneo Yoshioka

7,9144 gold badges39 silver badges34 bronze badges

5 Comments

degreesoffun Over a year ago

Correct me if I'm wrong but doesn't this show that unshift has quadratic time complexity? If unshift was linear, as you increase n from 100,000 to 200,000 wouldn't you expect the time taken to double. As n is increased by a factor of 2, the time taken to complete the algorithm is increased by a factor of 4. The number of operations is proportional to the size of the data-set squared.

Tsuneo Yoshioka Over a year ago

@louism2 right... I fixed to O(N^2), and noticed that unshift() is O(N) in Ruby2, and O(N^2) in Ruby1.9 .

olleicua Over a year ago

If unshift is O(n) and you call it n times it will take O(n^2) time.. also I imagine you want more than two data points for a trend..

olleicua Over a year ago

You want something like n=100000;b=1000;l=(1..n).to_a;b.times{l.unshift(1);} (b stands for benchmark, keep b the same and varry n)

olleicua Over a year ago

I'm getting roughly O(n) on ruby-1.9.3-p551 and interestingly O(1) on ruby-2.2.2

Collectives™ on Stack Overflow

ruby array internals

2 Answers 2

3 Comments

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related