ソートと探索

# -*- coding: UTF-8 -*-
from random import *
from time import *
from bisect import *
from math import *
import numpy as np

#***************************/
# ソートと探索             */
#      coded by Y.Suganuma */
#***************************/
		# 初期設定
seed()
		#
		# 探索（list）
		#
			# データ設定
N      = 1000000
NS     = 100000
data   = []
data_s = []
m      = 0
tm1    = time()
for i1 in range(0, N) :
	k = floor(2000000000 * random())
	data.append(k)
	if i1%10 == 0 :
		data_s.append(k)
		m += 1
			# sort
tm2 = time()
data.sort()
			# 探索
tm3 = time()
for i1 in range(0, NS) :
	bisect_left(data, data_s[i1])
tm4 = time()

print("データ数(list)： " + str(N) + "，探索データ数 " + str(NS))
print("   data " + str(floor((tm2-tm1)*1000)) + " ms")
print("   ソート " + str(floor((tm3-tm2)*1000)) + " ms")
print("   二分探索 " + str(floor((tm4-tm3)*1000)) + " ms，失敗 0")
		#
		# 探索（NumPy）
		#
			# データ設定
N      = 1000000
NS     = 100000
data   = np.zeros(N, np.int)
data_s = np.zeros(NS, np.int)
n      = 0
m      = 0
tm1    = time()
for i1 in range(0, N) :
	k      = floor(2000000000 * random())
	data[n] = k
	n      += 1
	if i1%10 == 0 :
		data_s[m] = k
		m += 1
			# sort
tm2 = time()
np.sort(data)
			# 探索
tm3 = time()
for i1 in range(0, NS) :
	np.searchsorted(data, data_s[i1])
tm4 = time()

print("データ数(NumPy)： " + str(N) + "，探索データ数 " + str(NS))
print("   data " + str(floor((tm2-tm1)*1000)) + " ms")
print("   ソート " + str(floor((tm3-tm2)*1000)) + " ms")
print("   二分探索 " + str(floor((tm4-tm3)*1000)) + " ms，失敗 0")
		#
		# 文字列（ string ）
		#
N1  = 1000201
NS1 = 5000
NL  = 200
			# データ設定
data1   = bytearray()
data1_s = []
n       = 0
b       = bytearray(b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz")
tm1     = time()
for i1 in range(0, N1) :
	data1.append(b[floor(52 * random())])
	if n < NS1 and i1 >= 2*NL and (i1 % NL) == 0 :
		k = floor(i1 - NL - NL / 2 - 1)
		s = data1[k:k+NL]
		if n % 2 > 0 :    # 存在しないデータの作成
			s[5] = 40 
		data1_s.append(s)
		n += 1
				# 探索
tm2 = time()
NS1 = n
n1  = 0
n2  = 0
for i1 in range(0, NS1) :
	if data1.find(data1_s[i1]) < 0 :
		n2 += 1
	else :
		n1 += 1
tm3 = time()

print("文字数(bytearray)： " + str(N1) + "，探索データ（数 " + str(NS1) + "，文字数 " + str(NL) + "）")
print("   data " + str(floor((tm2-tm1)*1000)) + " ms")
print("   探索 " + str(floor((tm3-tm2)*1000)) + " ms，成功 " + str(n1) + "，失敗 " + str(n2))
		

（出力）

データ数(list)： 1000000，探索データ数 100000
   data 942 ms
   ソート 651 ms
   二分探索 197 ms，失敗 0
データ数(NumPy)： 1000000，探索データ数 100000
   data 1072 ms
   ソート 71 ms
   二分探索 183 ms，失敗 0
文字数(bytearray)： 1000201，探索データ（数 5000，文字数 200）
   data 1151 ms
   探索 3860 ms，成功 2500，失敗 2500