为什么 Python 处理排序列表比未排序列表花费更多的时间

Question

示例：

import cProfile, random, copy
def foo(lIn): return [i*i for i in lIn]
lIn = [random.random() for i in range(1000000)]
lIn1 = copy.copy(lIn)
lIn2 = sorted(lIn1)
cProfile.run('foo(lIn)')
cProfile.run('foo(lIn2)')

结果：

0.075 秒内调用 3 次函数

排序方式：标准名称

   ncalls tottime percall cumtime percall 文件名：lineno(function(        1    0.005    0.005    0.075    0.075 :1()        1 0.070 0.070 0.070 0.070 test.py:716(foo(        1 0.000 0.000 0.000 0.000 {方法"禁用"_lsprof。探查器的对象}

0.143 秒内调用 3 次函数

排序方式：标准名称

   ncalls tottime percall cumtime percall 文件名：lineno(function(        1    0.006    0.006    0.143    0.143 :1()        1 0.137 0.137 0.137 0.137 test.py:716(foo(        1 0.000 0.000 0.000 0.000 {方法"禁用"_lsprof。探查器的对象}

Answer 1

还不是真正的答案，但评论边际对于这个来说有点太小了。

由于random.shuffle()会产生相同的结果，我决定实现自己的shuffle函数并改变随机播放的次数。(在下面的示例中，它是要xrange、300000 的参数。

def my_shuffle(array):
    for _ in xrange(300000):
        rand1 = random.randint(0, 999999)
        rand2 = random.randint(0, 999999)
        array[rand1], array[rand2] = array[rand2], array[rand1]

其他代码几乎未修改：

import cProfile, random, copy
def foo(lIn): return [i*i for i in lIn]
lIn = [random.random()*100000 for i in range(1000000)]
lIn1 = copy.copy(lIn)
my_shuffle(lIn1)
cProfile.run('foo(lIn)')
cProfile.run('foo(lIn1)')

我第二cProfile得到的结果取决于我洗牌的次数：

10000 0.062100000 0.082200000 0.099400000 0.122800000 0.1378000000 0.14110000000 0.141100000000 0.248

看起来你把数组弄得越乱，操作所需的时间就越长，直到某个点。(我不知道最后的结果。花了很长时间，我在后台做了一些轻微的其他事情，真的不想重试。