運行時間Array＃unshift vs Array＃shift

Question

我預計Array#shift和Array#unshift的運行時間都是Θ(n)。原因是機器需要遍歷每個陣列成員並將其分配給左側或右側的鍵。

在Array#unshift的情況下，假設只有一個值作爲參數傳入並且存在大量數組成員，我假定array[0]的值賦值對運行時間沒有顯着影響。換句話說，當數組成員數很多，並且傳入Array#unshift的變量數很低時，我預計Array#shift和Array#unshift具有相同的運行時間。

在Ruby 2.1.2上運行基準測試時，這些假設並不適用。爲什麼？

代碼：

require 'benchmark' 

GC.disable  

number_of_elements = 25_600_000 

a1 =[] 
a2 = [] 
a3 = [] 
a4 = [] 
q1 = Queue.new 
q2 = Queue.new 

puts number_of_elements 

number_of_elements.times do 
    q1.enq(true) 
    q2.enq(true) 
    a1 << true 
    a2 << true 
    a3 << true 
    a4 << true 
end 

number_of_operations = 1 

Benchmark.bm do |bm| 
    puts "Queue#enq('test')" 
    bm.report do  
    number_of_operations.times { q1.enq('test') } 
    end 

    puts "Queue#deq" 
    bm.report do  
    number_of_operations.times { q2.deq } 
    end 

    puts "Array#shift" 
    bm.report do 
    number_of_operations.times { a1.shift } 
    end 

    puts "Array#unshift" 
    bm.report do 
    number_of_operations.times { a2.unshift('test') }  
    end 

    puts "Array#pop" 
    bm.report do 
    number_of_operations.times { a3.pop } 
    end 

    puts "Array#<<" 
    bm.report do 
    number_of_operations.times { a4 << 'test' } 
    end  
end 

結果：

25600000 
     user  system  total  real 
Queue#enq('test') 
    0.000000 0.000000 0.000000 ( 0.000006) 
Queue#deq 
    0.010000 0.020000 0.030000 ( 0.029928) 
Array#shift 
    0.010000 0.020000 0.030000 ( 0.032203) 
Array#unshift 
    0.080000 0.060000 0.140000 ( 0.143272) 
Array#pop 
    0.000000 0.000000 0.000000 ( 0.000004) 
Array#<< 
    0.000000 0.000000 0.000000 ( 0.000007) 

Answer 1

在MRI紅寶石2.1.2，unshift不realloc的數組，並將其複製完全：

   static VALUE 
rb_ary_unshift_m(int argc, VALUE *argv, VALUE ary) 
{ 
    long len = RARRAY_LEN(ary); 

    [...] 

    ary_ensure_room_for_unshift(ary, argc); 
    ary_memcpy(ary, 0, argc, argv); 
    ARY_SET_LEN(ary, len + argc); 
    return ary; 
} 

shift顯然不總是做這樣的事情：

   static VALUE 
rb_ary_shift_m(int argc, VALUE *argv, VALUE ary) 
{ 
    VALUE result; 
    long n; 

    [...] 

    rb_ary_modify_check(ary); 
    result = ary_take_first_or_last(argc, argv, ary, ARY_TAKE_FIRST); 
    n = RARRAY_LEN(result); 
    if (ARY_SHARED_P(ary)) { 
     if (ARY_SHARED_OCCUPIED(ARY_SHARED(ary))) { 
      ary_mem_clear(ary, 0, n); 
     } 
     ARY_INCREASE_PTR(ary, n); 
    } 
    else { 
     RARRAY_PTR_USE(ary, ptr, { 
      MEMMOVE(ptr, ptr + n, VALUE, RARRAY_LEN(ary)-n); 
     }); /* WB: no new reference */ 
    } 
    ARY_INCREASE_LEN(ary, -n); 

    return result; 
}