python - 如何在 python 中实现真正有效的位向量排序

Question

其实这是一个来自编程珍珠的有趣话题，用高效的算法对有限内存中的 10 位电话号码进行排序。你可以找到整个故事here

我感兴趣的是在 python 中实现的速度有多快。我用模块 bitvector 做了一个简单的实现。代码如下:

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，结果如下:

---

• 测试数据大小为:1000
• 排序功能 需要 0.000274896621704

• vec_sort函数取0.00383687019348

• test_data 大小为:10000

• 排序函数取 0.00380706787109

• vec_sort函数取0.0371489524841

• test_data 大小为:100000

• 排序函数需要 0.05205​​60741425

• vec_sort函数取0.374383926392

• test_data 大小为: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 的时间减少了一秒以上。我还没有提交我的更改，因为 bitarray 实在是太快了。