ruby - Rubyの+=配列の複雑さの順序は何ですか?

Question

長さ n の配列 a があり、長さ m の配列 b をもう 1 つ追加したいとします。すなわち

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コピーしますmemcpy()。この回答が示唆するように、Cmemcpyは O(N) です - realloc と memcpy はどのように機能しますか?

したがって、この場合は ~O(N+M) になります。Ruby のソース コードをさらに調べることをお勧めします。+=その場合、 single のみを実行する可能性が非常に高くなりmemcpyます。また、Ruby のさまざまな実装があります。