Python瓶颈argpartsort性能

Question

有没有理由(考虑到我没有搞砸某事)为什么在对给定数组中的前n = 1000个元素进行排序时,bottleneck.argpartsort的性能最佳？

我创建了以下脚本:

d = numpy.random.rand(300000)
l = []
for i in range(5):
    to = time()
    ind = argpartsort(-d, pow(10,i))
    tf = time()
    l.append((pow(10,i), tf - to))

结果导致:

 [(1, 0.008157968521118164),
 (10, 0.006367921829223633),
 (100, 0.006164073944091797),
 (1000, 0.002994060516357422),
 (10000, 0.004293203353881836)]

绘制结果给出:

我认为较少的值argpartsort必须追踪它应该更快,但它不是我所观察到的.我在某个地方搞砸了还是预期的？

提前致谢!

Answer 1

你只看这里的5个步骤.以下是执行500步时的外观:

我相信这种波动来自Hoare的快速选择(枢轴选择是问题 - 它可能非常好但可能非常糟糕,非常随机).在quicksort中使用了类似的想法,让我们来看看:

d = numpy.random.rand(3000)

def test(n):
    ld = d[:n]
    s = time.time()
    ld.sort()
    e = time.time()
    return e-t

这段代码表明,为了增加i排序所花费的时间不应该下降(因为我们只采用相同数组的更大切片,所以如果我们可以更快地排序更大的切片,那么我们应该至少以较快的速度对较小切片进行排序).这是结果:

正如你所看到的,我们也有波动(我不是在谈论大跳跃,这可能是由于我的机器所做的其他事情,但我在谈论它们之间的这种小跳跃).问题在于算法本身.它的平均速度非常快.

最后请注意,您的机器在此期间所做的一切也会影响测试,因此很难给出完整的诊断.