java.util.AbstarctCollectionを継承した抽象リスト表現のクラス。add、remove、indexOfやclearはそのまんまの実装やサブクラス責務になってるんですが、面白い個所がいくつかありました。
フェイルファスト動作
AbstractListにこんな場所があります。
/*簡便化のため、元ソースとはコードの位置を変えています。*/
int expectedModCount = modCount;
protected transient int modCount = 0;private class Itr implements Iterator {
public Object next() {
checkForComodification();
...
expectedModCount = modCount;
...
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
ConcurrentModificationExceptionがカギ･･･とはいえ読んだままの例外で「オブジェクトの同時変更を検出したメソッドによって、そのような変更が許可されていない場合にスローされます」とのこと。
Iteratorにはremoveやaddなど元のリストを変更できるメソッドがあり、マルチスレッドで元リストとIteratorに変更を加えると不整合な状態になる可能性があります。
同時変更の検出はcheckForComodification()が主体です。modCountはフェイルファスト動作が必要なサブクラス*1が、addやremoveのリストの内容が変更されたときに値を更新していきます。
サブリストとフェイルファスト動作
AbstractListにはサブリストを返すメソッドがあります。中身は、AbstractListと同じファイルに収められていて、実装自体はIteratorと同じように元リストのビューを返しています。
ここには、ちょっと面白い点がありました。
class SubList extends AbstractList {
private AbstractList l;//参照元のリスト
private int expectedModCount; public void add(int index, Object element) {
checkForComodification();
l.add(index+offset, element);
expectedModCount = l.modCount;
modCount++;
}
}
addやremoveなどでサブリスト自体の修正回数をカウント(modCount++)しています。参照元のリストが修正回数をカウントしてるので、サブリスト自体はカウントする必要ないんじゃ･･･と思いました。が、しかし･･･
public List subList(int fromIndex, int toIndex) {
return new SubList(this, fromIndex, toIndex);
}
サブリストのサブリストを返すことができるので、サブリスト自体も修正回数を保持する必要があるのでした。
java.util.RandomAccess
サブリストを返すメソッドはこんな風になっています。
public List subList(int fromIndex, int toIndex) {
return (this instanceof RandomAccess ?
new RandomAccessSubList(this, fromIndex, toIndex) :
new SubList(this, fromIndex, toIndex));}
RandomAccessはマーカーインタフェースで中身は空です。詳細はjavadocに譲るとして、ちょっと気になる記述があります。
このインタフェースをつけたクラスは「（中略）動作を変更して、優れたパフォーマンスを実現することです」とある。また、この場合Iteratorよりもget(int)でのシーケンシャルアクセスのほうが早いのだという。
というわけで実験。
long start = 0;
long end =0;
List hogeList = new ArrayList();
/*100万のIntegerインスタンス生成*/
for (int i = 0; i<1000000;i ++) {
hogeList.add(new Integer(i));
}
start = System.currentTimeMillis();
for (Iterator i=hogeList.iterator(); i.hasNext(); ) {
i.next();
}
end = System.currentTimeMillis();
System.out.println("Iterator:" + (end - start));start = System.currentTimeMillis();
for (int i=0, n=hogeList.size(); i < n; i++) {
hogeList.get(i);
}
end = System.currentTimeMillis();
System.out.println("for :"+(end - start));
| 経過ミリ秒 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| Iterator | 3594 | 3532 | 79 | 78 | 250 | 109 | 93 |
| for | 2094 | 2157 | 31 | 46 | 141 | 32 | 32 |
コンパイル直後の1-2発目は妙に遅かったり、数字がバラついたりしてるけど環境依存の問題なのであまりそれは気にしなくてもよいかと。
確かにArrayList自体のAPI使った方が数倍早い。しかし、色々最適化利き始めたあとは遅いといっても0.1秒〜の世界。しかも100万オブジェクトでの結果なので、通常は問題にならないと思う。Iterator使った方が何かと便が良いし、パフォーマンス上げるといってもこんな細かいとこ吊るし上げるより先に見る場所いくらでもあるしね･･･。
問題になりそうなのは数値科学計算とか大量データの分析とかだろうけど、さすがにその辺で速度欲しい場合はJava以外の言語やシステム使うだろうしね。
