如何在Python中实现高效的位图排序

4 投票

2 回答

1352 浏览

提问于 2025-04-15 23:40

其实这是一个很有趣的话题，来自《编程珠玑》这本书，讨论的是如何在有限的内存中用高效的算法对10位的电话号码进行排序。你可以在这里找到完整的故事。

我感兴趣的是在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
sort函数耗时：0.000274896621704秒
vec_sort函数耗时：0.00383687019348秒
测试数据大小：10000
sort函数耗时：0.00380706787109秒
vec_sort函数耗时：0.0371489524841秒
测试数据大小：100000
sort函数耗时：0.0520560741425秒
vec_sort函数耗时：0.374383926392秒
测试数据大小：1000000
sort函数耗时：0.867373943329秒
vec_sort函数耗时：3.80475401878秒
测试数据大小：10000000
sort函数耗时：12.9204008579秒
vec_sort函数耗时：38.8053860664秒

让我失望的是，即使测试数据大小达到100,000,000，sort函数的速度仍然比vec_sort快。有没有什么办法可以加速vec_sort函数呢？

数据结构编程实践排序算法测试数据性能测试内存优化算法效率位图排序

2 个回答

我的Python水平不太高，但看起来你的代码里有个错误：

bv = BitVector( size = len(input_li) )

你的位向量大小和输入数组的大小是一样的。其实你应该把位向量的大小设为你的数据范围，也就是10的10次方。至于Python的位向量如果超出了范围会怎么处理，我不太清楚，但如果它会自动调整大小，那你的程序可能会变得很慢。

另外，我想Python的排序函数是用C语言实现的，所以它的效率应该比纯Python写的排序要高。不过，这也不一定会让O(nlogn)的算法比O(n)的算法快很多。

补充一下：这个排序方法只适合处理大数据集。你的算法运行时间是O(n + 10^10)（根据你的测试，我想你应该知道这一点），对于小数据来说，这个时间会比O(nlogn)要差。

回答于 2025-04-15 由 Python大师

分享举报

正如Niki所说，你在比较一个非常快的C语言程序和一个Python程序。使用psyco可以让我稍微加快速度，但如果你想大幅提升速度，可以使用一个用C语言写的位向量模块。我使用了bitarray，然后用位排序的方法，处理大约250,000个元素的数组时，速度超过了Python自带的排序。

这是我使用的函数：

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实在是太快了。

回答于 2025-04-15 由 Python大师

分享举报

如何在Python中实现高效的位图排序

2 个回答

撰写回答