4

实际上，这是一个来自编程珍珠的有趣话题，使用有效的算法在有限的内存中对 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 大小为：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，sort 函数仍然比 vec_sort 快。有什么方法可以加速 vec_sort 功能？

4

2 回答 2

3

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

这是我使用的功能：

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

附带说明一下，即使针对 Python，BitVector 也没有特别优化。在我找到 bitarray 之前，我对模块做了一些不同的调整，并使用我的模块进行了调整，对于这种大小的数组，vec_sort 的时间减少了一秒钟。不过，我还没有提交我的更改，因为 bitarray 的速度要快得多。

于 2010-06-07T18:33:16.043 回答
1

我的 Python 不是最好的，但看起来您的代码中存在错误：

bv = BitVector( size = len(input_li) )

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

此外，我认为 Python 的排序功能是用 C 实现的，并且不会产生纯粹用 Python 实现的排序的开销。然而，这可能不会导致 O(nlogn) 算法比 O(n) 算法运行得更快。

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

于 2010-06-07T17:38:46.333 回答