Created
December 12, 2015 03:49
-
-
Save oyakodon/616cfa3bd1df449cd1a6 to your computer and use it in GitHub Desktop.
自作探索プログラムで探索アルゴリズムを比較する。(コンソールアプリケーション / C#)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
using System.Threading.Tasks; | |
namespace Search_Algo_Compare | |
{ | |
/// <summary> | |
/// 自作探索プログラムで探索アルゴリズムを比較する。 | |
/// </summary> | |
class Program | |
{ | |
static int Calc_cnt = 0; // 試行回数を記録するための変数 | |
static void Main(string[] args) | |
{ | |
// 入力待ち | |
Console.Write("続行するには何かキーを押してください . . ."); | |
Console.Read(); | |
#region 配列準備 | |
var renge = 10000; // 配列の要素数 | |
var target = renge; // 探索する目的の数(今回は10000) | |
// 配列に順番に数を代入していき、要素をシャッフル(実験用) | |
var deta = new List<int>(); | |
for (var i = 0; i < renge; ++i) | |
deta.Add(i + 1); | |
var n = deta.Count; | |
var rnd = new Random(); | |
while (n > 1) | |
{ | |
--n; | |
var k = rnd.Next(n + 1); | |
var tmp = deta[k]; | |
deta[k] = deta[n]; | |
deta[n] = tmp; | |
} | |
#endregion | |
// 配列の内容を全て表示 | |
for (var i = 0; i < deta.Count; ++i) | |
Console.Write(deta[i] + " "); | |
Console.WriteLine("\n\n目的の数 : " + target); // 目的の数を表示 | |
// ここから線形探索 | |
Console.WriteLine("\n[線形探索 (Linear Search)]"); | |
Console.WriteLine(Linear_Search(deta, target) ? "存在する" : "存在しない"); | |
Console.WriteLine("試行回数 : " + Calc_cnt); | |
Calc_cnt = 0; //試行回数のリセット | |
// ここから二分探索 | |
Console.WriteLine("\n[二分探索 (Binary Search)]"); | |
Console.WriteLine(Binary_Search(deta, target) ? "存在する" : "存在しない"); | |
Console.WriteLine("試行回数 : " + Calc_cnt); | |
// ここからC#が持っているバイナリサーチ | |
Console.WriteLine("\n[C#のバイナリサーチ]"); | |
deta.Sort(); // リストを整列 | |
// 「BinarySearch」では、目的の数がどこに入っているのかをintで返す。 | |
var ret = deta.BinarySearch(target); | |
Console.WriteLine(ret > 0 ? "存在する\n" : "存在しない\n"); | |
} | |
/// <summary> | |
/// 線形探索(リニアサーチ) | |
/// </summary> | |
/// <param name="deta">探索対象のリスト</param> | |
/// <param name="value">探索目標</param> | |
/// <returns>存在するか(True)、しないか(False)</returns> | |
static bool Linear_Search(List<int> deta, int value) | |
{ | |
for(var i = 0; i < deta.Count; ++i) // 要素数でループを回し、要素1つずつに対して比較を実行する。 | |
{ | |
++Calc_cnt; | |
if (deta[i] == value) | |
{ | |
return true; | |
} | |
} | |
return false; // 最後まで見つからなかったら、False。 | |
} | |
/// <summary> | |
/// 二分探索(バイナリサーチ) | |
/// </summary> | |
/// <param name="deta">探索対象のリスト</param> | |
/// <param name="value">探索目標</param> | |
/// <returns>存在するか(True)、しないか(False)</returns> | |
static bool Binary_Search(List<int> list, int value) | |
{ | |
var tmp = new List<int>(list); // リストのコピー | |
tmp.Sort(); // リストの整列 | |
int left = 0, mid = 0; | |
var right = tmp.Last(); | |
while (right >= left) | |
{ | |
++Calc_cnt; | |
mid = (right + left) / 2; //中央の数を計算 | |
if (tmp[mid] == value) | |
return true; | |
else if (list[mid] < value) | |
{ | |
// 真ん中の数 < 探索目標 であれば、範囲を真ん中の数より大きい要素に絞り込む。 | |
left = mid + 1; | |
} | |
else | |
{ | |
// 真ん中の数 > 探索目標 であれば、範囲を真ん中の数より小さい要素に絞り込む。 | |
right = mid - 1; | |
} | |
} | |
return false; // 最後まで見つからなかったら、False。 | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment