insert方法在Ruby Array中的复杂性顺序

Question

当n是数组大小时,在Ruby中插入数组的预期数量级是多少？
谢谢

Answer 1

TL; DR追加(一种特殊形式的插入)项目到数组的末尾通常在O(1)时间内完成.

让我们来看看(MRI)ruby源代码,看看为什么会这样.我们从这行ruby代码开始:

a = [1,2]

Ruby准备一个数组对象,然后在这个C函数中初始化它.检查参数的有效性,然后将新数组的容量设置为估计的长度:

ary_resize_capa(ary, len);

数组的容量是阵列可以在其从操作系统分配的内存块中保存的元素数.数组的长度(数组实际保存的元素数)始终小于或等于容量.通过设置数组的容量,ruby确保分配足够的内存来保存len数组中的项目数.

现在,让我们在数组的末尾添加一个元素:

a << 3

函数的来源<<如下所示:

VALUE
rb_ary_push(VALUE ary, VALUE item)
{
    long idx = RARRAY_LEN(ary);
    VALUE target_ary = ary_ensure_room_for_push(ary, 1);
    RARRAY_PTR_USE(ary, ptr, {
    RB_OBJ_WRITE(target_ary, &ptr[idx], item);
    });
    ARY_SET_LEN(ary, idx + 1);
    return ary;
}

这段代码看起来并不太可怕.它发现idx新元素的index()是数组的长度,确保数组有足够的内存来保存新元素(ary_ensure_room_for_push),将新元素写入数组,并增加数组长度.

当阵列的容量大于其长度时,不需要分配更多的存储器,ary_ensure_room_for_push并且操作可以在O(1)时间内完成.

当数组的容量等于其长度时(数组中的内存量可以精确地保存它所拥有的元素数), ary_ensure_room_for_push需要增加容量,以便另外一个元素.让我们看看这是如何完成的:

static VALUE
ary_ensure_room_for_push(VALUE ary, long add_len)
{
    long old_len = RARRAY_LEN(ary);
    long new_len = old_len + add_len;
    long capa;

    // ...

    rb_ary_modify(ary);
    capa = ARY_CAPA(ary);
    if (new_len > capa) {
        ary_double_capa(ary, new_len);
    }

    return ary;
}

我们看到,ary_ensure_room_for_push如果请求的长度超过当前容量,则数组容量加倍(在引擎盖下ary_double_capa使用ary_resize_capa我们在数组初始化期间看到的方法).此代码从操作系统请求新的(更大的)内存块,并将所有数组元素复制到此新内存中.我们无法确切地说出复制操作具有哪种复杂性(不要过多地考虑操作系统内部),但我们假设它在最坏的情况下是O(n).

当新元素符合数组容量时,这会导致向元素添加元素的时间为O(1),如果超出容量,则为O(n).

仅供参考:将容量加倍(而不是将其精确地增加到所请求的长度)是一种巧妙的技巧,可以优化多次向阵列添加元素的情况.有了这个技巧,我们大部分时间都有O(1)时间进行追加操作.仅对于每个log(n)追加操作,需要增加容量,从而产生O(n)运行时间.