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分探索と揃えています。
処理の概要は下記の通りです。探索の対象は同じものを使っています。
ソースコードは下記のとおりです。
#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倍近く時間がかかる)です。私の予想は当てにならんなあ。
< | 2019 | > | ||||
<< | < | 10 | > | >> | ||
日 | 月 | 火 | 水 | 木 | 金 | 土 |
- | - | 1 | 2 | 3 | 4 | 5 |
6 | 7 | 8 | 9 | 10 | 11 | 12 |
13 | 14 | 15 | 16 | 17 | 18 | 19 |
20 | 21 | 22 | 23 | 24 | 25 | 26 |
27 | 28 | 29 | 30 | 31 | - | - |
合計:
本日:
管理者: Katsuhiro Suzuki(katsuhiro( a t )katsuster.net)
This is Simple Diary 1.0
Copyright(C) Katsuhiro Suzuki 2006-2023.
Powered by PHP 8.2.15.
using GD bundled (2.1.0 compatible)(png support.)