x10のArrayListの要素挿入・削除のコスト #x10

概要

x10で可変長の配列を扱うためのクラスとして ArrayList というクラスがある。
要素の挿入や削除のコストが気になるので、どのように実装されているか調査した。
結論としてはC++のvectorと同じように配列で実装されており、先頭や中間の要素の挿入・削除のコストはO(N)。

参考文献

コードリーディング

ArrayListのコードを読んでいく。
まず冒頭でaという値としてGrowableRailを保持していることがわかる。これが配列のデータの実体。

ArrayList.x10

public class ArrayList[T] extends AbstractCollection[T] implements List[T] {
    private val a: GrowableRail[T];
    ...

GrowableRailの方も見ていくと

GrowableRail.x10

public final class GrowableRail[T] implements CustomSerialization {
    private var data:Rail[T];
    ...

というように Rail[T] の変数を保持していて、ここにデータ保持されている。
GrowableRailクラスには、要素数が変わるたびに必要に応じて data変数を別のサイズのRailに移していく。
（C++のSTLのvectorみたいなもの。）

dataのリサイズ処理は grow, shrink というメソッドで実装されていた。該当部分を引用すると

GrowableRail.x10

    public def grow(var newCapacity:Long):void {
        assert (newCapacity >= capacity());
        var oldCapacity:Long = capacity();
        if (newCapacity < oldCapacity*2) {
            newCapacity = oldCapacity*2;
        } 
       ...

と実装されており、２倍ずつcapacityを増やしていく実装となっている。shrinkもほぼ同様。

つまり、ArrayListに対してaddやremoveLastを呼ぶと、典型的にはO(1)、最悪ケースでO(N)の時間がかかる。

当然ながら、内部でRail（配列）を利用しているので要素の先頭への挿入や削除にはO(N)かかる。
要素の挿入・削除は以下のように実装されていた。

ArrayList.x10

    public def addBefore(i: Long, v: T): void {
        a.add(v);
        for (var j:Long = a.size()-1; j > i; j--) {
            a(j) = a(j-1);
        }
        a(i) = v;
    }

    public def removeAt(i: Long): T {
        val v = a(i);
        for (var j: Long = i+1; j < a.size(); j++) {
            a(j-1) = a(j);
        }
        a.removeLast();
        return v;
    }

QueueやListの実装は標準ライブラリにはないのだろうか？

x10のArrayListの要素挿入・削除のコスト

概要

参考文献

コードリーディング

コメント