为什么我的 Python 冒泡排序这么慢？

Question

我有以下代码，它使用冒泡排序来反转列表，并且时间性能最差：

for i in xrange(len(l)):
    for j in xrange(len(l)):
        if l[i]>l[j]:
            l[i], l[j] = l[j], l[i]

在某些情况下（当 len(l) = 100000 时），代码花费超过 2 小时才能完成执行，我觉得很奇怪，请纠正我的代码或提出一些建议。 欢迎 numpy 和 numarray 解决方案。

Answer 1

您可以执行

l.reverse()

脚本 ee.py：

l = []
for i in xrange(100000):
    l.append(i)

l.reverse()

lyrae@localhost:~/Desktop$ time python ee.py

real    0m0.047s
user    0m0.044s
sys    0m0.004s

Answer 2

我忘了补充一点，如果您对数据集的大小和键的分布有所了解，那么您可以使用基数排序，其复杂度为 O(N)。 要了解基数排序的概念，请考虑您要对或多或少分布在 0, 100,000 之间的数字进行排序的情况。 然后，您只需创建类似于哈希表的内容，例如包含 100,000 个列表的数组，并将每个数字添加到存储桶中。 这是我在几分钟内编写的一个实现，它生成一些随机数据，对其进行排序，然后打印出随机段。 对于 100,000 个整数的数组，执行时间不到 1 秒。

选项严格开启
模块上显式选项

Module1

Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0

Private Sub generateData()
    ' fill with random numbers between 0 and MAX_SIZE - 1
    For i = 0 To MAX_SIZE - 1
        m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
    Next

End Sub

Private Sub sortData()
    For i As Integer = 0 To MAX_SIZE - 1
        Dim x = m_input(i)
        If m_table(x) Is Nothing Then
            m_table(x) = New List(Of Integer)
        End If
        m_table(x).Add(x)
        ' clearly this is simply going to be MAX_SIZE -1
        m_operations = m_operations + 1
    Next
End Sub

 Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
    If start < 0 Or start > MAX_SIZE - 1 Then
        Throw New Exception("printData - start out of range")
    End If
    If finish < 0 Or finish > MAX_SIZE - 1 Then
        Throw New Exception("printData - finish out of range")
    End If
    For i As Integer = start To finish
        If m_table(i) IsNot Nothing Then
            For Each x In m_table(i)
                Console.WriteLine(x)
            Next
        End If
    Next
End Sub

' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
    m_operations = 0
    generateData()
    Console.WriteLine("Time started = " & Now.ToString())
    sortData()
    Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
    ' print out a random 100 segment from the sorted array
    Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
    printData(start, start + 100)
End Sub

Sub Main()
    test()
    Console.ReadLine()
End Sub

终端模块
开始时间 = 6/15/2009 4:04:08 PM
完成时间 = 6/15/2009 4:04:08 PM 操作次数 = 100000
21429
21430
21430
21431
21431
21432
21433
21435
21435
21435
21436
21437
21437
21439
21441
...

Answer 3

如果您必须自己编写代码，请使用插入排序。 其代码量大致相同，但速度要快几倍。

Answer 4

就像其他帖子所说，冒泡排序是可怕的。 由于性能不佳，就像您所经历的那样，几乎应该不惜一切代价避免它。
幸运的是，还有很多其他排序算法，http://en.wikipedia.org/wiki/Sorting_algorithm ，例如。

根据我在学校的经验，快速排序和合并排序是与冒泡排序一起或不久之后引入的另外两种基本排序算法。 因此，我建议您研究一下这些内容，以学习更有效的排序方法。

Answer 5

首先，出于本回复的目的，我假设 - 因为您自己声明 - 您这样做只是为了对不同的语言进行基准测试。 所以我不会进入“冒泡排序很慢”的领域。 真正的问题是为什么 Python 的速度这么慢。

答案是，Python 本质上比 C++ 甚至 Java 慢得多。 您在典型的事件驱动或 I/O 绑定应用程序中看不到它，因为大多数时间都花在等待输入时空闲或等待 I/O 调用完成。 然而，在您的情况下，算法完全受 CPU 限制，因此您直接测量 Python 字节码解释器的性能。 据估计，这比执行相应的本机代码慢 20-30 倍，C++ 和 Java 都是如此。

一般来说，任何时候你在 Python 中编写一个长时间运行的 CPU 密集循环，你都应该期待这种性能。 解决这个问题的唯一方法是将整个循环移动到C中。仅移动循环体（例如使用NumPy）不会有太大帮助，因为循环迭代本身仍然由Python解释器执行。

Answer 6

因为它将执行比较并可能执行交换 100,000 x 100,000 次。 如果计算机速度足够快，每秒执行最里面的语句 1,000,000 次，那仍然是 167 分钟，比 3 小时略短。

顺便说一句，为什么 SO 上有这么多愚蠢的问题？ 难道不会做简单的代数不是编程的先决条件吗？ ;- ）

Answer 7

对我来说，这看起来不像冒泡排序，如果是的话，它的实现效率非常低。

Answer 8

随着输入中元素数量的增加，冒泡排序通常不能很好地适应大多数可能的输入。 （即，它是 O(N^2)。）

随着 N 的增长，给定大小为 N 的随机输入数组，您不太可能获得使用冒泡排序快速排序的数组（例如，几乎排序的数组）。 您更有可能得到一个需要很长时间才能排序的数组。

然而，这里真正的问题是您发布的代码不是冒泡排序。 传统上，如果没有进行交换，并且不尝试交换已经排序的值，冒泡排序将提前终止。 （经过 P 次之后，最后 P 个项目将按正确的顺序排列，因此您不需要处理它们。）发布的实际代码将始终检查数组中的每一对，因此它将始终运行内部循环N^2 次。 对于 100000 个元素，即 10000000000 次迭代。

Answer 9

如果您有兴趣进行自己的排序，只需几行代码即可将冒泡排序更改为梳状排序。 梳排序几乎与最佳排序一样好。 当然，最好将自己的排序作为学习练习。

梳排序改进了冒泡排序，并且
速度上的竞争对手更加复杂
像快速排序这样的算法。

http://en.wikipedia.org/wiki/Comb_sort

Answer 10

我认为在如此大的数据集上使用 bubble 基本上是浪费时间。 慢的原因有3个：

1）Python慢
2）冒泡排序速度慢
3）列出的冒泡排序编码不正确/效率低下。

无论如何编码，其复杂度都是 O(N^2)。 为什么不使用合并/树排序..或者如果您想尝试快速排序（也是最坏情况 O(N^2)），它对于您的特定数据集可能会更快。 我相信，如果数据中已经有很多排序，那么从经验上看，快速排序会更快。

Answer 11

这里我整理了一些代码，将基本冒泡排序与更简化的版本进行比较（基本与修改） - 修改后的速度大约快 2-3 倍，仍然是一个慢排序，但更快

from array import *
from random import *
from time import *

def randarray(typecode, numElements, minValue, maxValue):
    a = array(typecode)
    for i in xrange(0, numElements):
        a.append(randint(minValue, maxValue))
    return a

def basesort(l):
    for i in xrange(len(l)):
        for j in xrange(len(l)):
            if l[i]<l[j]:
                l[i], l[j] = l[j], l[i]
    return l

def modifiedsort(l):
    NotComplete = True
    i = 0
    arange = xrange(len(l))
    while NotComplete:
        NotComplete = False
        for j in xrange(len(l) - i):
            if l[i]<l[j]:
                l[i], l[j] = l[j], l[i]
                NotComplete = True
        i += 1

Num = 1000
b = randarray('i', Num, 1, 100000)
m = b[:]

print 'perform base bubble sort'
t = time()
basesort(b)
basetime =  time() - t
print basetime
#print a
print 'complete'

print 'perform modified bubble sort'
t = time()
modifiedsort(m)
modtime =  time() - t
print modtime
#print a
print 'complete'

print 'mod sort is ', basetime / modtime,' fast then base sort'

Answer 12

其一，你循环次数过多。 您的内部循环应该从 i + 1 开始到列表末尾，而不是从 0 开始。其次，正如其他人指出的，冒泡排序具有 O(N^2) 复杂度，因此对于 100000 个元素，您将循环 10,000,000,000 次。 循环是解释型语言性能最差的领域之一，这一事实使情况变得更加复杂。 所有这些加起来导致性能极其糟糕。 这就是为什么任何需要如此紧密循环的计算通常都是用 C/C++ 编写并包装以供 Python 等语言使用。

Answer 13

冒泡排序进行 O(N²) 次比较操作（或迭代）。 对于 N = 100,000，这意味着将有 10,000,000,000 次迭代。 如果这需要 2 小时（称之为 10,000 秒），那么这意味着每秒会进行 1,000,000 次迭代，或者每次迭代 1 微秒。 这速度虽然不算快，但也不算太差。 我挥手并忽略不断的乘法因子。

如果您使用快速排序，那么您将获得 Nlog(N) 次迭代，这意味着大约 1,000,000 次迭代，总共需要 1 秒。 （log₁₀(N) 为 5；为简单起见，我将其四舍五入为 10。）

因此，您刚刚充分证明了为什么冒泡排序不适合大型数据集，并且 100,000 个项目足够大证明这一点。

Answer 14

numpy 解决方案是什么意思？ Numpy 有一些排序工具，对于那些相当小的数组来说是即时的：

import numpy as np
a = np.random.randn(100000)
# Take a few ms on a decent computer
np.sort(a)

有 3 种可用的排序算法，平均都是 Nlog(N)。

Answer 15

我相信您提到过您试图使用它作为比较速度的基准。

我认为一般来说，Python 比 Ruby 快一点，但还没有真正接近 Java/C/C++/C#。 Java 的速度比 C 慢 2 倍以内，但所有解释型语言的速度都慢 100 倍左右。

您可能会在谷歌上搜索“编程语言游戏”以进行大量应用程序/语言/等的比较。 查看 Python JIT 以获得更好的性能。

您还可以将其与 Ruby 进行比较，以查看更公平的测试。

编辑：只是为了好玩（与问题无关）检查这个 -

public class Test {
    public static void main(String[]s) {
        int size=Integer.valueOf(s[0]).intValue();
        Random r=new Random();
        int[] l=new int[size];
        for(int i=0;i<size;i++)
            l[i]=r.nextInt();
        long ms=(new Date()).getTime();
        System.out.println("built");
        if(fast) {
            Arrays.sort(l);
        else {
            int temp;
            for(int i=0;i<size;i++)
                for(int j=0;j<size;j++)
                    if(l[i]>l[j]) {                        
                        temp=l[i];
                        l[j]=l[i];
                        l[j]=temp;                        
                    }
            }
        ms=(new Date()).getTime()-ms;
        System.out.println("done in "+ms/1000);
    }
}

有趣的是：Java 运行时间的顺序是：

Array size  Slow Time   Fast time
 100k         2s          0s
  1M         23s          0s
 10M         39m          2s
100M         NO          23s

并不是说​​这个添加与问题有任何关系，但天哪构建-实施速度很快。 我认为生成比排序花费的时间更长（猜测这对于调用随机和内存分配是有意义的。）

必须进入 CLI 和 -Xmx1000M 才能运行最后一个。

Answer 16

冒泡排序可能可怕和缓慢等，但您宁愿使用 O(N^2) 算法超过 100 个项目，还是 O(1) 需要拨号的算法向上连接？

列出 100 个项目不应花费 2 小时。 我不懂Python，但是当你进行这些作业时，你是否有机会复制整个列表？

这是Python中的冒泡排序（来自Google，因为我很懒）：

def bubbleSort(theList, max):
    for n in range(0,max): #upper limit varies based on size of the list
        temp = 0
        for i in range(1, max): #keep this for bounds purposes
            temp = theList[i]
            if theList[i] < theList[i-1]:
                theList[i] = theList[i-1]
                theList[i-1] = temp

另一个来自维基百科：

def bubblesort(l):
    "Sorts l in place and returns it."
    for passesLeft in range(len(l)-1, 0, -1):
        for index in range(passesLeft):
            if l[index] < l[index + 1]:
               l[index], l[index + 1] = l[index + 1], l[index]
    return l

冒泡排序的顺序是N(N-1)。 这本质上是 N^2，因为对于每个元素，您都需要扫描列表并比较每个元素。

顺便说一下，您可能会发现 C++ 是最快的，然后是 Java，然后是 Python。

Answer 17

这不完全是冒泡排序...除非我犯了一个小错误，否则这更接近于 python 冒泡排序：

swapped = True
while swapped:
  swapped = False
  for i in xrange(len(l)-1):
    if l[i] > l[i+1]:
      l[i],l[i+1] = l[i+1],l[i]
      swapped = True

请注意，整个想法是“冒泡”沿着数组移动，交换相邻值直到它移动浏览列表，没有任何交换。 可以进行一些优化（例如缩小内部循环的大小），但通常只有当您“以家庭作业为导向”时才值得烦恼。

编辑：固定长度() -> 长度（）

Answer 18

冒泡排序是一种糟糕的排序算法。 这很可能就是原因。 如果速度是必要的，我会尝试另一种算法，例如快速排序或合并排序。