コグノスケ

線形探索と2分探索の話

Twitterで線形探索と2分探索の性能逆転ポイントはどこか？という話をしていて、気になったので測ってみました。

線形探索と2分探索は、要素数をNとしたとき、処理量オーダーでいうとO(N) とO(logN) となり、圧倒的に2分探索が速いです。ただし処理量オーダーによる比較は、Nが十分に大きい場合に成り立ちます。Nが極端に小さい場合は線形探索が2分探索と同等、もしくは、勝ってしまう領域があるのではないか？という話です。

結論だけ先に言えば2分探索の圧勝でした。かなりNを小さく（100程度）しないと、線形探索に勝ち目はなかったです。個人的にはN=1000〜2000程度ならば線形探索が勝つ予想をしていましたが、全くそんなことはなかったです。2分探索スゴい。

探索速度検証

検証方法ですが、線形探索（lsearch）を実装して、Cライブラリ（GNU libc 2.29）に実装されている2分探索（bsearch）と速度を比較しました。線形探索lsearchのAPIは2分探索と揃えています。

処理の概要は下記の通りです。探索の対象は同じものを使っています。

• 要素数Nの配列を作る
• 配列を乱数で埋める
• 配列をソートする（bsearchはソート済みの配列にしか使えない）
• 2分探索（bsearch）をM回実行する、時間を測る
• 線形探索（lsearch）をM回実行する、時間を測る

ソースコードは下記のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

int comp(const void *key, const void *val)
{
	int k = *(int *)key;
	int v = *(int *)val;

	return k - v;
}

void *lsearch(const void *key, const void *base,
	      size_t nmemb, size_t size,
	      int (*compar)(const void *, const void *))
{
	void *v = (void *)base;
	size_t i;

	for (i = 0; i < nmemb; i++) {
		if (compar(key, v) == 0)
			return v;
		v += size;
	}

	return NULL;
}

int main(int argc, char *argv[])
{
	int *array, *keys;
	int **fb, **fl;
	size_t n, kn, i;
	struct timeval start_b, end_b, ela_b;
	struct timeval start_l, end_l, ela_l;

	if (argc < 3) {
		fprintf(stderr, "usage:\n\t%s n loop\n", argv[0]);
		return -1;
	}

	n = atoi(argv[1]);
	kn = atoi(argv[2]);
	if (n == 0 || kn == 0) {
		fprintf(stderr, "usage:\n\t%s n loop\n", argv[0]);
		return -1;
	}

	srand(time(NULL));

	array = (int *)malloc(n * sizeof(int));
	keys = (int *)malloc(kn * sizeof(int));
	fb = (int **)malloc(kn * sizeof(int *));
	fl = (int **)malloc(kn * sizeof(int *));

	for (i = 0; i < n; i++) {
		array[i] = rand() % (int)n;
	}
	for (i = 0; i < kn; i++) {
		keys[i] = rand() % (int)n;
	}

	qsort(array, n, sizeof(int), comp);

	gettimeofday(&start_b, NULL);
	for (i = 0; i < kn; i++) {
		fb[i] = bsearch(&keys[i], array, n, sizeof(int), comp);
	}
	gettimeofday(&end_b, NULL);
	timersub(&end_b, &start_b, &ela_b);

	gettimeofday(&start_l, NULL);
	for (i = 0; i < kn; i++) {
		fl[i] = lsearch(&keys[i], array, n, sizeof(int), comp);
	}
	gettimeofday(&end_l, NULL);
	timersub(&end_l, &start_l, &ela_l);

	for (i = 0; i < kn; i++) {
		if (fb[i] && fl[i] && *fb[i] == *fl[i])
			continue;

		if (fb[i] != fl[i])
			printf("diff %d: key:%d, fb:%d, fl:%d\n",
				(int)i, keys[i],
				(fb[i]) ? *fb[i] : -1,
				(fl[i]) ? *fl[i] : -1);
	}

	printf("n:%d, loop:%d, bin: %d.%06d[s], lin: %d.%06d[s]\n",
		(int)n, (int)kn,
		(int)ela_b.tv_sec, (int)ela_b.tv_usec,
		(int)ela_l.tv_sec, (int)ela_l.tv_usec);

	return 0;
}

コピペしていたり、エラー処理が甘かったり、適当な書き方で申し訳ないですが、性能比較が目的なのでそこは見逃していただくとして。測ってみるとこんな結果になりました。

環境はRyzen 7 2700, Debian 10 (Linux 5.2.0-3-amd64) です。コンパイラはgcc 9.2.1で、最適化レベルは -O2 です。

$ for i in 1 `seq 25 25 500`; do ./a.out $i 1000000; done

n:1, loop:1000000, bin: 0.001702[s], lin: 0.001710[s]
n:25, loop:1000000, bin: 0.019114[s], lin: 0.011656[s]
n:50, loop:1000000, bin: 0.022469[s], lin: 0.018549[s]
n:75, loop:1000000, bin: 0.026413[s], lin: 0.023774[s]
n:100, loop:1000000, bin: 0.028008[s], lin: 0.028900[s]
n:125, loop:1000000, bin: 0.029601[s], lin: 0.034308[s]  ★この辺りで逆転される★
n:150, loop:1000000, bin: 0.030671[s], lin: 0.040280[s]
n:175, loop:1000000, bin: 0.031898[s], lin: 0.045664[s]
n:200, loop:1000000, bin: 0.032771[s], lin: 0.048153[s]
n:225, loop:1000000, bin: 0.033985[s], lin: 0.052148[s]
n:250, loop:1000000, bin: 0.034322[s], lin: 0.055871[s]
n:275, loop:1000000, bin: 0.034761[s], lin: 0.059935[s]
n:300, loop:1000000, bin: 0.035766[s], lin: 0.065683[s]
n:325, loop:1000000, bin: 0.036407[s], lin: 0.070435[s]
n:350, loop:1000000, bin: 0.037010[s], lin: 0.072971[s]
n:375, loop:1000000, bin: 0.036926[s], lin: 0.077805[s]
n:400, loop:1000000, bin: 0.037422[s], lin: 0.082656[s]
n:425, loop:1000000, bin: 0.037844[s], lin: 0.086240[s]
n:450, loop:1000000, bin: 0.038894[s], lin: 0.089354[s]
n:475, loop:1000000, bin: 0.038516[s], lin: 0.093286[s]
n:500, loop:1000000, bin: 0.038590[s], lin: 0.100021[s]

結果の見方ですが、最初のn: は配列の要素数です。次のloop: は何回検索するかを表しています。bin: は2分探索bsearch、lin: は線形探索lsearchを表し、それぞれloop回実行し終わるまでの時間を出しています。

線形探索と2分探索の逆転ポイントは実行するたびに割とズレますが、N=500にもなれば、もはや線形探索に勝ち目はありません。2分探索強いです。

ループ回数を増やしても大勢に影響はありませんが、ループ回数を増やすほどlsearchがわずかに有利になるようです。N=1のときlsearchが勝つことが多いので、関数の呼び出しコストが低いのかも？

個人的に予想していたN=1000〜2000のレンジでは、線形探索は桁違いに遅かった（2分探索の10倍近く時間がかかる）です。私の予想は当てにならんなあ。

イコライザー

普段ヘッドフォンを使っているのですが、若干、低音が足りないなと思うことがあります。

Windows標準のBass Boostは設定項目が2つと大変シンプルでわかりやすいですが、音の歪みを防止するためなのか、Boostを有効にすると音が全体的に小さくなってしまうのが辛いところです。

Bass Boost

最大値は24dBですが、最大値に設定しようものなら非常に音が小さくなります。良いヘッドフォンアンプを持っていればアンプ側で音量を上げれば良いですが、PCのヘッドフォン端子に直接ヘッドフォンを接続している場合は、ボリュームを最大にしても聞こえなくなる可能性があります。

Bass Boostの設定画面

これはイマイチだなあってことで、代わりを探していましたら、VLC Playerのイコライザはシンプルデザインかつ設定の幅が広くて、とても良かったです。

VLCイコライザの設定画面

全体の音量（Preamp）と、各帯域ごとの音量を別々に調整できるので、WindowsのBass Boostに似た設定もできる（Preampを下げ、80Hz帯を上げる）し、音が歪むのもお構いなしの設定にもできます。あまりやりすぎるとバリバリ言い始めるのでほどほどに、ですけど。

linux-nextの不思議なバージョン情報

Linuxというかlinux-nextですが、リポジトリ内のファイルをオリジナルから変更してビルドした場合、バージョン情報の最後に -dirtyが付きます。あれはどうやっているのだろう？？と気になりました。

Makefileを眺めていると、scripts/setlocalversionというスクリプトでローカルバージョンを付与しているように見えます。

試しにcleanなリポジトリでscripts/setlocalversionを実行すると、-next-20191009のようなlocalversionのみ（※）が表示され、ファイルを適当に書き換えてから実行すると、-next-20191009-dirtyになりました。このスクリプトで当たりっぽいです。

もしLinux Upstreamカーネルで試す場合は、CONFIG_LOCALVERSION_AUTOをyにして、make prepareを実行する必要があります。そうしないとscripts/setlocalversionを実行しても "+" しか表示されません。

（※）この文字列はトップディレクトリのlocalversion-nextというファイルに書いてあります。

Gitの小技、リポジトリ変更を検知

スクリプトsetlocalversionを追いかけてみるとgit --no-optional-locks status -uno --porcelainで変更を検知して、-dirtyを出力するかどうか決めていました。オプション --porcelainのヘルプを見ると「スクリプトなどで処理しやすい形式でstatusを出力する」とのことです。へえー、こんなのあるんだ。初めて知りました。

オプション --no-optional-locksはロックを取らずに実行するという意味です。ヘルプ曰く、バックグラウンドでstatusを実行する際に、他のgit statusプロセスと衝突するので、指定した方が良いとのこと。手動で使うことはなさそうだし、気にしなくて良いでしょう。

オプション-unoは --untracked-files=noの省略形です。効果は実際に見た方が早いです。以下をご覧ください。

#### scripts/setlocalversionを書き換え

$ vim scripts/setlocalversion

#### 未追跡ファイルaaaを作成

$ touch aaa

上記の変更を加えたうえで、オプション -unoなし、オプション -unoありで、それぞれ実行してみます。

$ git status --porcelain

 M scripts/setlocalversion
?? aaa


$ git status -uno --porcelain

下記と同じ

$ git status --untracked-files=no --porcelain

 M scripts/setlocalversion

見た目で明らかだとは思いますが、オプション -unoが指定されていない場合は、未追跡のファイルaaaも表示されますが、-unoを指定すると未追跡のファイルは無視します。

スクリプト内でGitリポジトリが変更されたか？されていないか？を判定する必要は、普通の人はほぼ無いと思うんですけど……、もし必要が生じたら、sedとかgrepとかでゴチャゴチャやらずに、オプション --porcelainを使いましょう。

Gitの小技、コミットID取得

最近、会社でCI/CDで自動化のマネごとを始めました。といっても大したことはなくて、ビルドしてDebianやRPMパッケージを作って、Webサーバーにぶっこむだけです。

Nightlyビルドのパッケージを作成する際に、パッケージ名の最後にGitのコミットIDを付加しようと思ったのですが、方法が分かりません。調べてみるとrev-parseというコマンドを使うそうです。知らなかった。

$ git rev-parse HEAD

5ab7d0ae0c170fc0409d564fe945aac5ce54f86c

$ git rev-parse --short HEAD

5ab7d0ae0c1

ID全部だと長すぎるため --shortオプションを使うとより良いです。

台風19号

あの台風15号（Faxai）（2019年9月8日の日記参照）を超える、かつてない規模の台風19号（Hagibis）が来るということで、窓にガラス飛散防止でダンボールを貼ってみたり、食料、水を買い込んで備えていました。

都内だと多摩川沿いの一部堤防のない地域が水浸し、東日本だと長野、宮城が洪水で大変なことになっているそうで、東京の治水事業には感謝しかありません。

多摩川の水位

我が家からはやや遠いですが、最寄りの大きな川といえば多摩川です。水位が大変なことになっていて、思わずスクリーンショットを撮ってしまいました……。

家

我が家は北と東に窓がありまして、台風15号のときは北からガンガン風と雨が吹き付けていたため、あまりの風圧に、雨が窓サッシの隙間から侵入していました。壁に飛来物が当たり、ものすごい音もしていました（窓の真横に当たり、窓にはギリギリ当たらず本当に幸運だった）。今回はどうやら西、ないし、南から吹き付けていたようで、15号のときほど被害はありませんでした。

今回は全体的に幸運でしたが、災害への備えは日頃からやっておいて損はないですね。

家財

家の外にある家財は車くらいしかないので、台風が過ぎた後に見に行ってみましたが、特に飛来物が当たった形跡もなく、何ともなかったです。良かった良かった。