スピード勝負
アルゴリズムに大切なことは
・わかりやすい
・メモリ使用量が少ない
・速い
・スタイリッシュ&エレガント←
4つ目要るのか?
そげなことは置いときまして
『100万個のデータに対して、線形探索と二分探索ではどちらが速いのか?』
って問題があるわけですが、まぁ考えるまでもなく二分探索でしょう
データ数n、探索する数mの時、
線形探索の場合はO(nm)
二分探索の場合は、探索前にソートする必要があるのでO(nlogn) + O(mlogn)
ぶっちゃけ、探索数が少ないときは線形探索の方が速いんだよな
探索数が少ないとき、二分探索全体では(ソートする時間) > (探索する時間)だからだろうね
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <windows.h>
#include <mmsystem.h>
const int SEARCH = 500000;
int cmp(const void *a, const void *b)
{
return *(int*)a - *(int*)b;
}
int main(void)
{
int *data;
int search[SEARCH];
int i, j, count = 0;
FILE *fp;
int start, end;
// for (i = 0;i < 1000000;i++)
// printf("%d\n", rand()%5000000);
data = (int*)malloc(sizeof(int)*1000000);
fp = fopen("rand_data.txt", "r");
srand(10);
for (i = 0;i < SEARCH;i++)
search[i] = rand()%5000000;
for (i = 0;i < 1000000;i++)
fscanf(fp, "%d", &data[i]);
/*
///////////////////////////////////////////////////
count = 0;
start = timeGetTime();
for (i = 0;i < SEARCH;i++) {
for (j = 0;j < 1000000;j++) {
if (search[i] == data[j]) {
count++;
break;
}
}
}
end = timeGetTime();
printf("liner search\n");
printf("Match : %d\n", count);
printf("Time : %d msec\n", end-start);
///////////////////////////////////////////////////
*/
start = timeGetTime();
count = 0;
qsort(data, 1000000, sizeof(int), cmp);
for (i = 0;i < SEARCH;i++) {
if (bsearch(&search[i], data, 1000000, sizeof(int), cmp) != NULL)
count++;
}
end = timeGetTime();
printf("quick sort + binary search\n");
printf("Match : %d\n", count);
printf("Time : %d msec\n", end-start);
///////////////////////////////////////////////////
return 0;
}