1

所以我使用 insort from bisect 将字符串插入到排序列表中。如果我使用内置的，它会更快。**更快我的意思是，平均快两倍（1 毫秒对 2 毫秒在 10,000 字列表上）。我在比我下面的列表更大的列表上运行了 unix cmd：

time script.py < wordList.txt

我认为它与C有关，但我不明白如何或为什么。我想让我的速度一样快，但不使用内置的。

这里直接来自 bisect 源代码：

def insort_left(a, x, lo=0, hi=None):
"""Insert item x in list a, and keep it sorted assuming a is sorted.

If x is already in a, insert it to the left of the leftmost x.

Optional args lo (default 0) and hi (default len(a)) bound the
slice of a to be searched.
"""

if lo < 0:
    raise ValueError('lo must be non-negative')
if hi is None:
    hi = len(a)
while lo < hi:
    mid = (lo+hi)//2
    if a[mid] < x: lo = mid+1
    else: hi = mid
a.insert(lo, x)

平分源代码

这是我认为使它与众不同的部分：

# Overwrite above definitions with a fast C implementation
try:
    from _bisect import *
except ImportError:
    pass

这是输入列表：

#wordlist = ["hello", "jupiter", "albacore", "shrimp", "axe", "china", "lance", "peter", "sam", "uncle", "jeniffer", "alex", "fer", "joseph"]

一些使其工作的代码：

sorted_list = []
for line in wordlist:
    insort_left(sorted_list, line)
print(sorted_list)

所以我关心的是在不使用模块的情况下在 python 中实现基于 C 的排序。我怎样才能做到这一点？

4

1 回答 1

2

在这种情况下，在 VM 上执行的 Python 永远不会像本机代码那样快。

原因是Python VM 只需要做更多的工作来执行 Python 代码。C 代码已经编译并直接执行。虽然 C 扩展代码仍然需要访问 Python VM/运行时，但它还有一个额外的好处，即它可以直接通过公开的C API执行某些操作。有一个RPython项目可以消除Python 代码由于键入而产生的一些额外的运行时执行开销，但它有限制（没有双关语）。

与其试图让 Python 代码比 C“更快”（这对于相同的算法不会发生），不如让 Python 代码比 C 更“聪明”。

在这种情况下，所使用的算法的复杂性很差，~O(n^2)因为它是有效的嵌套循环 - 一个循环用于读取一行，一个循环用于嵌套insort调用（至少用于插入）。这种复杂性可以并且很可能应该被改进，~O(n lg n)并且它将在n高于某些（相对较小的）值的性能上产生差异。

假设这lines是一个包含文件中所有行的列表，然后考虑以下方法。不要在循环中重新运行这些排序建议！

  1. lines.sort()- 内置list.sort，是一种很好的混合排序，并且比上面重复调用的使用有更好的界限insort。这可能是作弊，因为它仍然使用 Python 提供的“本机 C”实现。在任何情况下，这绝对会破坏insort超过几 [打] 行的实现。

  2. largeSort(lines)-合并排序或梳排序largeSort的“纯 Python”实现在哪里。对于足够大的（跨未排序的数据），这将比C 代码更快。由于执行 Python 代码会带来额外的持续性能开销，因此需要进行测试以找出它的哪个值开始占主导地位。ninsortn

  3. smallSort(lines)- smallSort“纯 Python”插入排序实现在哪里。这对于非常小的列表可能更好，并且可以像insort方法一样在线/流式执行。需要进行性能测试，但在这种特殊情况下，这可能比（“纯 Python”）insort 更快。

在任何情况下，精确的常数因子开销和被排序的数据集都是相关的。我建议查看（即绘制）几种方法的性能和包括最坏情况在内的预期数据。即使是诸如预拆分数据之类的东西也可能（相对）使一种方法优于另一种方法或产生误导/非理想收益。另一个可能的考虑是整个 Python 程序的计时（“基准”）可能由甚至与所采用的排序机制无关的开销支配。

于 2013-09-03T23:59:01.037 回答