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

Bubble sort - ужасный алгоритм сортировки. Это вполне возможно, причина. Если скорость необходима, я бы попробовал другой алгоритм, такой как быстрая сортировка или сортировка слиянием.

Answer 2

Это не совсем пузырьковая сортировка ... если бы я не сделал тривиальную ошибку, это было бы ближе к пузырьковой сортировке:

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

Обратите внимание, что вся идея заключается в том, что «пузырь» перемещается вдоль массива, меняя соседние значения до тех пор, пока он не перемещается по списку, и при этом ничего не меняется. Можно сделать несколько оптимизаций (например, уменьшить размер внутреннего цикла), но их обычно стоит беспокоить только тогда, когда вы «ориентированы на домашнюю работу».

Редактировать: Фиксированная длина () -> len ()

Answer 3

Bubble sort может быть ужасный и медленный и т. Д., Но вы бы предпочли использовать алгоритм 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 4

Что вы подразумеваете под numy решением? У 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 5

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

Я думаю, что в целом Python немного быстрее, чем Ruby, но не совсем рядом с Java / C / C ++ / C #. Java находится в 2х раз от С, но все интерпретируемые языки были примерно в 100 раз медленнее.

Вы можете использовать Google "Programming Language Game" для МНОГО сравнений приложений / языков / и т. Д. Проверьте 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

Не то, чтобы это дополнение имело какое-либо отношение к вопросу, но святая корова - встроенная имплементация, БЫСТРАЯ. Я думаю, что генерация заняла больше времени, чем сортировка (угадайте, что имеет смысл с вызовами Random и выделением памяти.)

Пришлось войти в CLI и -Xmx1000M, чтобы запустить последний из них.

Answer 6

Bubble sort позволяет 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 7

Я думаю, что вы в основном тратите свое время, используя пузырь на таком большом наборе данных. Есть 3 причины, почему это медленно:

1) Python медленный 2) Пузырьковая сортировка медленная 3) Перечисленная сортировка пузырьков закодирована неправильно / неэффективно.

Независимо от того, как оно закодировано, оно будет O (N ^ 2). Почему бы не использовать сортировку слиянием / деревом ... или если вы хотите попробовать быструю сортировку (также в худшем случае O (N ^ 2)), это может быть быстрее для вашего конкретного набора данных. Я считаю, что быстрая сортировка выполняется эмпирически быстрее, если в данных уже много упорядочений.

Answer 8

Bubblesort в целом плохо масштабируется для большинства возможных входных данных, так как количество элементов во входных данных увеличивается. (Т.е. это O (N ^ 2).)

По мере роста N, учитывая произвольный входной массив размера N, вы значительно реже получаете массив, который сортируется быстро с пузырьковой сортировкой (например, почти отсортированные массивы). У вас гораздо больше шансов получить массив, который занимает много времени для сортировки.

Однако, настоящий кикер здесь заключается в том, что код, который вы разместили, не является пузырьковой сортировкой. Традиционно, пузырьковая сортировка прекращается досрочно, если не было выполнено никаких перестановок, а также не будет пытаться поменять местами уже отсортированные значения. (После P числа проходов последние элементы P будут в правильном порядке, поэтому вам не нужно их обрабатывать.) Фактический отправленный код всегда будет проверять каждую пару в массиве, поэтому он всегда будет запускать внутренний цикл N ^ 2 раза. Для 100000 элементов это 10000000000 итераций.

Answer 9

Например, вы делаете слишком много циклов. Ваш внутренний цикл должен идти от i + 1 до конца списка, а не от 0. Во-вторых, как отмечалось другими, пузырьковая сортировка имеет сложность O (N ^ 2), поэтому для 100000 элементов вы выполняете цикл 10 000 000 000 раз. Это усугубляется тем фактом, что циклы являются одной из областей, где интерпретируемые языки имеют худшую производительность. Все это сводится к невероятно плохой производительности. Вот почему любые вычисления, требующие такого жесткого цикла, обычно пишутся на C / C ++ и переносятся для использования такими языками, как Python.

Answer 10

Вот некоторый код, который я собрал, чтобы сравнить базовую пузырьковую сортировку с более упрощенной версией (базовая и модифицированная) - модифицированная примерно в 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'