ruby - 运行时间 Array#unshift 与 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 Ruby 2.1.2 中，unshift重新分配数组并完全复制它:

              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;
}