python - Numpy `searchsorted` 比我的二进制搜索功能慢得多

Question

我正在试验二进制搜索，当我的版本工作时，我想我会将它的速度与 NumPy 的速度进行比较。我对结果感到相当惊讶，原因有两个。

1. 我知道二分搜索应该增长为log n，我的就是这样，但 NumPy 是线性增长的。
2. 不仅如此，NumPy 的速度也很慢——在开始时，当然在结束时。

我附上了一张结果图。橙色是 NumPy，蓝色是我的。左侧是在列表中找到最后一项所需的时间（以毫秒为单位）（items[-1]），底部显示列表的长度。我还检查了以确保我的代码返回了正确的值，并且确实如此。

如果我不清楚，我的问题基本上是“为什么”两个 #1 和 #2

#binary_search.py
from typing import Iterable
from numba import njit
from numba.typed import List


def _find(items: Iterable[int], to_find: int):
    min = -1
    max = len(items)

    while True:
        split = int((max+min)/2)
        item = items[split]
        if item == to_find:
            return split

        elif max == min:
            print(min, max)
            print(items)
            print(to_find)
            print(split)
            exit()

        elif item > to_find:
            max = split - 1
        elif item < to_find:
            min = split + 1


def findsorted(_items: Iterable[int], to_find: int):
    items = _items
    return _find(items, to_find)

#graph_results.py
import binary_search as bs
import sys
import time
import numpy as np

from matplotlib import pyplot as plt

iterations = int(sys.argv[1])
items = [0, 1]
lx = []
ly = []
nx = []
ny = []

for i in range(2, iterations):
    l_avg_times = []
    n_avg_times = []
    items.append(items[-1] + 1)
    for _ in range(0, 100):
        to_find = items[-1]
        lstart = time.time()
        bs.findsorted(items, to_find)
        lend = time.time()

        nstart = lend
        np.searchsorted(items, to_find)
        nend = time.time()

        ltotal = lend-lstart
        ntotal = nend-nstart
        l_avg_times.append(ltotal)
        n_avg_times.append(ntotal)
    ly.append(
        round(
            sum(l_avg_times)/len(l_avg_times),
            1000
        )*1000
    )
    lx.append(i)
    ny.append(
        round(
            sum(n_avg_times)/len(n_avg_times),
            1000
        )*1000
    )
    nx.append(i)


plt.plot(lx, ly)
plt.plot(nx, ny)
plt.show()

标签： pythonpython-3.xnumpybinary-search