A programmer's site

点点滴滴：生活，技术

01 Jun 2013

python语言，binary search和dict对比

今天是国际儿童节。跟我没有什么关系。祝他们都能开心，快乐的成长。

dict可以用来判断一个元素是不是在集合里面，binary search也可以。一直想对比一下他们的性能：

查找，hash是O(1), binary search是O(logn)
由于array内存非常紧凑，可能内存访问会少一些，它还更省内存
我写过几个程序，array的数据是通过mmap得到，是别的程序排好序，写入文件的
有些语言，如C，标准库没有dict（map）的实现
个数从2k到200k，1500次查询，750个能查到，另外750个可能查到

测试代码

测试代码在。其中binary search的实现为：

def binary_search(arr, key):
    lo, hi = 0, (len(arr) - 1)
    while lo <= hi:
        mid = (lo + hi) >> 1
        k = arr[mid]
        if k == key:
            return mid
        elif k < key:
            lo = mid + 1 # search upper subarray
        else:
            hi = mid - 1 # search lower subarray
            # (-(insertion point) - 1)
    return -(lo + 1)

随机生成测试数据的代码

COUNT = 1000 * 200

# key is string
key_str = {}
for i in range(COUNT):
    key_str[random_string(random.randint(2, 15))] = True

# key is int
key_int = {}
for i in range(COUNT):
    key_int[random.randint(0, 1 << 32)] = True