运行时间：Array#unshift 与 Array#shift

Question

运行时间：Array#unshift 与 Array#shift

7

我原以为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)

- migu

如果增加操作次数会发生什么？ - Ajedi32

#shift@12.8m: 0.016307，#shift@25.6m: 0.059878，#shift@64m: 0.098583，#shift@128m: 0.344900。#unshift@12.8m: 0.059736，#unshift@25.6m: 0.126382，#unshift@64m: 0.285351，#unshift@128m: 0.993967。仅通过比较这些比率，似乎#shift的运行时间为Θ(3.4n)，而#unshift略微呈指数增长。 - migu

1

你是否研究过Ruby源代码，以了解数组是如何实现以及shift/unshift的工作原理？幕后可能发生各种事情，这会影响你的结果。向数组开头添加一个元素并不一定为数组分配单个新条目，它可能会分配多个条目，或者只是移动指向数组起始位置的指针；同样，shift一个元素可能只是更新指针以指向新的索引0地址。 - mu is too short

我看过了，但是它是用C语言编写的，由于我没有任何C编程经验，所以我很难理解它。 - migu

1

你的问题没有提及你使用哪个 Ruby 版本，所以有点无用。 - phoet

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- undur_gongor · Accepted Answer

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