レビューで鍛えるJavaコーディング力その６（コレクション）

今回はコレクションを用いたキャッシュに関する問題です。

問題

以下のコードの問題を指摘し、修正してください。
ただし、問題は複数あることもあれば、全くないこともあります。

import java.util.List;

public class IdService {
	/** IDキャッシュ */
	private List<Integer> cache;

	/** リモートシステムへのアクセッサ */
	private RemoteAccessor accessor;

	public IdService() {
		// accessorの初期化は割愛。
		reloadCache();
	}

	/**
	 * IDが存在するかどうかを判定します。
	 * @param id ID
	 * @return IDが存在する場合はtrue、そうでない場合はfalseを返します。
	 */
	public boolean exists(Integer id) {
		return cache.contains(id);
	}

	/**
	 * キャッシュの更新を行います。
	 */
	public void reloadCache() {
		cache = accessor.getIdList();
	}
}

リモートシステムへのアクセス（RemoteAccessorの利用）をできるだけ避けるため、
取得した情報をキャッシュすることが、この処理の目的です。

現実的には、ちょっと仕様（要件）がおかしい感じもしますが、
問題を簡単にするために、敢えてこんな内容にしています。
あくまで目的を達成することを、今回の主眼としてください。

コラム

前回の問題について、id:backpaper0さんからはてブでコメントを頂きました。

getTemplateLines は配列のコピーを返さなくて良いのかな？（変更される恐れがあるので）

これはおっしゃる通りですね。

public String[] getTemplateLines() {
	return this.templateLines;
}

の箇所を、以下のように修正すべきです。

public String[] getTemplateLines() {
	String[] copy = new String[templateLines.length];
	System.arraycopy(templateLines, 0, copy, 0, templateLines.length);
	return copy;
}

あるいは、性能を気にしないなら（あまりオススメできませんが、読みやすくするために）

public String[] getTemplateLines() {
	return StringUtils.splitByWholeSeparatorPreserveAllTokens(this.template, "\r\n");
}

としても良いでしょうか。

問題が不完全な事もちょくちょくありますので
ぜひコメントやトラックバック、ブクマコメント、スターなどで突っ込んでください m(_ _)m

解答

今回の問題点は、ここです。

public boolean exists(Integer id) {
	return cache.contains(id);
}

ArrayListのcontainsメソッドは、ただの線形検索です。
要素数が10や100程度なら1ms以内に終わるでしょうけど、
10000程度にもなってくると、無視出来ない処理時間になってきます。

そもそも「検索（存在判定）」が目的なのですから、ArrayListは不向きです。
ここではSet、実装としてはHashSetなどを使えば良いでしょう。

private Set<Integer> cache;

public void reloadCache() {
	cache = new HashSet<Integer>(accessor.getIdList());
}

また、Collections#binarySerachによる二分探索を使う事も可能です。
その場合、リストのソートをしておくことが前提となるため、以下のような修正になります。

public boolean exists(Integer id) {
	int result = Collections.binarySearch(cache, id);
	return result > -1;
}

public void reloadCache() {
	List<Integer> list = accessor.getIdList();
	Collections.sort(list);
	cache = list;
}

ちなみに私のCore2Duoマシンでは、以下のような処理時間の差が出ました。

10,000要素の線形検索を10,000回繰り返した場合（＝全要素を1回ずつ検索した場合）
　・HashSet : 0ms
　・ArrayList : 485ms
　・ArrayList(binarySearch) : 16ms

100,000要素の線形検索を100,000回繰り返した場合（＝全要素を1回ずつ検索した場合）
　・HashSet : 15ms
　・ArrayList : 47,781ms
　・ArrayList(binarySearch) : 47ms

基本的に「List#containsは不吉な匂い」と考えて、差し支えないでしょう。

補足

今回の内容について、スレッドセーフ性について疑問を持った人もいるかも知れません。
そのような方は、恐らく以下の2つについて考えたのではないでしょうか。

　1. Listのgetとaddが同時に行われて、問題が発生しないか？
　2. reloadCacheが連続して呼び出されたら、問題が発生しないか？

観点としては大切なのですが、
今回は、いずれの問題も起きることはありません。

処理順序を追って行くと分かるのですが、
cache変数はreloadCacheメソッドの中で、インスタンスを置き換えているため
（また、そのインスタンスに対する処理は、reloadCache内では行わないため）
複数のスレッドからcacheに対して「get」を行うことはあっても、
同時に「get」と「add」することはないので、問題は発生しないのです。

逆に言えば、reloadCacheメソッドの中で、
cacheに対してインスタンスの置き換え以外の処理を行なってしまえば、
問題が起きる可能性があります。

たとえば、解答の中でソートを行う処理がありましたが、

public void reloadCache() {
	List<Integer> list = accessor.getIdList();
	Collections.sort(list);
	cache = list;
}

もしこれを、以下のようにしてしまうと、問題が発生してしまいます。

public void reloadCache() {
	cache = accessor.getIdList();
	Collections.sort(cache);
}

ソートが終わる前に、cacheに対してbinarySearchされてしまえば、きちんと検索ができませんし
ソート中にインスタンスが入れ替わってしまうと、ソート結果がどうなるか分かりません。

このように、キャッシュの更新などを行う場合には、
最後にまとめてインスタンスを置き換えることで
synchronizedせずにスレッドセーフ化することもできるのです。

若干、ソースからでは伝わりにくい、、、かも知れませんけどね。

まとめ

List#containsは不吉な匂い
キャッシュを自前で実装するなら、スレッドセーフになっているかどうかは要確認
インスタンスを置き換えることで、スレッドセーフ化するという手段もアリ

というかそもそも、きちんとしたキャッシュ機構を作りたいなら
ローカルにDB（あるいはインメモリDB）を置くか、
サードパーティ製のキャッシュライブラリの利用を検討すべきなんでしょうけどね。

と言いつつ、実は私もキャッシュのライブラリについては詳しくないので、
「これが鉄板でしょう」というものがあれば、ぜひ教えてください m(_ _)m

谷本心 in せろ部屋

はてなダイアリーから引っ越してきました

レビューで鍛えるJavaコーディング力その６（コレクション）

問題

コラム

解答

補足

まとめ