Listの要素を削除する最善の方法

java

卒論の発表原稿を書いている途中に突然ですがJavaにおいてListの要素を削除するベストな方法を検証してみたくなったためやってみました。
決して現実逃避ではありません。

ちなみにJavaのバージョンは1.6.0_23です。


ここではとりあえずArrayListを例にあげてみましょう
ArrayListの要素を削除する方法としては

  • forループで該当する値を削除する
  • list.remove(Object o)メソッドを使う
  • Iteratorを使う

が挙げられます。
※ここではあくまで削除する方法を列挙しているだけです。

とりあえず今回は

ArrayList<Integer> list = new ArrayList<Integer>();
list.add(0);
list.add(1);
list.add(1);
list.add(2);
list.add(1);
list.add(2);

という状況でlistの要素の値が2の場合、その要素を削除します。

  • forループで削除
for(int i=0;i<list.size();i++){
    if(list.get(i).equals((Integer)2)) list.remove(i);
}

この書き方8年前にみたわー8年前に。
拡張for文使って要素を削除しようとしてもエラーがでるので問題外。
とりあえずこの書き方は保留。

  • list.remove(Object o)メソッドを使う
while(list.remove((Integer)2)){}

完結すぎてやばい。list.remove()でtrueが返ってくる間ずっと消し続ける。
ワンライナー

Iterator itr = list.iterator();
while(itr.hasNext()){
    Integer i = (Integer)itr.next();
    if(i.equals((Integer)2)) itr.remove();
}

多分こう書くのがスタンダードなのかな？
＞Iteratorインタフェースは処理中に要素を安全に削除する仕組みを持っています
ってどこかに書いてあったし安心して使えるよね多分。


処理速度を比べてみよう。
上記の環境だと速度差がほとんどでないのでlistの要素を100個に増やして同じ処理を10000回ループさせました。

  • forループで該当する値を削除する
1  140ms
2  266ms
3  93ms
4  78ms
5  250ms
6  93ms
7  94ms
8  171ms
9  93ms
10 250ms

平均値 152.8ms

  • list.remove(Object o)メソッドを使う
1  93ms
2  281ms
3  124ms
4  141ms
5  109ms
6  109ms
7  93ms
8  109ms
9  109ms
10 125ms

平均値 129.3ms

1  374ms
2  172ms
3  156ms
4  343ms
5  328ms
6  312ms
7  156ms
8  296ms
9  172ms
10 172ms

平均値 248.1ms

結果は 129.3mss > 152.8 > 248.1ms ということで
while(list.remove(Object o))
のワンライナースマートプレイが優勝しました!!!

しかしIteratorはLinkedListになると爆速になるという情報を手に入れたのでどうせなら同じ環境でLinkedListにしてその実力を図ろう!!!
ということでLinkedListでも同じ環境で測定してみました。

  • forループで該当する値を削除する
1  107
2  109
3  175
4  107
5  105
6  117
7  100
8  102
9  186
10 100

平均値 120.8ms

  • list.remove(Object o)メソッドを使う
1  108
2  102
3  103
4  97
5  97
6  97
7  100
8  95
9  104
10 105

平均値 100.8ms

1  157
2  172
3  166
4  162
5  156
6  159
7  159
8  107
9  158
10 134

平均値 153.0ms

ということでLinkedListでも 100.8ms > 120.8ms > 153.0ms という同じ結果になりました。

やはり攻守最強はwhile(list.remove((Integer)2)){}か！？

それどこ情報ー？どこ情報よー？


…真面目に考えてみると、実験前はIteratorを使ったほうが速そうというイメージだったのですが、結果が違ったのでJavaのソースコードを読んでみた。
ArrayListの場合

list.remove(Object o)は
listをfor文で回し、前方からチェックしてoと同じObjectがあった場合にoの前後のlistをSystem.arraycopyでくっつけるとう処理をしています。
つまり一回list.remove((Integer)2)で2を格納した要素をremoveすると、また先頭からfor文で2を格納した要素を探しに行きます。

対してIteratorを使った場合は
Iterator.remove()をすると、最終的にArrayListのlist.remove(int index)が実行され、index値の前後のlistをSystem.arraycopyでくっつけています。
つまり前方から探していき、2を格納した要素を発見、removeしてもその続きから処理していきます。

ということで、この処理を比較してみた限りなぜ上記のような結果になったかというのを考えると…
listのサイズが小さすぎるため、list.remove(Object o)の方がIteratorを使うよりコストが低かった!!!
そのため早く処理されてしまったということですね。
なので、リストのサイズがすごい大きくなると普通にIterator使ったほうが早く削除できると思います。

まぁサイズが100とかならlist.remove(Object o)使ってワンライナーで削除したほうが簡単だし低コストなのでいいのかも。
とか言っても多分普通プログラム書いてるとそこまで考えて実装するの難しいから、大変なことになる前にIterator使うのがいいんじゃないかな〜。
ってことでした。

実際に要素数を5000にしてforループを1000回としてみたところ

  • list.remove(Object o)
1 7749ms
2 7757ms
3 7730ms
4 7785ms
5 7738ms

平均値 7751.8ms

1 4392ms
2 4310ms
3 4285ms
4 4288ms
5 4418ms

平均値 4338.6ms
おお、本当にIteratorの方が早くなってる!!!



ちなみにLinkedListの場合
list.remove(Object o)とIteratorのitr.remove()は同じ処理をしてる
Iterator.remove()は内部でlist.remove(index)を行っており、list.remove()は

public E remove(int index){
    return remove(entry(index));
}

となっており、list.remove(Object p)を呼び出しているため同じ。
ということでLinkedListの場合はIteratorのコストを考えると

while(list.remove(Object o)){}

としたほうがいいの

…かと思ったら、LinkedListのIteratorはAbstractSequentialListから継承されており、処理としては同じだが内部で最適化されている模様。
LinkedListのremove(Object o)メソッドは

for (Entry<E> e = header.next; e != header; e = e.next) {
    if (o.equals(e.element)) {
        remove(e);
        return true;
    }
}

だいたいこんな感じになっており、一見すると同じ処理をしているように思いますが
LinkedListはIteratorを使ってitr.remove()をするとArrayListのlist.remove(Object o)と違い、先頭一致ではなくheaderの場所（Iteratorの現在地）からループ処理をするため、要素が多いほど相対的には高速な処理になります。
そして、whileループでremove(Object o)とした場合は、ArrayListと同じくheaderが先頭一致で処理していくので時間がかかってしまう。

ということでこちらも要素数を5000にしてforループを1000回としてみたところ

  • list.remove(Object o)
1 11432ms
2 10916ms
3 10991ms
4 10911ms
5 10908ms

平均値 11031.6ms

1 1906ms
2 1477ms
3 1478ms
4 1477ms
5 1533ms

平均値 1574.2ms

我が軍は圧倒的じゃないか…!!
つまり、要素を削除するときはArrayListとLinkedList、どちらもIteratorを使うべきという結論になりました。


間違ってたりしたら指摘してくれると嬉しいです。
参考
JavaはIteratorを使うべき理由
Iteratorより基本forループでArrayListのget()を使ったほうがいいなんて話はもはや百害あって一利なしです。