求む！ArrayList<int>

Javaでも、バージョンが5になった時からジェネリクスに対応し、
ArrayList<String>
の様に、コンテナクラスに格納するデータの型を限定できるようなりました。

しかし、プリミティブ型は指定できません。その場合は、ラッパクラスを指定します。
ArrayList<int> …… NG
ArrayList<Integer> …… OK

とは言え、同じく Java5 から採用されたオートボクシング機能によって、この違いを気にすることなく使うことが出来ます。

ArrayList<Integer> ary = new ArrayList<Integer>;

int n = 10;
ary.add(n);

int m = ary.get(0);

---

オートボクシングのお蔭で、コードを書く時には気にしなくても良くても、実際にコンテナに格納されているのはInteger型のオブジェクトなわけですから、

ArrayList<Integer> ary = new ArrayList<Integer>;

int n = 10;
ary.add(new Integer(n));

Integer m0 = ary.get(0);
int m = m0.intValue();

と、となっているはずです。（実際は、少し違う）

ArrayList<Integer> ary = new ArrayList<Integer>;
for (int i = 0; i < 10000; i++)
    ary.add(i);

気軽に、こんなコードを書いちゃったりするわけですが、10000個ものIntegerのオブジェクトが作られているとすると、コストが気になるところです（オブジェクトの生成とか、ガーベジコレクションとか）。
（実際は、0に近いところの値を表すIntegerオブジェクトは共有しているのでそれほどでもない）

---

Javaのコードを実行する場合、VMのJITコンパイラが「最適化」を行っているはずなので、ArrayList<Integer>はIntegerオブジェクトを使わないように最適化されているんじゃないかと期待してしまったわけですが…。

そこで、確認してみました。
とはいえ、JITコンパイラが吐いたコードは分からないので、実行時間で比較してみました。

【ArrayList<Integer>の場合】

    final int SIZE = 100000;
    final int LOOP = 1000;

    final ArrayList<Integer> array = new ArrayList<Integer>(SIZE);
    for (int i = 0; i < SIZE; i++)
        array.add(null);

    final long start = System.currentTimeMillis();

    for (int i = 0; i < SIZE; i++)
        array.set(i, i);

    for (int j = 0; j < LOOP; j++) {
        for (int i = 0; i < SIZE; i++) {
            int n = array.get(i);
            n = n * 2;
            array.set(i, n);
        }
    }

    final long end = System.currentTimeMillis();
    System.out.printf("%d\n", end - start);

【ArrayList<Integer>っぽいものをintで作成した場合】

    final int SIZE = 100000;
    final int LOOP = 1000;

    final ArrayListInt array = new ArrayListInt(SIZE);

    final long start = System.currentTimeMillis();

    for (int i = 0; i < SIZE; i++)
        array.set(i, i);

    for (int j = 0; j < LOOP; j++) {
        for (int i = 0; i < SIZE; i++) {
            int n = array.get(i);
            n = n * 2;
            array.set(i, n);
        }
    }

    final long end = System.currentTimeMillis();
    System.out.printf("%d\n", end - start);


class ArrayListInt
{
    int[] elementData;
    int size;
    public ArrayListInt(int s)
    {
        size = s;
        elementData = new int[s];
    }
    public int set(int index, int element)
    {
        RangeCheck(index);
        int oldValue = elementData[index];
        elementData[index] = element;
        return oldValue;
    }
    public int get(int index)
    {
        RangeCheck(index);
        return elementData[index];
    }
    private void RangeCheck(int index)
    {
        if (index >= size)
            throw new IndexOutOfBoundsException(
                "Index: "+index+", Size: "+size);
    }
}

1つ目の実行時間：3687
2つ目の実行時間：1812

約半分の時間で終わると言うことは、ArrayList<Integer>は、Integerオブジェクトを使わないように最適化されないと、そういうことなのですね。
というか、差が大きいのにビックリ。

---

そんなわけで、パフォーマンスのためには、ラッパクラスを使わないバージョンのArrayList<Integer>、ArrayList<Byte>、HashMap<Integer,Object>等を作る必要がありそうです。

でも、きっと誰かが作っているだろうと探したら、やっぱりありました。
Apache Commonsに。
（Mapは無いですが）

---

参考までに。

    final int[] array = new int[SIZE];

    final long start = System.currentTimeMillis();

    for (int i = 0; i < SIZE; i++)
        array[i] = i;

    for (int j = 0; j < LOOP; j++) {
        for (int i = 0; i < SIZE; i++) {
            int n = array[i];
            n = n * 2;
            array[i] = n;
        }
    }

    final long end = System.currentTimeMillis();
    System.out.printf("%d\n", end - start);

実行時間：172

配列サイズが固定なら、普通に配列を使った方が更に10倍くらい速くなるのか。

タグ：Java