为什么我在日期时间列表上使用numpy.searchsorted而不是bisect.bisect_left不能获得更好的性能？

Question

我读过numpy的搜索排序比python的二分搜索更快。需要做更多的准备工作。

我使用的是numpy.array of numpy.datetime64对象。这个性能测试与我的用例相似--为单个目标搜索大约1000次的日期列表。

from bisect import bisect_left
from datetime import datetime, timedelta
from random import randrange
from timeit import timeit

import numpy as np


def randdate():
    r = randrange(int((datetime.max - datetime.min).total_seconds()))
    return datetime.min + timedelta(seconds=r)


data = sorted(randdate() for _ in xrange(1000))
np_data = np.array(data, dtype=np.datetime64)

x = randdate()
np_x = np.datetime64(x)


def python_bisect():
    result = bisect_left(data, x)
    return result


def numpy_searchsorted():
    result = np_data.searchsorted(np_x)
    return result


time1 = timeit(python_bisect, number=1000)
time2 = timeit(numpy_searchsorted, number=1000)
print time1
print time2
print "bisect/searchsorted: {}".format(time1 / time2)

不过，我看到的是搜索排序速度的两倍。

Answer 1

与基准有关的一些问题：

1. 应该对输入列表/数组进行排序。
2. Python for循环中的单个操作对于NumPy来说并不是一个很好的性能度量：np.searchsorted的第二个参数支持数组。使用这个特性。
3. 使用更多的输入，例如10**6而不是20000。
4. 使用timeit进行可靠的性能测量。

下面是一个演示：

N = 10**6

data = sorted([randdate() for _ in range(N)])
np_data = np.sort(np.array(data, dtype=np.datetime64).astype(np.int64))

def python_bisect():
    return [bisect(data, data[x]) for x in range(N)]

def numpy_searchsorted():
    return np.searchsorted(np_data, np_data, side='right')

%timeit python_bisect()       # 1.3 s per loop
%timeit numpy_searchsorted()  # 60 ms per loop