如何在Python中高效地对逆向排序的列表进行二分查找?

huangapple go评论82阅读模式
英文:

How to efficiently do binary search on reverse sorted list in Python?

问题

I want to do binary search on reverse sorted lists in Python. The list is appended in reverse order, and it has to be like this or else my code will break.

I need the code to be as fast as possible, assume the list is huge. I know Python code is slow so the code has to be compiled. And I know the bisect module in the standard library imports precompiled _bisect module if found, _bisect is implemented in C which is very fast.

However it doesn't work on reverse sorted lists, I tried key = lambda x: -x and it didn't work:

In [51]: l = range(50, 0, -5)

In [52]: from bisect import bisect

In [53]: bisect(l, 18, key=lambda x: -x)
Out[53]: 10

I copied code from the file from the installation and modified it:

def bisect_right(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x < a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

Change x < a[mid] to x > a[mid] will make it work on reverse sorted lists.

def reverse_bisect(a, x):
    lo, hi = 0, len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

The uncompiled code is much slower than precompiled code, as expected. Also note I cannot compare the performance of reverse_bisect against _bisect.bisect because the latter doesn't work properly in this case.

In [55]: %timeit bisect(range(0, 10**7, 10), 4096)
2.91 µs ± 97.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

In [56]: %timeit bisect_right(range(0, 10**7, 10), 4096)
5.22 µs ± 87.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

So I tried to compile the functions using numba.jit, I added @numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False) to the line before bisect_right, producing bisect_right_nb, but bisect_right_nb gives me a warning and is SIX ORDERS OF MAGNITUDE SLOWER:

In [59]: @numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)
    ...: def bisect_right_nb(a: list, x: int):
    ...:     lo, hi = 0, len(a)
    ...:     while lo < hi:
    ...:         mid = (lo + hi) // 2
    ...:         if x < a[mid]:
    ...:             hi = mid
    ...:         else:
    ...:             lo = mid + 1
    ...:     return lo

In [60]: l = list(range(0, 10**7, 10))

In [61]: %timeit bisect_right_nb(l, 4096)
C:\Python310\lib\site-packages\numba\core\ir_utils.py:2149: NumbaPendingDeprecationWarning:
Encountered the use of a type that is scheduled for deprecation: type 'reflected list' found for argument 'a' of function 'bisect_right_nb'.

For more information visit https://numba.readthedocs.io/en/stable/reference/deprecation.html#deprecation-of-reflection-for-list-and-set-types

File "<ipython-input-59-23a3cb61146c>", line 2:
@numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)
def bisect_right_nb(a: list, x: int):
^

  warnings.warn(NumbaPendingDeprecationWarning(msg, loc=loc))
1.66 s ± 11.2 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

In [62]: 1.66*10**6/5.22
Out[62]: 318007.66283524904

Just how can I improve the performance of reverse_bisect_right?

And no, I have read this answer, I am not trying to insert the element into the list, I am trying to get rid of all elements smaller than it.

(And my network connection is unstable, my ISP is disrupting my VPN connection, so my update took so long.)

英文:

I want to do binary search on reverse sorted lists in Python. The list is appended in reverse order, and it has to be like this or else my code will break.

I need the code to be as fast as possible, assume the list is huge. I know Python code is slow so the code has to be compiled. And I know the bisect module in the standard library imports precompiled _bisect module if found, _bisect is implemented in C which is very fast.

However it doesn't work on reverse sorted lists, I tried key = lambda x: -x and it didn't work:

In [51]: l = range(50, 0, -5)

In [52]: from bisect import bisect

In [53]: bisect(l, 18, key=lambda x: -x)
Out[53]: 10

I copied code from the file from the installation and modified it:

def bisect_right(a, x):
    lo, hi = 0, len(a)
    while lo &lt; hi:
        mid = (lo + hi) // 2
        if x &lt; a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

Change x &lt; a[mid] to x &gt; a[mid] will make it work on reverse sorted lists.

def reverse_bisect(a, x):
    lo, hi = 0, len(a)
    while lo &lt; hi:
        mid = (lo + hi) // 2
        if x &gt; a[mid]:
            hi = mid
        else:
            lo = mid + 1
    return lo

The uncompiled code is much slower than precompiled code, as expected. Also note I cannot compare the performance of reverse_bisect against _bisect.bisect because the latter doesn't work properly in this case.

In [55]: %timeit bisect(range(0, 10**7, 10), 4096)
2.91 &#181;s &#177; 97.3 ns per loop (mean &#177; std. dev. of 7 runs, 100,000 loops each)

In [56]: %timeit bisect_right(range(0, 10**7, 10), 4096)
5.22 &#181;s &#177; 87.9 ns per loop (mean &#177; std. dev. of 7 runs, 100,000 loops each)

So I tried to compile the functions using numba.jit, I added @numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False) to the line before bisect_right, producing bisect_right_nb, but bisect_right_nb gives me a warning and is SIX ORDERS OF MAGNITUDE SLOWER:

In [59]: @numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)
    ...: def bisect_right_nb(a: list, x: int):
    ...:     lo, hi = 0, len(a)
    ...:     while lo &lt; hi:
    ...:         mid = (lo + hi) // 2
    ...:         if x &lt; a[mid]:
    ...:             hi = mid
    ...:         else:
    ...:             lo = mid + 1
    ...:     return lo

In [60]: l = list(range(0, 10**7, 10))

In [61]: %timeit bisect_right_nb(l, 4096)
C:\Python310\lib\site-packages\numba\core\ir_utils.py:2149: NumbaPendingDeprecationWarning:
Encountered the use of a type that is scheduled for deprecation: type &#39;reflected list&#39; found for argument &#39;a&#39; of function &#39;bisect_right_nb&#39;.

For more information visit https://numba.readthedocs.io/en/stable/reference/deprecation.html#deprecation-of-reflection-for-list-and-set-types

File &quot;&lt;ipython-input-59-23a3cb61146c&gt;&quot;, line 2:
@numba.jit(nopython=True, fastmath=True, cache=True, forceobj=False)
def bisect_right_nb(a: list, x: int):
^

  warnings.warn(NumbaPendingDeprecationWarning(msg, loc=loc))
1.66 s &#177; 11.2 ms per loop (mean &#177; std. dev. of 7 runs, 1 loop each)

In [62]: 1.66*10**6/5.22
Out[62]: 318007.66283524904

Just how can I improve the performance of reverse_bisect_right?


And no, I have read this answer, I am not trying to insert the element into the list, I am trying to get rid of all elements smaller than it.

(And my network connection is unstable, my ISP is disrupting my VPN connection, so my update took so long.)

答案1

得分: 2

不要忽略警告

遇到了计划废弃的类型的使用:在函数'bisect_right_nb'的参数'a'中找到了类型'reflected list'。

如果我们解决这个问题并使用'TypedList',那么我们可以获得很好的速度提升:

l = nb.typed.List(list(range(0, 10**7, 10)))
%timeit bisect_right_nb(l, 4096)
1.14 微秒 ± 1.21 纳秒每次循环均值 ± 标准差7 次运行1,000,000 次循环每次

与之相比:

l = list(range(0, 10**7, 10))
%timeit bisect_right_nb(l, 4096)
753 毫秒 ± 38.6 毫秒每次循环均值 ± 标准差7 次运行1 次循环每次
英文:

Don't ignore warnings

Encountered the use of a type that is scheduled for deprecation: type &#39;reflected list&#39; found for argument &#39;a&#39; of function &#39;bisect_right_nb&#39;.

If we adress that and use a TypedList, then we get a nice speedup:

l = nb.typed.List(list(range(0, 10**7, 10)))
%timeit bisect_right_nb(l, 4096)
1.14 &#181;s &#177; 1.21 ns per loop (mean &#177; std. dev. of 7 runs, 1,000,000 loops each)

compared to

l = list(range(0, 10**7, 10))
%timeit bisect_right_nb(l, 4096)
753 ms &#177; 38.6 ms per loop (mean &#177; std. dev. of 7 runs, 1 loop each)

huangapple
  • 本文由 发表于 2023年7月24日 15:06:09
  • 转载请务必保留本文链接:https://go.coder-hub.com/76752114.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定