ソートと探索

<?php
/****************************/
/* ソートと探索             */
/*      coded by Y.Suganuma */
/****************************/
			//
			// 二分探索
			//
	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
*/
?>