配列の操作は、大きくパフォーマンスに影響することのひとつです。
最近のプログラミング言語は、関数型インターフェースやstreamインターフェースを標準的に備えていたり、便利なメソッドが用意されているなど、配列への操作が非常に便利になってきました。
しかし、その中で特に問題となるのは、パフォーマンスです。100件、200件の操作であればまったくもって問題にはなりませんが、それが1万件、10万件となってくると、顕著にパフォーマンスが劣化することとなります。
今回は、そんな配列のパフォーマンスチューニングについて考えてみたいと思います。
はじめに
多くのプログラミング言語で標準的に備えているListインターフェースは、配列をラップして使い勝手を向上させているクラスです。
今回の記事では、配列を直接操作するわけではなく、このListインターフェースを通じて操作するコードを主として記述します。
要素の検索
現代の主要なプログラミング言語には、配列のインデックスを返すindexOfをはじめとして、JavaではStreamインターフェースのfilter、find、JavaScriptではinclude、C#ではLinQなど、様々な手段が用意されています。
しかし、これらのメソッドの多くは基本的に線形探索アルゴリズム（リストの先頭から順番に見ていくアルゴリズム）を利用しています。
線形探索は、検索したいデータの位置が先頭に近づけば近づくほど計算コストが下がりますが、末尾に近づけば近づくほど計算コストが上がります。1万件のリストを順次探索すると、検索したいデータの位置が完全にランダムとした場合、平均5000回の計算が走ります。
1人のユーザーが利用するだけなら一瞬で検索を完了できますが、同時に多数のユーザーが検索を利用する場合、とてつもない負荷になるのは言うまでもありません。
解決方法
本例の解決方法としては、「HashMap」や「Dictionary」などの連想配列系クラスを活用し、索引を作成することが有力な手段となります。
HashMap、Dictionaryを利用する
結局のところ、ListやArrayListでは何をやっても線形探索アルゴリズムを利用している以上、それを超えるパフォーマンスは出ません。独自に二分探索（バイナリサーチ）などを実装しても構わないのですが、ソートが必須であるなど、いくつかの理由で汎用的とは言えません。
そこで、HashMapやDictionaryなどのクラスを使うことで高速化を図ることができます。JavaのMapを使った例を挙げてみます。
Main.java
import java.util.*;
import java.util.stream.*;
import java.util.function.*;
public class Main {
public static void main(String[] args) throws Exception {
// create test data.
List<User> list = new ArrayList<>();
for(int i = 0; i < 10000; i++){
list.add(new User(i, "user-" + i));
}
listPerf(list);
hashMapPerf(list);
}
// Listをそのまま検索する
private static void listPerf(List<User> list){
long startTime = System.currentTimeMillis();
// User.idを1から順番に検索する
for(int i = 0; i < 10000; i++){
final int targetId = i;
for(User user : list){
// idがtargetIdと等価なら検索を打ち切る
if(user.id == targetId){
break;
}
}
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("List:" + totalTime);
}
// Mapに変換してから検索する
private static void hashMapPerf(List<User> list){
long startTime = System.currentTimeMillis();
// Mapに変換する
Map<Integer, User> hashMap = list.stream().collect(Collectors.toMap(User::getId, Function.identity()));
// User.idを1から順番に検索する
for(int i = 0; i < 10000; i++){
final int targetId = i;
hashMap.get(targetId);
}
long endTime = System.currentTimeMillis();
long totalTime = endTime - startTime;
System.out.println("Map:" + totalTime);
}
}
User.java
public class User{
public int id;
public String name;
User(int id, String name){
this.id = id;
this.name = name;
}
int getId(){
return id;
}
}
結果
List:217
Map:43
本例では、単なるDTOに対して検索を1万回実行してみました。Listをそのまま検索するのに比べ、Mapに一旦格納すると約5倍のパフォーマンスが出ていることがお分かり頂けると思います。
List⇒Mapへの変換コストを考慮しても、かなりのパフォーマンス改善に繋がることでしょう。
HashTableという有名なアルゴリズムに基づいて実装されているHashMapですが、目的の配列の添字を「キーをハッシュ化した値」とすることで、検索時の計算量が常に「キーをハッシュ化するコスト」だけで済むわけです。
ただし、本例は1つの資源に対し大量の検索を繰り返しているということに注意してください。1つの資源に対し数回程度しか検索を行わない場合は、Mapに変換するコストが線形探索コストを上回るため、むしろパフォーマンスが落ちてしまいます。
先ほどのコードの繰り返し部分を「100」に変更し、更に線形探索（Listの検索）に不利な降順（10000,9999,9998…）で検索した結果がこちらです。
List:24
Map:30
Listから100回検索する最悪コストを、Mapを生成するコストが上回っていることが分かります。
以上のことから、この解決方法は、Mapに変換されたデータを一定期間キャッシュしておき、それに対して何万ものユーザーがアクセスするような場合に有効です。Mapの生成にかかるコストは掛かりますが、それ以降は爆速のパフォーマンスを発揮するチューニングとなります。
工夫次第で前方一致検索も可能
少しメモリを食ってしまいますが、Mapをネストすることで前方一致検索をも実現可能です。実装例は省略しますが、Mapのキーを1文字のStringまたはCharで持つようにし、それを繰り返し格納していけばよいのです。
それでは、JavaScriptで簡単な検索プログラムを書いてみましょう。
var dictionary = {
"a": {
"b": {
"s": {
"t": {
"r": {
"a": {
"c": {
"t": "abstract: 抽象的な"
}
}
}
}
}
},
"p": {
"p": {
"l": {
"e": "apple: りんご",
"i": {
"c": {
"a": {
"t": {
"i": {
"o": {
"n": "application: 適用"
}
}
},
"n": {
"t": "applicant: 申し込み"
}
}
}
}
}
}
}
}
};
function search(str){
var top = dictionary;
// 渡された文字列の先頭から順に連想配列をたどっていく
str.split("").forEach(c => top = top[c]);
console.log(dig(top));
}
// 最下層を取得するメソッド
function dig(obj, arr){
arr = arr || [];
if(typeof obj !== "object"){
arr.push(obj);
return;
}
for(var i in obj){
dig(obj[i], arr);
}
return arr;
}
試してみましょう。
search("app"); // -> [ 'apple: りんご', 'application: 適用', 'applicant: 申し込み' ]
search("appli"); // -> [ 'application: 適用', 'applicant: 申し込み' ]
search("applicat"); // -> [ 'application: 適用' ]
search("ab"); // -> [ 'abstract: 抽象的な' ]
このように、前方一致探索が可能となりました。
もちろん、パフォーマンスを気にしないならfilterメソッドなどが使えます。正規表現も用いてあげれば、はるかに柔軟な検索ができます。しかし、例えば英単語辞書の検索システムを作ろうとしたとき、100万語を超えるとされる英単語を毎回filterしていては、遅すぎて使い物になりません。
そもそも、そんなシステムはRDBMSやNoSQLなどのデータベースを使用すべきであって、自前でこのようなロジックを作成するようなことは避けなければなりませんが、このような手法を知っておくことで、役に立つ日が来ることもあるかもしれません。
まとめ
パフォーマンスチューニングは、計算量を頭の中で描くことが必要不可欠です。
Listなどの便利なクラスは、内部実装を何も知らなくても使用できます。しかし、あえてソースコードを読むなどして内部の動作を知ることで、ボトルネックの所在や潜在的なバグの存在をいち早く突き止めることができます。もし内部実装を知らなくても、計算コストを意識してコードを精査することで、パフォーマンス向上への糸口を掴むことが出来ます。
また、いろいろな手段を自分の引き出しに持っておくことで、試行錯誤を繰り返しつつ、適切なチューニングを行うことができるようになるかと思います。
他の有名なアルゴリズムなども、是非調べてみてください。