Почему моя сортировка пузырьков в 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

Прежде всего, для целей этого ответа я предполагаю - поскольку вы сами заявляете об этом - что вы делаете это только для сравнения различных языков. Так что я не буду вдаваться в «пузырьковую сортировку - это просто медленная» территория. На самом деле вопрос в том, почему в Python все намного медленнее.

Ответ заключается в том, что Python по своей природе намного медленнее, чем C ++ или даже Java. Вы не видите его в типичном приложении, управляемом событиями или связанным с вводом / выводом, так как там большую часть времени тратится либо на бездействие, ожидая ввода, либо ожидая завершения вызовов ввода / вывода. Однако в вашем случае алгоритм полностью связан с процессором, и, таким образом, вы напрямую измеряете производительность интерпретатора байт-кода Python. Что, по некоторым оценкам, в 20-30 раз медленнее, чем выполнение соответствующего нативного кода, что происходит с C ++ и Java.

В общем, всякий раз, когда вы пишете длительный цикл с привязкой к процессору в Python, вы должны ожидать такой производительности. Единственный способ исправить это - переместить весь цикл в C. Перемещение только тела (например, с помощью NumPy) не очень вам поможет, поскольку итерация самого цикла все равно будет выполняться интерпретатором Python. 1007 *

Answer 2

Потому что он собирается выполнить сравнение и, возможно, обмен 100 000 x 100 000 раз. Если компьютер достаточно быстр для выполнения самого внутреннего оператора 1 000 000 раз в секунду, это все равно составляет 167 минут, что немного меньше 3 часов.

Кстати, почему на SO так много таких глупых вопросов? Разве невозможность сделать простую алгебру обязательным условием для программирования? ; -)

Answer 3

Если вы заинтересованы в создании собственной сортировки, вы можете изменить сортировку по пузырькам на сортировку с помощью всего лишь нескольких строк кода. Расческа почти так же хороша, как и лучшие. Конечно, создание собственного вида лучше всего оставить в качестве учебного упражнения.

Сортировка расчески улучшает пузырьковую сортировку, и соперники в скорости сложнее алгоритмы типа быстрой сортировки.

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

Answer 4

Это не похоже на пузырьковую сортировку, и если это так, то это очень неэффективная реализация.

Answer 5

Вы можете сделать

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 6

Я забыл добавить, что если у вас есть представление о размере набора данных и распределении ключей, вы можете использовать радикальную сортировку, которая будет O (N). Чтобы получить представление о радикальной сортировке, рассмотрим случай, когда вы сортируете, скажем, числа, более или менее распределенные между 0, 100 000. Затем вы просто создаете что-то похожее на хеш-таблицу, скажем, массив из 100 000 списков, и добавляете каждое число в корзину. Вот реализация, которую я написал за несколько минут, которая генерирует некоторые случайные данные, сортирует их и распечатывает случайный сегмент. Время выполнения для массива из 100 000 целых чисел составляет менее 1 с.

Опция Строгое Включено Опция Явная Вкл.

Модуль Модуль1

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

Конечный модуль Время началось = 15.06.2009 16:04:08 Время закончено = 15.06.2009 16:04:08 Количество операций = 100000 21429 21430 21430 21431 21431 21432 21433 21435 21435 21435 21436 21437 21437 21439 21441 ...

Answer 7

Если вам нужно написать свой код, используйте сортировку вставкой. Примерно столько же кода, но в несколько раз быстрее.

Answer 8

Как и в других постах, пузырьковая сортировка ужасна. Этого в значительной степени следует избегать любой ценой из-за плохой проформы, как вы испытываете.
К счастью для вас, существует множество других алгоритмов сортировки, http://en.wikipedia.org/wiki/Sorting_algorithm, для примеров.

По моему опыту в школе, быстрая сортировка и слияние - это два других основных алгоритма сортировки, введенные с пузырьковой сортировкой или вскоре после нее. Поэтому я бы порекомендовал вам ознакомиться с ними для изучения более эффективных способов сортировки.