Python3 中 sorted() 和 heapq 函数的性能

大佬教程收集整理的这篇文章主要介绍了Python3 中 sorted() 和 heapq 函数的性能，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

如何解决Python3 中 sorted() 和 heapq 函数的性能？

开发过程中遇到Python3 中 sorted() 和 heapq 函数的性能的问题如何解决？下面主要结合日常开发的经验，给出你关于Python3 中 sorted() 和 heapq 函数的性能的解决方法建议，希望对你解决Python3 中 sorted() 和 heapq 函数的性能有所启发或帮助；

我想使用 python3 以最快的方式实现以下过程：给定一个 N 随机整数列表，我需要返回 K 最小的整数（并且我不需要返回的整数排序）。 我以三种不同的方式实现了它（如下面的代码所示）。

• test_sorted() 函数使用内置的 sorted() 函数对整个整数列表进行排序，然后获取前 K 元素的切片。此操作的成本本质上应该是运行 sorted() 函数的成本，其时间复杂度为 O(N log(N))。

• test_heap() 函数使用堆仅存储最低的 K 元素并返回它们。在堆上插入一个元素的时间复杂度为 O(log(N))，理论上我们需要在堆中推送一个项目的时间为 N。但是，在第一个 K 插入之后，我们将从堆中推送和弹出，我希望如果传入的元素比堆中的任何元素都大，则不会发生插入，时间复杂度应该介于 {{ 1}} 和 O(K log(N))（取决于输入列表的实际顺序）。无论如何，即使我的假设不正确，最坏的复杂度也应该是 O(N log(N))（像往常一样，我认为我们需要的所有比较的成本可以忽略不计）。

• O(N log(N)) 函数使用 test_nsmallest() 模块中的 nsmallest() 函数。我对这种方法没有期望，因为在官方 python 文档中我只发现

  对于较大的值，使用 sorted() 函数效率更高。 我决定试一试。

heapq

我的（旧）2011 年末 MACBook Pro 上的输出如下所示。

# test.py

from heapq import heappush,heappushpop,nsmallest
from random import randint
from timeit import timeit

N,K = 1000,50
RANDOM_INTS = [randint(1,100) for _ in range(N)]

def test_sorted():
    return sorted(RANDOM_INTS)[:K]

def test_heap():
    heap = []
    for val in RANDOM_INTS:
        if len(heap) < K:
            heappush(heap,-val)
        else:
            heappushpop(heap,-val)
    return [-val for val in heap]

def test_nsmallest():
    return nsmallest(K,RANDOM_INTS)


def main():
    sorted_result = timeit("test_sorted()",globals=globals(),number=100_000)
    print(f"test_sorted took: {sorted_result}")

    heap_result = timeit("test_heap()",number=100_000)
    print(f"test_heap took: {heap_result}")

    nsmallest_result = timeit("test_nsmallest()",number=100_000)
    print(f"test_nsmallest took: {nsmallest_result}")

    r1,r2,r3 = test_sorted(),test_heap(),test_nsmallest()
    assert len(r1) == len(r2) == len(r3)
    assert set(r1) == set(r2) == set(r3)


if __name__ == '__main__':
    main()

使用 $ python --version Python 3.9.2 $ python test.py test_sorted took: 8.389572635999999 test_heap took: 18.586762750000002 test_nsmallest took: 13.772040639000004 的最简单的解决方案是迄今为止最好的，谁能详细说明为什么结果与我的期望不符（即 sorted() 函数应该至少快一点）？我错过了什么？

如果我用 pypy 运行相同的代码，结果是相反的。

test_heap()

这更接近我的期望。

假设我对 python 内部结构一无所知，并且我对为什么 pypy 比 python 快只有一个非常粗略的理解，任何人都可以详细说明这些结果并添加一些关于正在发生的事情的信息，以便让我正确预见未来类似情况的最佳选择？

另外，如果您对运行速度比上述更快的其他实现有任何建议，请随时分享！

更新：

如果我们需要根据一些不是项目本身的值的标准对输入列表进行排序怎么办（正如我在实际用例中实际需要的那样；以上只是一个简化）？那么，在这种情况下，结果更令人惊讶：

$ pypy --version
Python 3.7.10 (51efa818fd9b,Apr 04 2021,12:03:51)
[PyPy 7.3.4 with GCC Apple LLVM 12.0.0 (clang-1200.0.32.29)]

$ pypy test.py 
test_sorted took: 7.1336525249998886
test_heap took: 3.1177806880004937
test_nsmallest took: 7.5453417899998385

输出：

# test2.py

from heapq import heappush,nsmallest
from random import randint
from timeit import timeit


N,100) for _ in range(N)]


def test_sorted():
    return sorted(RANDOM_INTS,key=lambda x: X)[:K]

def test_heap():
    heap = []
    for val in RANDOM_INTS:
        if len(heap) < K:
            heappush(heap,(-val,val))
        else:
            heappushpop(heap,val))
    return [val for _,val in heap]

def test_nsmallest():
    return nsmallest(K,RANDOM_INTS,key=lambda x: X)


def main():
    sorted_result = timeit("test_sorted()",test_nsmallest()
    assert len(r1) == len(r2) == len(r3)
    assert set(r1) == set(r2) == set(r3)


if __name__ == '__main__':
    main()

这至少告诉我两件事：

• 使用外部键进行排序非常昂贵，无论是使用 $ python test2.py test_sorted took: 18.740868524 test_heap took: 27.694126547999996 test_nsmallest took: 25.414596833000004 $ pypy test2.py test_sorted took: 65.88409741500072 test_heap took: 3.9442632220016094 test_nsmallest took: 19.981832798999676 kwarg 提供 lambda 函数还是需要构建元组 key 以获得所需的排序堆。

• 在 pypy 中使用 lambdas 似乎非常昂贵，但我不知道为什么......也许 pypy 无法优化它们并且这与它执行的其他优化不兼容？？？>

解决方法

大佬总结

以上是大佬教程为你收集整理的Python3 中 sorted() 和 heapq 函数的性能全部内容，希望文章能够帮你解决Python3 中 sorted() 和 heapq 函数的性能所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。