如何在Python中实现真正高效的位向量排序

Question

实际上，这是珍珠编程中的一个有趣的主题，使用有效的算法在有限的内存中对 10 位电话号码进行排序。您可以在此处找到整个故事，

我感兴趣的是速度有多快可以用 python 实现。我已经使用模块位向量完成了一个简单的实现。代码如下：

from BitVector import BitVector
import timeit
import random
import time
import sys

def sort(input_li):
        return sorted(input_li)

def vec_sort(input_li):
        bv = BitVector( size = len(input_li) )
        for i in input_li:
                bv[i] = 1

        res_li = []
        for i in range(len(bv)):
                if bv[i]:
                        res_li.append(i)

        return res_li

if __name__ == "__main__":
        test_data = range(int(sys.argv[1]))
        print 'test_data size is:', sys.argv[1]
        random.shuffle(test_data)

        start = time.time()
        sort(test_data)
        elapsed = (time.time() - start)
        print "sort function takes " + str(elapsed)
        start = time.time()
        vec_sort(test_data)
        elapsed = (time.time() - start)
        print "sort function takes " + str(elapsed)
        start = time.time()
        vec_sort(test_data)
        elapsed = (time.time() - start)
        print "vec_sort function takes " + str(elapsed)

我在我的macbook（2GHz Intel Core 2 Duo 2GB SDRAM）中从数组大小100到10,000,000进行了测试，结果如下：

---

• test_data size is: 1000
• sort function 需要 0.000274896621704

• vec_sort 函数需要 0.00383687019348

• test_data 大小为：10000

• 排序函数需要 0.00380706787109
• < p>vec_sort 函数需要 0.0371489524841

• test_data 大小为：100000

• 排序函数需要 0.05205​​60741425

• vec_sort 函数需要 0.374383926392

• test_数据大小为：1000000

• 排序函数需要 0.867373943329

• vec_sort 函数需要 3.80475401878

• test_data 大小为：10000000

• 排序函数需要 12。 9204008579
• vec_sort函数需要38.8053860664

令我失望的是，即使当 test_data 大小为 100,000,000 时，排序函数仍然比 vec_sort 更快。有什么方法可以加速 vec_sort 函数吗？

Answer 1

正如 Niki 指出的，您正在将非常快速的 C 例程与 Python 例程进行比较。使用 psyco 对我来说会加快一点速度，但是你可以通过使用位向量来加快速度用C编写的模块。我使用了 bitarray 然后位排序方法超越了使用 psyco 对大约 250,000 的数组大小进行内置排序。

这是我使用的函数：

def vec_sort2(input_li):
    bv = bitarray(len(input_li))
    bv.setall(0)
    for i in input_li:
        bv[i] = 1

    return [i for i in xrange(len(bv)) if bv[i]]

另请注意，我使用了列表理解来构造排序列表，这有点帮助。将 psyco 和上述函数与您的函数一起使用，我得到以下结果：

test_data size is: 1000000
sort function takes 1.29699993134
vec_sort function takes 3.5150001049
vec_sort2 function takes 0.953999996185

作为旁注，BitVector 即使对于 Python 也没有特别优化。在找到 bitarray 之前，我对模块做了一些不同的调整，并使用经过调整的模块，对于这种大小的数组，vec_sort 的时间减少了一秒多。不过，我还没有提交对它的更改，因为位数组要快得多。

Answer 2

我的Python不是最好的，但看起来你的代码中有一个错误：

bv = BitVector( size = len(input_li) )

位向量的大小与输入数组的大小相同。您希望位向量是域的大小 - 10^10。我不确定Python的位向量如何处理溢出，但如果它自动调整位向量的大小，那么你就会得到二次行为。

另外，我认为 Python 的排序函数是用 C 实现的，并且不会有纯粹用 Python 实现的排序的开销。然而，这可能不会导致 O(nlogn) 算法的运行速度明显快于 O(n) 算法。

编辑：这种排序也仅适用于大型数据集。您的算法在 O(n + 10^10) 时间内运行（根据您的测试，我假设您知道这一点），对于小输入，这将比 O(nlogn) 更糟糕。