平方根を求める関数で全探索と二分探索を比較

※TODO: 実行結果怪しいので諸々修正必要

はじめに

全探索と二分探索の概要
　全探索は、可能なすべての解候補を試し、最適な解を見つける手法です。一方、二分探索は、ソートされた配列やデータ構造内で特定の値を効率的に検索する手法です。
　この記事では、これらのアルゴリズムの基本的な概念と、それらの実装、速度の比較について掘り下げていきます。
研究目的と方法
　もともとアルゴリズムについて全く知識がなかった状態で平方根を求める関数の実装中に二分探索というアルゴリズムを知りました。
　関数の実装とアルゴリズムの勉強を兼ねて、引数に与えられた数値の平方根を求める関数を実装し、実行時間を比較計測します。
　なお、筆者の動作環境は以下です。
TODO:動作環境の記載あるいは動作環境用の記事を記載
実装する関数の要件
・引数に整数をとり、戻り値には引数の整数の平方根を返す。
・引数が平方数である場合には平方根を、それ以外は0を返す。
・引数が0以下の場合は0を返す。
結果
　今回の計測では、intの最大値を入力した場合では約30倍、longlongの最大値を入力した場合では約1200万倍の速度比で二分探索が速いと分かりました。

全探索の実装

全探索アルゴリズムの説明
全探索アルゴリズムは、問題の解候補が有限である場合に使用されます。このアルゴリズムでは、すべての解候補を順番に試し、条件を満たす解を見つけるまで繰り返します。全探索は、解候補の数が比較的少ない場合や、問題の入力サイズが小さい場合に有効ですが、解候補の数が増えると計算時間が爆発的に増加する可能性があります。
C言語での実装方法
　1からカウントアップする単純な実装です。計算量は最大で$\sqrt{nb}$になります。

sqrt_brute_force.c

long long	sqrt_brute_force(long long nb)
{
    long long	i;

	if (nb <= 0)
		return (0);
	i = 1;
	while (i <= nb / i)
	{
		if (
			(i == nb / i)
			&& (nb % i == 0)
			)
			return (i);
		i++;
	}
	return (0);
}

時間計測の実装
　文字列を数値に変換する関数について、今回のケースでは標準実装のatollを使うことが一般的だと思います。筆者は勉強のため、自力で最低限の機能だけ実装しました。ft_atoi_ll.cについてはappendixで記載しますが、いったんあらゆるエラー処理を無視すれば簡単に実装ができました。

main_brute.c

#include <stdio.h>
#include <time.h>
#include "sqrt_brute_force.c"
#include "ft_atoi_ll.c" 

int	main(int argc, char **argv)
{
	long long	nb;
	long long	ans;
	clock_t		start;
	clock_t		end;
	double		sec;

	if (argc != 2)
		return (0);
	nb = ft_atoi_ll(argv[1]);
	start = clock();
	ans = sqrt_brute_force(nb);
	end = clock();
	printf("%lld\n", ans);
	sec = (double)(end - start) / CLOCKS_PER_SEC;
	printf("全探索は%lldの平方根の探索に%f秒かかりました.\n", nb, sec);
	return (0);
}

二分探索の実装

二分探索アルゴリズムの説明
二分探索アルゴリズムは、ソートされた配列やデータ構造内で特定の値を効率的に検索する手法です。このアルゴリズムでは、探索対象の範囲を半分に分割しながら、目標の値を見つけるまで繰り返します。
　二分探索は、探索対象がソートされている必要がありますが、ソートされたデータを処理する場合に非常に効率的です。
C言語での実装方法
　一般的な二分探索を用いています。検索範囲の中間点の平方数が引数よりも小さい場合は検索対象を上位半分に更新し、逆ならば下位半分に更新します。
　注意点は、midの更新ルールを
mid = (start + end) / 2
とすることも可能ですが、この場合endに想定する最大値を代入した場合、オーバーフローするバグが発生するため、それを防ぐ実装にしています。
参考:

sqrt_binary_search.c

long long	sqrt_binary_search(long long nb)
{
	long long	start;
	long long	end;
	long long	mid;

	if (nb <= 0)
		return (0);
	start = 1;
	end = nb;
	while (start <= end)
	{
		mid = start + (end - start) / 2;
		if (
			(mid == nb / mid)
			&& (nb % mid == 0)
			)
			return (mid);
		else if (mid < nb / mid)
			start = mid + 1;
		else
			end = mid - 1;
	}
	return (0);
}

時間計測の実装
ft_atoi_ll.cについては同上。

main_binary.c

#include <stdio.h>
#include <time.h>
#include "sqrt_binary_search.c"
#include "ft_atoi_ll.c"

int	main(int argc, char **argv)
{
	long long	nb;
	long long	ans;
	clock_t		start;
	clock_t		end;
	double		sec;

	if (argc != 2)
		return (0);
	nb = ft_atoi_ll(argv[1]);
	start = clock();
	ans = sqrt_binary_search(nb);
	end = clock();
	printf("%lld\n", ans);
	sec = (double)(end - start) / CLOCKS_PER_SEC;
	printf("二分探索は%lldの平方根の探索に%f秒かかりました.\n", nb, sec);
	return (0);
}

計測結果の比較

全探索と二分探索の計測結果の比較
　筆者の実行環境で複数回実行したときの平均を取りました。

アルゴリズム	INT_MAXの実行時間	LONG_LONG_MAXの実行時間
全探索	約0.001秒	約60秒
二分探索	約0.00003秒	約0.000005秒

結論

計測結果から得られる知見
　今回の計測では、intの最大値を入力した場合では約30倍、longlongの最大値を入力した場合では約1200万倍の速度比で二分探索が速いと分かりました。
　今後の課題として、検索件数と各アルゴリズムの実行時間をプロットし、実行速度に明確な差が発生する試行回数を把握したいと思います。プロットを学び次第、追加で記事にします。

Appendix

　ft_atoi_llは以下で記載しています。標準実装のatoi関数はlong long型を扱えないためです。本題ではないため、標準実装のatoi関数とは仕様が全く異なる単純な実装にしています。
　※筆者がC言語の勉強かでら実装したというだけなので、一般的には標準実装されているatoll関数などを使用するべきだと思います。

ft_atoi_ll.c

long long ft_atoi_ll(char *str)
{
	long long	ll;

	if (*str == '\0')
		return (0);
	else if (*str == '-')
		return (0);
	ll = 0;
	while (*str)
	{
		ll = ll * 10 + (*str - '0');
		str++;
	}
	return (ll);
}

参考文献

参考にした資料や文献のリスト

WIP:平方根を求める関数で二分探索と全探索の速度を比較してみた