What is the runtime shift / shift time in a ruby ​​array

Question

Does anyone know how effective shifting and shifting in a ruby ​​array are?

Removing from the beginning of the array and moving each element in memory can become very inefficient. I assume Ruby does it differently.

Any information on the following would be helpful:
- Algorithmic runtime
- Implementation
- Overall effectiveness
- Will the offset / offset acceptable for use in the queue (something like C ++ will not)

Thanks!

Answer 1

In older versions of Ruby (before ~ ​​2012), unshift was unshift O (n). However, optimization was added in this commit and released in Ruby 2.0.0 , which makes unshift depreciate O (1), which means that it is guaranteed, on average, to be O (1), and an individual operation can be O (n). This is the same run time as shift .

This CS Stack exchange post has a good explanation of how this works and how you get the amortized O (1) runtime (this is for C ++ vector::push_back , but it works the same way).

Answer 2

You can go here and see the C source code of the unshift method (just click on the description block). This is very clear: increase the amount of memory, if it’s not enough for us, move the current contents of the array, copy the arguments passed to the free space at the beginning of our memory block. So, O(n) for unshift .

Answer 3

I found that the easiest and most accurate way to answer this question is to compare it.

 require 'benchmark' Benchmark.bm do |x| iterations = 10000000 x.report("push") { a = [] iterations.times do a.push(10) end } x.report("unshift") { a = [] iterations.times do a.unshift(10) end } a = [] iterations.times do a.push(10) end x.report("shift") { iterations.times do a.shift() end } a = [] iterations.times do a.push(10) end x.report("pop") { iterations.times do a.pop() end } end 

On my system running ruby ​​version 2.0.0 this returns the results:

  user system total real push 0.880000 0.030000 0.910000 ( 0.917213) unshift 0.920000 0.090000 1.010000 ( 1.026208) shift 0.780000 0.030000 0.810000 ( 0.810293) pop 0.710000 0.000000 0.710000 ( 0.724865) 

It seems that push , pop , shift and unshift take about the same amount of time.

Re-running this code with different values ​​for iterations gives me results that scale in proportion to the number of iterations changed. This means that regardless of the value of iterations each operation always takes on average the same time, that is, the execution time of each operation does not depend on the length of the array and therefore has an O(1) execution time.

I would say that it would be acceptable to use as a queue.

Answer 4

According to this article , it doesn't seem to move at all, just increase the pointer and return it. So in terms of efficiency, it is ridiculously effective (O (1)). However, the article mentions a potential memory leak that may or may not be present in later releases.