DjangoBB LoFi version

Полная версия: Время выполнения сортировки пузырьком в Питоне

Начало » Python для новичков » Время выполнения сортировки пузырьком в Питоне

hdj

Янв. 8, 2015 14:28:21

Вопросы:
- подправить ошибки;
- время выполнения алгоритма правильно замеряю?
- время операций питона больше, чем у других языков?

import random, datetime
l = []
def createrandom():
    for i in range(1, 2000):
        l.append(random.randint(-9900, 9900))
    #l.append(-99)
    
def sort1():
    #print ('Н: ' + str(l))
    i_maxrange = len(l) - 1
    isWasSort = False
    # Количество циклов
    for o in range(1, len(l)):
        isWasSort = False
        for i in range(0, i_maxrange):
            if (l[i] > l[i+1]):
                temp = l[i]
                l[i] = l[i+1]
                l[i+1] = temp
                isWasSort = True
        #print (str(o) + ')', l)
        i_maxrange -= 1
        if (not isWasSort): break
    #print (str(len(l)) + ' чисел в последовательности, ' + str(o) + ' циклов, ' + str(i + 1) + ' итераций в последнем')
createrandom()
start = datetime.datetime.now()
sort1()
end = datetime.datetime.now()
print(end - start)

На хабре у парня выходит “около 25 мс на размере 2000 элементов”. У меня же около 1 секунды и 300 мс. Хотелось бы знать почему.
http://habrahabr.ru/post/204600/#comment_7058336

andy4

Янв. 8, 2015 16:36:11

Тот парень на Java пишет - конечно у него быстрее.
У меня кстати 0.79 секунды.

vax

Янв. 8, 2015 20:59:14

Ближе к истине замерять скорость с помощью пакета (Тут будет запускаться 1000 раз и время будет взято среднее)

from timeit import timeit
print(timeit(sort1, number=1000))

Круглыес скобки у if-ов можно пропустить.

Время операций больше). У некоторых операций на микросекунды, на других (особенно если много сложений или другой подобной арифметики) - секунды.

createrandom можно заменить на оптимизированный вариант:

randint = random.randint
l = [randint(-9900, 9900) for _ in range(1, 2000)]

GreyZmeem

Янв. 8, 2015 22:02:08

Используйте xrange, вместо range.
Делайте swap, вместо создания дополнительно переменной (SO).

import random
 
def bubble_sort(size):
    l = [random.randint(-9900, 9900) for _ in xrange(size)]
 
    for i in xrange(size):
        is_sorted = True
        for j in xrange(size - i - 1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
                is_sorted = False
        if is_sorted:
            break
 
if __name__ == '__main__':
    from pprint import pprint
    import timeit
    pprint(timeit.repeat(
        'bubble_sort(2000)',
        setup='from __main__ import bubble_sort',
        repeat=10,
        number=1
    ))

[0.36500650941496676,
 0.3652929091354484,
 0.3865986737899916,
 0.3865463367852333,
 0.37194431245773374,
 0.3704558577344521,
 0.4057343911546587,
 0.37223022757631963,
 0.37062861831034377,
 0.36998385548783785]
[Finished in 3.9s]

Без проверок получается еще быстрей:

for i in xrange(size):
        for j in xrange(size - i - 1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]

[0.3443619840473902,
 0.35039188543817334,
 0.37408455673101126,
 0.39416985151070993,
 0.35705249619648094,
 0.3563435236227672,
 0.34699022242984734,
 0.3568962120850503,
 0.34422169179852524,
 0.34576757184647144]
[Finished in 3.7s]

Alen

Янв. 8, 2015 23:08:23

Ну и напоследок скомпилировать всё это:

import random
def bubble_sort(size):
    l = [random.randint(-9900, 9900) for _ in xrange(size)]
    for i in xrange(size):
        for j in xrange(size - i - 1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
bubble_sort(10000)

Python

~ ➭ time python test.py
~ ➭ python test.py  11,45s user 0,02s system 99% cpu 11,475 total

Nuika

~ ➭ nuitka test.py
~ ➭ time ./test.exe
./test.exe  7,67s user 0,02s system 99% cpu 7,695 total

Cython

~ ➭ cython test.py --embed
~ ➭ gcc -g -O2 test.c  `python-config --includes --ldflags` -o test
~ ➭ time ./test
./test  6,69s user 0,02s system 99% cpu 6,712 total

Приводим наш файл к pyrex-формату:

import random
cdef bubble_sort(int size):
    l = [random.randint(-9900, 9900) for _ in xrange(size)]
    for i in xrange(size):
        for j in xrange(size - i - 1):
            if l[j] > l[j+1]:
                l[j], l[j+1] = l[j+1], l[j]
bubble_sort(10000)

~ ➭ cython test.pyx --embed
~ ➭ gcc -g -O2 test.c  `python-config --includes --ldflags` -o test
~ ➭ time ./test
./test  7,04s user 0,02s system 99% cpu 7,063 total

Никакого эффекта.

PyPy
Ну и победитель сего конкурса:

~ ➭ time pypy test.py
pypy test.py  0,39s user 0,03s system 98% cpu 0,431 total

terabayt

Янв. 8, 2015 23:27:12

GreyZmeem
Используйте xrange, вместо range.

а если у него 3 пайтон?
и вместо вот этого:

for i in xrange(size):
        is_sorted = True
        for j in xrange(size - i - 1):

можно

for i in xrange(1, size):
        is_sorted = True
        for j in xrange(size - i):

GreyZmeem

Янв. 9, 2015 00:41:53

terabayt
а если у него 3 пайтон?

Тогда просто range

Из поста ТК не понятно какая у него версия.

terabayt
и вместо вот этого:
…
можно
…

Да, это немного ускорит выполнение.

hdj

Янв. 9, 2015 07:19:51

питон 3

пасибо всем, буду разбираться