ruby - Ruby中+=数组的复杂度顺序是什么？

Question

假设我有一个长度为 n 的数组 a，我希望添加另一个长度为 m 的数组 b。即

a+=b

这种操作的复杂性顺序是什么？我知道在 PERL 中，它有一个缓冲区，所以如果 m 不大，它就是 ~ o(m)。让我们采取两种情况：
1. m << n
2. m ~ n
谢谢。

Answer 1

可能我不会给你完整的答案，但对于初学者来说，请检查Array#+C 中的实现：

VALUE rb_ary_plus(VALUE x, VALUE y)
{
    VALUE z;
    long len;

    y = to_ary(y);
    len = RARRAY_LEN(x) + RARRAY_LEN(y);
    z = rb_ary_new2(len);
    MEMCPY(RARRAY_PTR(z), RARRAY_PTR(x), VALUE, RARRAY_LEN(x));
    MEMCPY(RARRAY_PTR(z) + RARRAY_LEN(x), RARRAY_PTR(y), VALUE, RARRAY_LEN(y));
    ARY_SET_LEN(z, len);
    return z;
}

如您所见，它定义了新实例，复制数组 X，然后复制数组 Y。 MEMCPY是一个宏，应该wrap memcpy()。正如这个答案所暗示的那样，Cmemcpy是 O(N) - realloc 和 memcpy 如何工作？

所以在我们的例子中，它将是~O(N+M)。我建议您进一步检查 Ruby 源代码。很有可能+=它只执行 single memcpy。我们也有不同的 Ruby 实现。