ソートと探索

#****************************/
#* ソートと探索             */
#*      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