Почему я не получаю более высокую производительность с numpy.searchsorted over bisect.bisect_left в списке datetime?

Question

Я читал, что сортировка поиска numpy - это более быстрый бинарный поиск, чем биссектон Python.Для numpy требуется дополнительная подготовка.

Я использую массив numpy.ar для объектов 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. Отдельные операции в цикле for уровня Python не являются хорошей меройпроизводительность для 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