Google gadget
Linux版が出たので、試してみた。最初は、リンクの段階でR_X86_64_32の指定はダメだから、-fPICを指定してね。と言われて失敗。調べてみたところ、どうやらzlibのコンパイルが良くなかった模様。Google gadgetをコンパイルするには、zlibが必要で、ここからソースをダウンロードしてコンパイルすればいいんだけど、普通にconfigure makeすると、後でGoogle gadgetのリンクの際に、zlib.aのリンクに失敗する(多分64bit版のみの問題)。zlibのコンパイルには、configureしてから、make CFLAGS=fPICを指定し、最後にmake installでインストールしておく。
あとは、Ubuntu forumに書いてあった方法でできた。
ただマルチディスプレイ環境だと、左側のディスプレイにしかサイドバーを配置できないみたい(サイドバーからアンドックすればガジェット自体は、動かせる)。「自動的に隠す」が無いと、ちょっと使う気にはならないかな。
Boyer Moore
久し振りにBoyer Moore Searchなぞ、実装してみた。まずは、通常の逐次検索。
public class NormalSearch {
public static int indexof(String from, String str) {
int len = from.length() - str.length();
for (int i = 0; i <= len; ++i) {
int j;
for (j = 0; j < str.length(); ++j) {
if (from.charAt(i + j) != str.charAt(j)) break;
}
if (j == str.length()) return i;
}
return -1;
}
}
Boyer Moore Searchの場合、高速化のために、探索文字列のテーブルを作るのが一般的だけど、この生成コストがバカにならないので、同じ文字列を検索する場合には、同じテーブルを使い回せるようにしてみる。Unicodeだと、このテーブルに256k Byte必要になってしまうのがつらいけど、Mapとか使うと、遅くなりそうなんで、今回は無視。
public class BMSearch {
final String searchStr;
final Table table;
public BMSearch(String searchStr) {
if (searchStr == null) throw new NullPointerException();
this.searchStr = searchStr;
table = new Table(searchStr);
}
static class Table {
int[] tbl = new int[Character.MAX_VALUE + 1];
Table(String str) {
Arrays.fill(tbl, -1);
for (int i = 0; i < str.length(); ++i) {
tbl[str.charAt(i)] = i;
}
}
int lastIndexOf(char c) {
return tbl[c];
}
}
public int indexof(String str) {
int strLen = str.length();
int str2Len = searchStr.length();
for (int i = 0; i <= strLen - str2Len; ++i) {
int j;
for (j = str2Len - 1; j >= 0; --j) {
if (str.charAt(i + j) != searchStr.charAt(j)) break;
}
if (j == -1) return i;
int idx = table.lastIndexOf(str.charAt(i + str2Len - 1));
if (idx == -1) i += str2Len - 1;
else {
int offset = str2Len - idx - 2;
if (offset > 0) i += offset;
}
}
return -1;
}
}
さて、速度を計ってみる。
Core 2 Duo E8400(3.7GHz overclocked) Ubuntu 8.04 64bit版 IBM JDK: java full version "JRE 1.6.0 IBM Linux build pxa6460sr1-20080416_01 (SR1) "
まずは、こんなテストを用意
long start = System.currentTimeMillis();
String from = "The quick fox jumps over the lazy dog";
String str = "jumps";
final int N = 1000000;
for (int i = 0; i < N; ++i) {
NormalSearch.indexof(from, str);
}
System.out.printf("Normal search(short): %,dms%n", System.currentTimeMillis() - start);
start = System.currentTimeMillis();
BMSearch bm = new BMSearch(str);
for (int i = 0; i < N; ++i) {
bm.indexof(from);
}
System.out.printf("BM search(short): %,dms%n", System.currentTimeMillis() - start);
Normal search(short): 198ms BM search(short): 439ms Normal search(short): 183ms BM search(short): 434ms Normal search(short): 191ms BM search(short): 414ms
あれ？ 正直、目を疑った。確かにBoyer Moore法は、テーブルの生成にコストがかかるんで、注意して適用しないと逆効果になることがある。でも、今回のテストはテーブル生成をループの外に出してある。なのに、単純な逐次探索の方が2倍くらい速いのだ。くやしいので、もっと極端な例にしてみる。
long start = System.currentTimeMillis();
String from = "The quick fox jumps over the lazy dog";
String str = "ABCDEFG";
final int L = 100000;
StringBuilder buf = new StringBuilder(from.length() * L + str.length());
for (int i = 0; i < L; ++i) buf.append(from);
buf.append(str);
from = buf.toString();
final int N = 10;
for (int i = 0; i < N; ++i) {
NormalSearch.indexof(from, str);
}
System.out.printf("Normal search(long): %,dms%n", System.currentTimeMillis() - start);
start = System.currentTimeMillis();
BMSearch bm = new BMSearch(str);
for (int i = 0; i < N; ++i) {
bm.indexof(from);
}
System.out.printf("BM search(long): %,dms%n", System.currentTimeMillis() - start);
Normal search(long): 156ms BM search(long): 33ms Normal search(long): 156ms BM search(long): 32ms Normal search(long): 152ms BM search(long): 31ms
さすがに、ここまで来ると5倍くらいになっている。検索対象が7文字だから、まぁ、だいたいは目論見通りか。念のためSunのJavaで、最初のやつを追試。
Normal search(short): 70ms BM search(short): 43ms Normal search(short): 72ms BM search(short): 50ms Normal search(short): 72ms BM search(short): 47ms
う、Sunさん、速いっすね。これだと2倍程度とはいえ、Boyer Mooreの方が速いな。じゃあ、後者のテストの方はというと、
Normal search(long): 163ms BM search(long): 38ms Normal search(long): 186ms BM search(long): 37ms Normal search(long): 169ms BM search(long): 37ms
IBM版との差は無くなった。実行時コンパイルの特性の違いなのかな。
テーブル作成コストとか、検索文字列の長さとか、本当にBoyer Mooreの方が速くなるのかどうかは、慎重な判断が必要になりそうだ。
