情報学部 菅沼ホーム 目次 索引

ソートと探索

    1. A. C++
    2. B. Java
    3. C. JavaScript
    4. D. PHP
    5. E. Ruby
    6. F. Python

  1. C++

    　　まず，new 演算子を使用した 1 次元配列に，ランダムに生成した 1,000,000 個のデータを記憶し，その後，C++ 標準ライブラリ内の sort 関数によってソートし，二分探索（バイナリサーチ）を行う C++ 標準ライブラリ内の binary_search 関数によって探索しています．探索するデータは，最初に生成したデータの 10 個毎のデータです（ 100,000 個）．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

    　　次は，探索木を利用した例です．C++ 標準ライブラリ内の コンテナである set クラスは，二本木として実装されているようですので，これを使用します．まず，ランダムに生成した 1,000,000 個の整数データを set クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

    　　3 番目は，ハッシュを利用した例です．C++ 標準ライブラリ内の コンテナである unordered_map クラスでは，各要素は，キーのハッシュ値に基づきハッシュテーブルに格納されるため，これを使用します．まず，ランダムに生成した 1,000,000 個の整数データを unordered_map クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

    　　最後は，文字列の探索です．ランダムに生成した長さ 1,000,200 の文字列 str に対して，5,000 個の長さ 200 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．ここでは，文字列に対して 2 つの方法を使用しています．最初は，文字列を char の配列として表現し，C/C++ の標準関数 strstr 関数を利用した場合です．2 番目の例では，文字列に対して，C++ 標準ライブラリ内の string クラスを利用しています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています． 
    /****************************/
/* ソートと探索             */
/*      coded by Y.Suganuma */
/****************************/
#include <time.h>
#include <string.h>
#include <stdio.h>
#include <algorithm>
#include <random>
#include <vector>
#include <set>
#include <unordered_map>
#include <string>

using namespace std;

#define N 1000000
#define NS 100000

int main()
{
			// 初期設定
	random_device sd;
	mt19937 rnd(sd());
			//
			// 二分探索（ vector ）
			//
				// データ設定
	int *data   = new int [N];
	int *data_s = new int [NS];
	clock_t tm1 = clock();
	int m       = 0;
	for (int i1 = 0; i1 < N; i1++) {
		int k = rnd();
		data[i1] = k;
		if (i1%10 == 0) {
			data_s[m] = k;
			m++;
		}
	}
				// sort
	clock_t tm2 = clock();
	sort(data, data+N);
				// 二分探索
	clock_t tm3 = clock();
	int n = 0;
	for (int i1 = 0; i1 < NS; i1++) {
		bool b = binary_search(data, data+N, data_s[i1]);
		if (!b)
			n++;
	}
	clock_t tm4 = clock();
	printf("データ数(array)： %d，探索データ数 %d\n", N, NS);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   sort %d ms\n", (int)(tm3-tm2));
	printf("   二分探索 %d ms，失敗 %d\n", (int)(tm4-tm3), n);
			//
			// 探索木（ set ）
			//
				// データ設定
	set<int> s;
	tm1 = clock();
	m   = 0;
	for (int i1 = 0; i1 < N; i1++) {
		int k = rnd();
		pair<set<int>::iterator, bool> b = s.emplace(k);
		if (b.second) {
			if (i1%10 == 0) {
				data_s[m] = k;
				m++;
			}
		}
		else
			i1--;
	}
				// 探索
	tm2 = clock();
	n   = 0;
	for (int i1 = 0; i1 < NS; i1++) {
		if (s.find(data_s[i1]) == s.end())
			n++;
	}
	tm3 = clock();
	printf("データ数(set)： %d，探索データ数 %d\n", N, NS);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，失敗 %d\n", (int)(tm3-tm2), n);
			//
			// ハッシュ（ unordered_map ）
			//
				// データ設定
	unordered_map<int, double> um;
	uniform_real_distribution<> uniform_r(0, 1.0);
	tm1 = clock();
	m   = 0;
	for (int i1 = 0; i1 < N; i1++) {
		int k    = rnd();
		double v = uniform_r(rnd);
		pair<unordered_map<int, double>::iterator, bool> b;
		b = um.insert(pair<int, double>(k, v));
		if (b.second) {
			if (i1%10 == 0) {
				data_s[m] = k;
				m++;
			}
		}
		else
			i1--;
	}
				// 探索
	tm2 = clock();
	n   = 0;
	for (int i1 = 0; i1 < NS; i1++) {
		if (um.find(data_s[i1]) == um.end())
			n++;
	}
	tm3 = clock();
	printf("データ数(unordered_map)： %d，探索データ数 %d\n", N, NS);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，失敗 %d\n", (int)(tm3-tm2), n);
			//
			// 文字列（ 配列 ）
			//
	int N1  = 1000201;
	int NS1 = 5000;
	int NL  = 200;
				// データ設定
	char *str1      = new char [N1+1];
	char **data_st1 = new char *[NS1];
	for (int i1 = 0; i1 < NS1; i1++)
		data_st1[i1] = new char [NL+1];
	n = 0;
	for (int i1 = 0; i1 < N1; i1++) {
		str1[i1] = (char)(65 + 58 * uniform_r(rnd));
		if (n < NS1 && i1 >= 2*NL && (i1 % NL) == 0) {
			int k = i1 - NL - NL / 2 - 1;
			for (int i2 = 0; i2 < NL; i2++) {
				data_st1[n][i2] = str1[k];
				k++;
			}
			data_st1[n][NL] = '\0';
			if (n % 2 > 0)    // 存在しないデータの作成
				data_st1[n][NL/2] = '(';
			n++;
		}
	}
	str1[N1] = '\0';
				// 探索
	NS1    = n;
	tm2    = clock();
	int n1 = 0;
	int n2 = 0;
	for (int i1 = 0; i1 < NS1; i1++) {
		char *p = strstr(str1, data_st1[i1]);
		if (p != NULL)
			n1++;
		else
			n2++;
	}
	tm3 = clock();
	printf("文字数(char)： %d，探索データ（数 %d，文字数 %d）\n", N1, NS1, NL);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，成功 %d，失敗 %d\n", (int)(tm3-tm2), n1, n2);
			//
			// 文字列（ string ）
			//
				// データ設定
	vector<string> data_st;
	string str;
	NS1 = 5000;
	n   = 0;
	tm1 = clock();
	for (int i1 = 0; i1 < N1; i1++) {
		str += (char)(65 + 58 * uniform_r(rnd));
		if (n < NS1 && i1 >= 2*NL && (i1 % NL) == 0) {
			int k = i1 - NL - NL / 2 - 1;
			string s = str.substr(k, NL);
			if (n % 2 > 0)    // 存在しないデータの作成
				s = s.replace(NL/2, 1, "(");
			data_st.push_back(s);
			n++;
		}
	}
				// 探索
	NS1 = n;
	tm2 = clock();
	n1  = 0;
	n2  = 0;
	for (int i1 = 0; i1 < NS1; i1++) {
		string::size_type p = str.find(data_st[i1]);
		if (0 <= p && p < str.size()-1)
			n1++;
		else
			n2++;
	}
	tm3 = clock();
	printf("文字数(string)： %d，探索データ（数 %d，文字数 %d）\n", N1, NS1, NL);
	printf("   data %d ms\n", (int)(tm2-tm1));
	printf("   探索 %d ms，成功 %d，失敗 %d\n", (int)(tm3-tm2), n1, n2);

	return 0;
}
    （出力） 
    データ数(array)： 1000000，探索データ数 100000
   data 9 ms
   sort 67 ms
   二分探索 20 ms，失敗 0
データ数(set)： 1000000，探索データ数 100000
   data 689 ms
   探索 63 ms，失敗 0
データ数(unordered_map)： 1000000，探索データ数 100000
   data 414 ms
   探索 6 ms，失敗 0
文字数(char)： 1000201，探索データ（数 5000，文字数 200）
   data 467 ms
   探索 2970 ms，成功 2500，失敗 2500
文字数(string)： 1000201，探索データ（数 5000，文字数 200）
   data 47 ms
   探索 3568 ms，成功 2500，失敗 2500

  2. Java

    　　最初は，配列に 1,000,000 個のデータを記憶し，Arrays クラス内のメソッド sort によってソートし，1,000,000 個の一部である 100,000 個のデータで探索を行っています（ Arrays クラス内のメソッド binarySearch ）．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

    　　次は，探索木を利用した例です．Java においては，TreeSet クラスを使用します．まず，ランダムに生成した 1,000,000 個の整数データを TreeSet クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

    　　3 番目は，ハッシュを利用した例です．Java においては，HashMap クラスを使用します．まず，ランダムに生成した 1,000,000 個の整数データを HashMap クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

    　　最後は，文字列の探索です．String クラスのオブジェクトに，ランダムに生成した長さ 1,000,200 の文字列 str を記憶し，5,000 個の長さ 200 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています． 
    /****************************/
/* クイックソート           */
/*      coded by Y.Suganuma */
/****************************/
import java.io.*;
import java.util.*;

public class Test {
	public static void main(String args[])
	{
			// 初期設定
		int N     = 1000000;
		int NS    = 100000;
		Random rn = new Random();
			//
			// 二分探索（ array ）
			//
				// データ設定
		int data[]   = new int [N];
		int data_s[] = new int [NS];
		long tm1 = System.currentTimeMillis();
		int m    = 0;
		for (int i1 = 0; i1 < N; i1++) {
			int k = rn.nextInt();
			data[i1] = k;
			if (i1%10 == 0) {
				data_s[m] = k;
				m++;
			}
		}
				// sort
		long tm2 = System.currentTimeMillis();
		Arrays.sort(data);
				// 二分探索
		long tm3 = System.currentTimeMillis();
		int n = 0;
		for (int i1 = 0; i1 < NS; i1++) {
			int b = Arrays.binarySearch(data, data_s[i1]);
			if (b < 0)
				n++;
		}
		long tm4 = System.currentTimeMillis();
		System.out.printf("データ数(array)： %d，探索データ数 %d\n", N, NS);
		System.out.printf("   data %d ms\n", (tm2-tm1));
		System.out.printf("   sort %d ms\n", (tm3-tm2));
		System.out.printf("   二分探索 %d ms，失敗 %d\n", (tm4-tm3), n);
			//
			// 探索木（ TreeSet ）
			//
				// データ設定
		TreeSet  s = new TreeSet  ();
		tm1 = System.currentTimeMillis();
		m   = 0;
		for (int i1 = 0; i1 < N; i1++) {
			int k = rn.nextInt();
			boolean b = s.add(new Integer(k));
			if (b) {
				if (i1%10 == 0) {
					data_s[m] = k;
					m++;
				}
			}
			else
				i1--;
		}
				// 探索
		tm2 = System.currentTimeMillis();
		n   = 0;
		for (int i1 = 0; i1 < NS; i1++) {
			if (!s.contains(data_s[i1]))
				n++;
		}
		tm3 = System.currentTimeMillis();
		System.out.printf("データ数(TreeSet)： %d，探索データ数 %d\n", N, NS);
		System.out.printf("   data %d ms\n", (tm2-tm1));
		System.out.printf("   探索 %d ms，失敗 %d\n", (tm3-tm2), n);
			//
			// ハッシュ（ HashMap ）
			//
				// データ設定
		HashMap  um = new HashMap  ();
		tm1 = System.currentTimeMillis();
		m   = 0;
		for (int i1 = 0; i1 < N; i1++) {
			int k    = rn.nextInt();
			double v = rn.nextDouble();
			um.put(new Integer(k), new Double(v));
			if (i1%10 == 0) {
				data_s[m] = k;
				m++;
			}
		}
				// 探索
		tm2 = System.currentTimeMillis();
		n   = 0;
		for (int i1 = 0; i1 < NS; i1++) {
			if (!um.containsKey(data_s[i1]))
				n++;
		}
		tm3 = System.currentTimeMillis();
		System.out.printf("データ数(HashMap)： %d，探索データ数 %d\n", N, NS);
		System.out.printf("   data %d ms\n", (tm2-tm1));
		System.out.printf("   探索 %d ms，失敗 %d\n", (tm3-tm2), n);
			//
			// 文字列（ String ）
			//
		int N1  = 1000201;
		int NS1 = 5000;
		int NL  = 200;
		char data_st1[][] = new char [NS1][NL];
		char str1[]       = new char[N1];
				// データ設定
		tm1 = System.currentTimeMillis();
		n  = 0;
		for (int i1 = 0; i1 < N1; i1++) {
			str1[i1] = (char)(65 + 58 * rn.nextDouble());
			if (n < NS1 && i1 >= 2*NL && (i1 % NL) == 0) {
				int k = i1 - NL - NL / 2 - 1;
				for (int i2 = 0; i2 < NL; i2++) {
					data_st1[n][i2] = str1[k];
					k++;
				}
				if (n % 2 > 0)    // 存在しないデータの作成
					data_st1[n][NL/2] = '(';
				n++;
			}
		}
		String data_st[] = new String [NS1];
		for (int i1 = 0; i1 < NS1; i1++)
			data_st[i1] = new String(data_st1[i1]);
		String str = new String(str1);
				// 探索
		NS1 = n;
		tm2 = System.currentTimeMillis();
		int n1 = 0;
		int n2 = 0;
		for (int i1 = 0; i1 < NS1; i1++) {
			int p = str.indexOf(data_st[i1]);
			if (p >= 0)
				n1++;
			else
				n2++;
		}
		tm3 = System.currentTimeMillis();
		System.out.printf("文字数(String)： %d，探索データ（数 %d，文字数 %d）\n", N1, NS1, NL);
		System.out.printf("   data %d ms\n", (int)(tm2-tm1));
		System.out.printf("   探索 %d ms，成功 %d，失敗 %d\n", (int)(tm3-tm2), n1, n2);
	}
}
    （出力） 
    データ数(array)： 1000000，探索データ数 100000
   data 19 ms
   sort 90 ms
   二分探索 24 ms，失敗 0
データ数(TreeSet)： 1000000，探索データ数 100000
   data 1297 ms
   探索 92 ms，失敗 0
データ数(HashMap)： 1000000，探索データ数 100000
   data 1027 ms
   探索 19 ms，失敗 0
文字数(String)： 1000201，探索データ（数 5000，文字数 200）
   data 51 ms
   探索 4476 ms，成功 2500，失敗 2500

  3. JavaScript

    　　ここをクリックし，表示された画面の「実行」ボタンをクリックすると，画面上で結果を見ることができます．なお，実行時間，データ数を多くするとブラウザが不安定になる，等の問題から，対象とするデータ数を減らしています．

    　　まず，1 次元配列に，ランダムに生成した 500,000 個のデータを記憶し，その後，Array オブジェクト内の sort 関数によってソートし，indexOf によって探索しています．探索するデータは，最初に生成したデータの 10 個毎のデータです（ 50,000 個）．また，二分探索を行う関数を作成し，その結果とも比較しています．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

    　　最後は，文字列の探索です．ランダムに生成した長さ 500,200 の文字列 str に対して，5,000 個の長さ 100 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています． 
    <!DOCTYPE HTML>

<HTML>

<HEAD>

	<TITLE>ソートと探索</TITLE>
	<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=utf-8">
	<SCRIPT TYPE="text/javascript">
		res = "";
			//
			// main
			//
		function main() {
				//
				// 探索（配列）
				//
			let N  = 500000;
			let NS = 50000;
					// データ設定
			let data   = new Array();
			let data_s = new Array();
			let now    = new Date();
			let tm1    = now.getTime();
			let    m   = 0;
			for (let i1 = 0; i1 < N; i1++) {
				let k    = Math.floor(2000000000 * Math.random());
				data[i1] = k;
				if (i1%10 == 0) {
					data_s[m] = k;
					m++;
				}
			}
					// sort
			now     = new Date();
			let tm2 = now.getTime();
			data.sort((a, b) => a - b);
					// 探索
			now     = new Date();
			let tm3 = now.getTime();
			let n1  = 0;
			for (let i1 = 0; i1 < data_s.length; i1++) {
				if (data.indexOf(data_s[i1]) < 0)
					n1++;
			}
					// 二分探索
			now     = new Date();
			let tm4 = now.getTime();
			let n2  = 0;
			for (let i1 = 0; i1 < data_s.length; i1++) {
				if (b_search(data_s[i1], data, N) < 0)
					n2++;
			}
			now     = new Date();
			let tm5 = now.getTime();

			res = res + "データ数(array)： " + data.length + "，探索データ数 " + data_s.length + "\n";
			res = res + "   data " + (tm2-tm1) + " ms\n";
			res = res + "   sort " + (tm3-tm2) + " ms\n";
			res = res + "   探索 " + (tm4-tm3) + " ms，失敗 " + n1 + "\n";
			res = res + "   二分探索 " + (tm5-tm4) + " ms，失敗 " + n2 + "\n";
				//
				// 文字列（ string ）
				//
					// データ設定
			let N1      = 500201;
			let NS1     = 5000;
			let NL      = 100;
			let data_st = new Array();
			str         = "";
			m           = 0;
			now         = new Date();
			tm1         = now.getTime();
			for (let i1 = 0; i1 < N1; i1++) {
				str += String.fromCharCode(Math.floor(65 + 58 * Math.random()));
				if (m < NS1 && i1 >= 2*NL && (i1 % NL) == 0) {
					let k = i1 - NL - NL / 2 - 1;
					let s = str.substr(k, NL);
					if (m % 2 > 0)    // 存在しないデータの作成
						s = s.substr(k, NL/2) + "(" + s.substr(NL/2+1, NL/2-1);
					data_st[m] = s;
					m++;
				}
			}
					// 探索
			now = new Date();
			tm2 = now.getTime();
			n1  = 0;
			n2  = 0;
			for (let i1 = 0; i1 < NS1; i1++) {
				if (str.indexOf(data_st[i1]) < 0)
					n2++;
				else
					n1++;
			}
			now = new Date();
			tm3 = now.getTime();
			res = res + "文字数(string)： " + str.length + "，探索データ（数 " + data_st.length + "，文字数 " + data_st[0].length + "）\n";
			res += "   data " + (tm2-tm1) + " ms\n";
			res = res + "   探索 " + (tm3-tm2) + " ms，成功 " + n1 + "，失敗 " + n2 + "\n";

			document.getElementById("result").value = res;
		}
			//
			// 二分探索
			//
		function b_search(key, data, n)
		{
			let sw    = -1;
			let left  = 0;
			let right = n - 1;

			if (data[right] > data[left]) {
				while (left < right) {
					let center = Math.floor((left + right) / 2);
					if (data[center] < key)
						left = (center < n-1) ? center + 1 : center;
					else
						right = center;
				}
			}
			else {
				while (left < right) {
					let center = Math.floor((left + right) / 2);
					if (data[center] > key)
						left = (center < n-1) ? center + 1 : center;
					else
						right = center;
				}
			}

			if (data[left] == key)
				sw = left;

			return sw;
		}
	</SCRIPT>

</HEAD>

<BODY STYLE="font-size: 130%; text-align:center; background-color: #eeffee;">

	<H2><B>ソートと探索</B></H2>

	<BUTTON STYLE="font-size: 100%; background-color: pink" onClick="return main()">実行</BUTTON><BR>
	<P>
	<DIV STYLE="text-align:center">実行結果</DIV>
	<TEXTAREA ID="result" COLS="70" ROWS="10" STYLE="font-size: 100%;"></TEXTAREA>
</BODY>

</HTML>
    （出力） 
    データ数(array)： 500000，探索データ数 50000
   data 44 ms
   sort 523 ms
   探索 20356 ms，失敗 0
   二分探索 31 ms，失敗 0
文字数(string)： 500201，探索データ（数 5000，文字数 100）
   data 1230 ms
   探索 177 ms，成功 2500，失敗 2500

  4. PHP

    　　まず，1 次元配列に，ランダムに生成した 1,000,000 個のデータを記憶し，その後，配列を扱う sort 関数によってソートし，in_array によって探索しています．探索するデータは，最初に生成したデータの 10 個毎のデータです（ 100,000 個）．また，二分探索を行う関数を作成し，その結果とも比較しています．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

    　　最後は，文字列の探索です．ランダムに生成した長さ 1,000,200 の文字列 str に対して，5,000 個の長さ 200 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています． 
    /****************************/
/* ソートと探索             */
/*      coded by Y.Suganuma */
/****************************/
<?php
			//
			// 二分探索
			//
	function b_search($key, $data, $n) {
		$sw    = -1;
		$left  = 0;
		$right = $n - 1;

		if ($data[$right] > $data[$left]) {
			while ($left < $right) {
				$center = floor(($left + $right) / 2);
				if ($data[$center] < $key)
					$left = ($center < $n-1) ? $center + 1 : $center;
				else
					$right = $center;
			}
		}
		else {
			while ($left < $right) {
				$center = floor(($left + $right) / 2);
				if ($data[$center] > $key)
					$left = ($center < $n-1) ? $center + 1 : $center;
				else
					$right = $center;
			}
		}

		if ($data[$left] == $key)
			$sw = $left;

		return $sw;
	}
			// 初期設定
	mt_srand();
			//
			// 探索（配列）
			//
				// データ設定
	$N      = 1000000;
	$NS     = 100000;
	$data   = array();
	$data_s = array();
	$tm1    = microtime();
	$ms     = strtok($tm1, " ");
	$sec    = strtok(" ");
	$tm1    = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);
	$m      = 0;
	for ($i1 = 0; $i1 < $N; $i1++) {
		$k         = mt_rand(0, 2000000000);
		$data[$i1] = $k;
		if ($i1%10 == 0) {
			$data_s[$m] = $k;
			$m++;
		}
	}
				// sort
	$tm2 = microtime();
	$ms  = strtok($tm2, " ");
	$sec = strtok(" ");
	$tm2 = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);
	sort($data);
				// 探索
	$tm3 = microtime();
	$ms  = strtok($tm3, " ");
	$sec = strtok(" ");
	$tm3 = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);
	$n   = 0;
	for ($i1 = 0; $i1 < $NS; $i1++) {
		if (!in_array($data_s[$i1], $data))
			$n++;
	}
				// 二分探索
	$tm4 = microtime();
	$ms  = strtok($tm4, " ");
	$sec = strtok(" ");
	$tm4 = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);
	$n   = 0;
	for ($i1 = 0; $i1 < $NS; $i1++) {
		if (b_search($data_s[$i1], $data, $N) < 0)
			$n++;
	}
	$tm5 = microtime();
	$ms  = strtok($tm5, " ");
	$sec = strtok(" ");
	$tm5 = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);

	printf("データ数(array)： %d，探索データ数 %d\n", $N, $NS);
	printf("   data %d ms\n", $tm2-$tm1);
	printf("   sort %d ms\n", $tm3-$tm2);
	printf("   探索 %d ms，失敗 %d\n", ($tm4-$tm3), $n);
	printf("   二分探索 %d ms，失敗 %d\n", ($tm5-$tm4), $n);
			//
			// 文字列（ string ）
			//
	$N1  = 1000201;
	$NS1 = 5000;
	$NL  = 200;
				// データ設定
	$data_st = array();
	$str     = "";
	$n       = 0;
	$tm1     = microtime();
	$ms      = strtok($tm1, " ");
	$sec     = strtok(" ");
	$tm1     = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);
	for ($i1 = 0; $i1 < $N1; $i1++) {
		$str = $str.chr(mt_rand(65, 123));
		if ($n < $NS1 && $i1 >= 2*$NL && ($i1 % $NL) == 0) {
			$k = $i1 - $NL - $NL / 2 - 1;
			$s = substr($str, $k, $NL);
			if ($n % 2 > 0) {    // 存在しないデータの作成
				$s1 = substr($s, $k, $NL/2);
				$s1 = $s1."(";
				$s1 = $s1.substr($s, $NL/2+1, $NL-$NL/2-1);
				$s  = $s1;
			}
			$data_st[$n] = $s;
			$n++;
		}
	}
				// 探索
	$tm2 = microtime();
	$ms  = strtok($tm2, " ");
	$sec = strtok(" ");
	$tm2 = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);
	$NS1 = $n;
	$n1  = 0;
	$n2  = 0;
	for ($i1 = 0; $i1 < $NS1; $i1++) {
		if (strstr($str, $data_st[$i1]) == FALSE)
			$n2++;
		else
			$n1++;
	}
	$tm3     = microtime();
	$ms      = strtok($tm3, " ");
	$sec     = strtok(" ");
	$tm3     = (intval($sec) % 1000) * 1000 + intval(floatval($ms) * 1000);

	printf("文字数(string)： %d，探索データ（数 %d，文字数 %d）\n", $N1, $NS1, $NL);
	printf("   data %d ms\n", ($tm2-$tm1));
	printf("   探索 %d ms，成功 %d，失敗 %d\n", ($tm3-$tm2), $n1, $n2);
?>
    （出力） 
    データ数(array)： 1000000，探索データ数 100000
   data 186 ms
   sort 336 ms
   探索 103832 ms，失敗 0
   二分探索 397 ms，失敗 0
文字数(string)： 1000201，探索データ（数 5000，文字数 200）
   data 28210 ms
   探索 462 ms，成功 2500，失敗 2500

  5. Ruby

    　　最初は，Array クラスによって生成した配列に 1,000,000 個のデータを記憶し，Array クラス内のメソッド sort によってソートし，1,000,000 個の一部である 100,000 個のデータで探索を行っています（ Array クラス内のメソッド bsearch ）．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

    　　次は，ハッシュを利用した例です．Ruby においては，Hash クラスを使用します．まず，ランダムに生成した 50,000 個の整数データを Hash クラスに保存し，その後，最初に生成したデータの 10 個毎のデータ（ 50,000 個）に対して探索を行っています．これは，私のパソコンではスタックオーバーフローのため，これ以上のデータを扱えないためです．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

    　　最後は，文字列の探索です．String クラスのオブジェクトに，ランダムに生成した長さ 1,000,200 の文字列 str を記憶し，5,000 個の長さ 200 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています． 
    #****************************/
#* ソートと探索             */
#*      coded by Y.Suganuma */
#****************************/
	# 初期設定
srand()
		#
		# 二分探索（ vector ）
		#
			# データ設定
nn     = 1000000
ns     = 100000
data   = Array.new()
data_s = Array.new()
tm1 = Process.times
for i1 in (0...nn)
	k = rand(2000000000)
	data.push(k)
	if i1%10 == 0
		data_s.push(k)
	end
end
			# sort
tm2  = Process.times
data = data.sort
			# 二分探索
tm3 = Process.times
n   = 0
for x in data_s
	b = data.bsearch { |v| v >= x }
	if b == nil
		n += 1
	end
end
tm4  = Process.times
printf "データ数(array)： %d，探索データ数 %d\n", nn, ns
printf "   data %d ms\n", Integer(1000*(tm2[0] - tm1[0] + tm2[1] - tm1[1]))
printf "   sort %d ms\n", Integer(1000*(tm3[0] - tm2[0] + tm3[1] - tm2[1]))
printf "   二分探索 %d ms，失敗 %d\n", Integer(1000*(tm4[0] - tm3[0] + tm4[1] - tm3[1])), n
		#
		# ハッシュ（ Hash クラス ）
		#
			# データ設定
nn  = 50000
ns  = 5000
key = Array.new()
val = Array.new()
m   = 0;
tm1  = Process.times
for i1 in (0...nn)
	k = rand(2000000000)
	key.push(k)
	v = rand()
	val.push(k)
	if i1%10 == 0
		data_s[m] = k
		m += 1
	end
end
x  = key.zip(val)
ha = Hash[*x.flatten]
			# 探索
tm2 = Process.times
n   = 0;
for i1 in (0...ns)
	p = ha.fetch(data_s[i1], -1)
	if (p < 0)
		n += 1;
	end
end
tm3 = Process.times
printf "データ数(Hash クラス)： %d，探索データ数 %d\n", nn, ns
printf "   data %d ms\n", Integer(1000*(tm2[0] - tm1[0] + tm2[1] - tm1[1]))
printf "   探索 %d ms，失敗 %d\n", Integer(1000*(tm3[0] - tm2[0] + tm3[1] - tm2[1])), n
		#
		# 文字列（ string ）
		#
nn      = 1000201
ns      = 5000
nl      = 200
			# データ設定
data_st = Array.new
tm1     = Process.times
n       = 0
str     = ""
for i1 in (0...nn)
	str.concat(Integer(65 + 58 * rand()))
	if (n < ns && i1 >= 2*nl && i1 % nl == 0)
		k = i1 - nl - nl / 2 - 1
		s = str.slice(k, nl)
		if (n % 2 > 0)    # 存在しないデータの作成
			k       = nl / 2
			s[k..k] = "("
		end
		data_st.push(s)
		n += 1
	end
end
			# 探索
tm2 = Process.times
ns  = n
n1  = 0
n2  = 0
for i1 in (0...ns)
	p = str.index(data_st[i1]);
	if (p == nil)
		n2 += 1
	else
		n1 += 1
	end
end
tm3 = Process.times
printf "文字数(String)： %d，探索データ（数 %d，文字数 %d）\n", nn, ns, nl
printf "   data %d ms\n", Integer(1000*(tm2[0] - tm1[0] + tm2[1] - tm1[1]))
printf "   探索 %d ms，成功 %d，失敗 %d\n", Integer(1000*(tm3[0] - tm2[0] + tm3[1] - tm2[1])), n1, n2
    （出力） 
    データ数(array)： 1000000，探索データ数 100000
   data 610 ms
   sort 1031 ms
   二分探索 266 ms，失敗 0
データ数(Hash クラス)： 50000，探索データ数 5000
   data 170 ms
   探索 0 ms，失敗 0
文字数(String)： 1000201，探索データ（数 5000，文字数 200）
   data 516 ms
   探索 453 ms，成功 2500，失敗 2500

  6. Python

    　　最初は，リストに 1,000,000 個のデータを記憶し，リスト内のメソッド sort によってソートしています．リストには，二分探索を行うメソッドがありませんので，bisect モジュールによって，1,000,000 個の一部である 100,000 個のデータによってその近傍の探索を行っています．データを記憶するのにかかった時間，ソートにかかった時間，及び，探索にかかった時間を出力しています．

    　　次は，ハッシュを利用した例です．Python においては，マッピング型 dict を使用します．まず，ランダムに生成した 1,000,000 個の整数データを dict に保存し，その後，最初に生成したデータの 10 個毎のデータ（ 100,000 個）に対して探索を行っています．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています．

    　　最後は，文字列の探索です．文字列型に，ランダムに生成した長さ 1,000,200 の文字列 str を記憶し，5,000 個の長さ 200 の文字列を探索しています．5,000 個の文字列は，str の部分文字列であり，その内，半分には，文字列 str に含まれない文字が 1 文字含まれています．そのため，半分の文字列に対しては，探索しても見つからないことになります．データを記憶するのにかかった時間，及び，探索にかかった時間を出力しています． 
    #****************************/
#* ソートと探索             */
#*      coded by Y.Suganuma */
#****************************/
# -*- coding: UTF-8 -*-
import sys
import time
import bisect
from random import *

		# 初期設定
seed()
		#
		# 二分探索（ vector ）
		#
			# データ設定
N      = 1000000
NS     = 100000
data   = list()
data_s = list()
tm1    = time.perf_counter()
m      = 0;
for i1 in range(0, N) :
	k = randint(0, 2000000000)
	data.append(k)
	if i1%10 == 0 :
		data_s.append(k)
			# sort
tm2 = time.perf_counter()
data.sort();
			# 二分探索支援
tm3 = time.perf_counter()
for i1 in range(0, NS) :
	bisect.bisect(data, data_s[i1])
tm4 = time.perf_counter()
print("データ数(list)：", N, "探索データ数", NS)
print("   data", int((tm2 - tm1) * 1000), "ms")
print("   sort ", int((tm3 - tm2) * 1000), "ms")
print("   二分探索 ", int((tm4 - tm3) * 1000), "ms")
		#
		# ハッシュ（ unordered_map ）
		#
			# データ設定
um  = dict()
tm1 = time.perf_counter()
data_s.clear()
for i1 in range(0, N) :
	k = randint(0, 2000000000)
	v = random()
	um[k] = v
	if i1%10 == 0 :
		data_s.append(k)
			# 探索
tm2 = time.perf_counter()
n   = 0;
for i1 in range(0, NS) :
	if um.get(data_s[i1], -1) < 0 :
		n += 1
tm3 = time.perf_counter()
print("データ数(dict)： ", N, "，探索データ数 ", NS)
print("   data", int((tm2 - tm1) * 1000), "ms")
print("   探索 ", int((tm3 - tm2) * 1000), "ms", "失敗", n)
		#
		# 文字列（ string ）
		#
N1  = 1000201
NS1 = 5000
NL  = 200
			# データ設定
data_st = list()
st      = ""
n       = 0
tm1     = time.perf_counter()
for i1 in range(0, N1) :
	st += chr(int(65 + 58 * random()))
	if n < NS1 and i1 >= 2*NL and i1 % NL == 0 :
		k = int(i1 - NL - NL / 2 - 1)
		s = st[k : NL]
		if n % 2 > 0 :    # 存在しないデータの作成
			k   = int(NL / 2)
			k1  = k + 1
			s1  = s[0 : k]
			s1 += "("
			s   = s1 + s[k1 : NL]
		data_st.append(s)
		n += 1
			# 探索
tm2 = time.perf_counter()
n1  = 0
n2  = 0
for i1 in range(0, NS1) :
	if st.find(data_st[i1]) < 0 :
		n2 += 1
	else :
		n1 += 1
tm3 = time.perf_counter()
print("文字数(string)： ", N1, "，探索データ（数 ", NS1, "，文字数 ", NL, "）")
print("   data", int((tm2 - tm1) * 1000), "ms")
print("   探索", int((tm3 - tm2) * 1000), "ms，成功 ", n1, "，失敗 ", n2)
    （出力） 
    データ数(list)： 1000000 探索データ数 100000
   data 2705 ms
   sort  722 ms
   二分探索  200 ms
データ数(dict)：  1000000 ，探索データ数  100000
   data 2938 ms
   探索  55 ms 失敗 0
文字数(string)：  1000201 ，探索データ（数  5000 ，文字数  200 ）
   data 1428 ms
   探索 620 ms，成功  2500 ，失敗  2500

情報学部 菅沼ホーム 目次 索引