Что-то не так с этим кодом Python, почему он работает так медленно по сравнению с Ruby?

Мне было интересно сравнить скорость Ruby и Python, поэтому я взял простейшее рекурсивное вычисление, а именно распечатал последовательность Фибоначчи.

Это код Python

#!/usr/bin/python2.7                       
def fib(n):
    if n == 0: 
        return 0
    elif n == 1:
        return 1 
    else:
        return fib(n-1)+fib(n-2)

i = 0
while i < 35:
    print fib(i)
    i = i + 1

и вот код рубина

#!/usr/bin/ruby

def fib(n)
    if n == 0
        return 0
    elsif n == 1
        return 1
    else
        fib(n-1)+fib(n-2)
    end
end 

i = 0 
while (i < 35)
    puts fib(i)
    i = i + 1 
end

за несколько прогонов, time сообщает это среднее

real    0m4.782s 
user    0m4.763s 
sys     0m0.010s

это для рубина, теперь python2.7 дает

real    0m11.605s
user    0m11.563s
sys     0m0.013s

В чем дело?


python ruby performance fibonacci
person rapadura    schedule 28.10.2010    source источник
comment
Я просто хочу указать, что итеративное вычисление будет намного быстрее в независимом от языка смысле. Использование здесь рекурсии приводит к тому, что одни и те же значения вычисляются снова и снова.   -  person Gavin H    schedule 28.10.2010
comment
Я не буду перечислять ответ, потому что я не знаю точную причину, но вполне вероятно, что компилятор ruby ​​имеет некоторые оптимизации, которых нет в Python. Наивные функции fib, использующие рекурсию, создают огромные стеки вызовов, с которыми некоторые языки плохо справляются. В частности, язык обычно должен реализовывать оптимизацию рекурсии хвостового вызова для эффективной обработки таких ситуаций и без переполнения стека при больших объемах рекурсии.   -  person CodexArcanum    schedule 28.10.2010
comment
Я согласен с CodexArcanum. Это может быть уместно: stackoverflow.com/questions / 824562 /   -  person duffymo    schedule 28.10.2010
comment
@ghills: Для записи, вполне возможно вычислить fib за линейное время с использованием рекурсии (хотя она не будет более читаемой, чем итеративная версия, и, вероятно, намного медленнее без TCO, так что ...).   -  person sepp2k    schedule 28.10.2010
comment
@Codex: Здесь нечего оптимизировать. Это определение не является хвостовым рекурсивным.   -  person sepp2k    schedule 28.10.2010
comment
Я думаю, вам нужно обратиться к людям, которые создали компиляторы, чтобы получить окончательный ответ на этот вопрос. Как сказал CodexArcanum, некоторая оптимизация выполняется в Ruby, но не в Python.   -  person Matti Lyra    schedule 28.10.2010
comment
@ sepp2k Я не был уверен, поскольку на самом деле не знаю, как сразу идентифицировать хвостовой рекурсивный вызов. Таким образом, почему я написал комментарий, а не ответ;) Тем не менее, спасибо за пояснение. Я также хотел использовать совокупную стоимость владения в качестве примера, поскольку я думаю, что некоторые компиляторы также выполняют другие формы устранения рекурсии.   -  person CodexArcanum    schedule 28.10.2010
comment
@ sepp2k - согласен, но в самом простом определении, как было опубликовано в вопросе, он экспоненциальный во времени и выполняет много ненужных пересчетов, тогда как простой цикл довольно понятен и эффективен.   -  person Gavin H    schedule 28.10.2010
comment
ах, если бы я мог принять ваше обсуждение как ответ, я бы принял его.   -  person rapadura    schedule 29.10.2010
comment
Зачем вообще петля? fibo = lambda n: int((((1 + math.sqrt(5)) / 2)**n + (1/((1 + math.sqrt(5)) / 2))**n) / math.sqrt(5) + 0.5)   -  person Nick T    schedule 29.10.2010
comment
Я бы также сказал, что менее чем на порядок (10-кратная разница в скорости) - это неплохой пробел для наивных программ, работающих на разных интерпретаторах, при условии одинаковых уровней абстракции для двух сравниваемых языков.   -  person kindall    schedule 29.10.2010
comment
Эта унидиоматическая функция практически бесполезна для сравнения скорости ruby ​​и python для любой программы, кроме этой.   -  person Chuck    schedule 29.10.2010
comment
Чак, из этого теста на плохую скорость я узнал, что python плохо работает с рекурсивными вызовами функций как ruby, и нужно позаботиться о разработке алгоритмов, чтобы этого избежать, например, чтобы вместо этого использовать генераторы. Я знаю, что не могу судить, и я не буду судить о Python на основе этого теста, но это стоило изучения.   -  person rapadura    schedule 29.10.2010
comment
@AntonioP ›› что я узнал из этого теста на плохую скорость ... ‹< Из вашего теста на плохую скорость, откуда вы знаете, что какая-либо разница в производительности связана именно с рекурсивными вызовами функций, а не со всеми вызовами функций? Откуда вы знаете, что разница не из-за оператора if? Откуда вы знаете, что разница не связана с целочисленной арифметикой?   -  person igouy    schedule 29.10.2010
comment
@AntonioP ›› что я узнал из этого теста на плохую скорость ... ‹< Откуда вы знаете, что программа Python не быстрее, чем программа Ruby для fib (17), fib (28) и fib (36)? [Вы не сообщили, какая реализация Ruby использовалась или какая ОС использовалась.]   -  person igouy    schedule 29.10.2010
comment
@igouy, я сделал это для fib (12), fib (16), fib (20), fib (30), fib (40), fib (50), 50 i пришлось прервать, потому что это заняло слишком много времени. Чем выше значение fib, которое я выберу, тем заметнее будет эффект скорости. Я использовал ruby ​​1.9.2p0 (18.08.2010, редакция 29036) [x86_64-linux] на ArchLinux и Python 2.7 (r27: 82500, 6 октября 2010 г., 12:29:13) [GCC 4.5.1] на linux2 Если вы есть любое другое объяснение, превращаюсь в ухо.   -  person rapadura    schedule 31.10.2010
comment
@AntonioP Вы понимаете, что ваше объяснение - предположение? Когда вы говорите, что я выбираю более высокую фибру, эффект более заметен в скорости, о которой вы говорите: больше вызовов функций, больше операторов if, больше арифметики - что заставляет вас догадываться, что причина / рекурсивные / вызовы функций? Сравнивали ли вы обе языковые реализации для нерекурсивных вызовов функций?   -  person igouy    schedule 01.11.2010
comment
@igouy, я знаю, это предположение. Я сделал еще один, используя только цикл while и еще одну проверку и присвоение if else. Руби по-прежнему выигрывает. Python: i = 0 a = 0 while i ‹6553500: i + = 1 if i! = 6553500: a = i else: print o print a # для ruby, просто добавьте два оператора end и удалите:, время ruby ​​составляет 0,74 с а время Python - 4,1 с.   -  person rapadura    schedule 01.11.2010
comment
@AntonioP Итак, теперь напишите рекурсивные версии, которые делают такое же количество вызовов функций, тот же оператор if и ту же арифметику - и сравните их с итеративными версиями. (И сравните более чем по одной точке данных.)   -  person igouy    schedule 01.11.2010
comment
@NickT: вы теряете точность с помощью чисел с плавающей запятой, например, сравните iterfib (), который использует целые числа, и binetfib (), который использует фиксированную точность < / а>   -  person jfs    schedule 18.10.2012

Ответы (5)


arrow_upward
8
arrow_downward

Эффективность рекурсии Python является причиной этих накладных расходов. Дополнительные сведения см. В этой статье. Вышеупомянутые решения, которые решают это итеративно, лучше подходят для Python, поскольку они не влекут за собой накладные расходы на вызов функции. Мое предположение о ruby ​​заключается в том, что он явно оптимизирует код, а python - нет. Опять же, эта статья подробно описывает это с использованием почти идентичной функции fib.

person dcolish    schedule 28.10.2010
comment
Мне тоже нравятся комментарии к той статье, которую вы связали. Это проливает свет на использование рекурсивных вызовов функций в Python. - person rapadura; 29.10.2010

arrow_upward
2
arrow_downward

Итак, для этого кода Python чуть более чем в два раза медленнее, чем Ruby. Вероятно, для других кодов Python будет быстрее, чем Ruby.

Ваша реализация fib () имеет экспоненциальное время выполнения. Этого легко избежать, используя цикл. Пример Python:

a, b = 1, 1
for i in range(35):
    a, b = b, a+b
print b
person Sven Marnach    schedule 28.10.2010
comment
Вопрос не в том, как написать эффективную реализацию fib (). Вопрос в том, почему создание огромных стеков вызовов в Python обходится дороже (если это так), чем в Ruby. - person jfs; 29.10.2010
comment
На самом деле я хотел бы сказать, что наблюдаемая разница мала - всего в два раза, что совсем не удивительно. Перечитывая свой пост еще раз, я считаю, что чужие комментарии лучше, но я просто оставлю его там :) - person Sven Marnach; 29.10.2010

arrow_upward
2
arrow_downward

Ваш метод вычисления первых 35 чисел в последовательности Фибоначчи чрезвычайно неэффективен. Вы запускаете функцию fib () 35 раз, и каждый раз функция fib () имеет экспоненциальное время выполнения. Генератор на Python - идеальное решение этой проблемы, и он намного более эффективен, чем то, что вы написали на Ruby.

def fibo_generator(n):
    # gets Fibonacci numbers up to nth number using a generator
    a, b = 0, 1
    for _ in range(n):
        yield a
        a, b = b, a + b

Затем вы можете распечатать все числа Фибоначчи до 35, используя этот код:

for f in fibo_generator(35):
    print f

Это, безусловно, самый эффективный способ реализации последовательности Фибоначчи в Python, а также самый универсальный.

person Rafe Kettler    schedule 28.10.2010
comment
Мне не нужен самый эффективный язык программирования x, я хочу знать, почему почти точные программы на Python и Ruby выполняются в очень разные временные рамки. Рубиновая версия оптимизирует код за моей спиной? Пока мы занимаемся этим, я думаю, что мемоизация значительно ускорит его. - person rapadura; 29.10.2010
comment
См. Ответ THC4k, чтобы узнать, почему этот тест ничего не значит. Это не означает, что Python медленнее Ruby, потому что ваше приложение не имеет особого смысла. Зачем вам делать что-то неэффективное на любом языке? Python является самым быстрым, если использовать его сильные стороны, как и Ruby. - person Rafe Kettler; 29.10.2010

arrow_upward
2
arrow_downward

Мне было интересно сравнить скорость Ruby и Python

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

Вот лучшее сравнение Python и Ruby.

person Jochen Ritzel    schedule 28.10.2010
comment
Почему это плохой способ сравнивать языки? В чем причина скорости Ruby по сравнению с почти таким же кодом на Python? Я знаю, что можно использовать генераторы, мемоизацию и тому подобное, чтобы дать последовательность в более удобное время ... но что меня интересует - почему такая большая разница для одного и того же кода? - person rapadura; 29.10.2010
comment
@AntonioP: Потому что такой код пишут только новички. Ваш тест говорит вам только о том, что эта плохая программа на Python работает медленнее, чем эта плохая программа на Ruby. Имеет смысл сравнивать только самые быстрые реализации, а не с одним и тем же кодом. - person Jochen Ritzel; 29.10.2010
comment
Я должен одновременно соглашаться и не соглашаться. Это правда, что сравнение плохих программ бесполезно. Однако я не согласен с тем, что вам следует сравнивать самые быстрые реализации. Я думаю, вам следует сравнить наиболее хорошо продуманные реализации. Задача составителя компилятора - убедиться, что наиболее хорошо спроектированная реализация также является самой быстрой, но если это не, вам не следует оптимизировать код, вам следует исправить компилятор. - person Jörg W Mittag; 29.10.2010
comment
@ Jörg W Mittag: Да, я полностью с вами согласен. - person Jochen Ritzel; 29.10.2010
comment
@ Jörg W Mittag: У разных людей скорее всего разные мнения о том, какие реализации являются наиболее хорошо продуманными. - person igouy; 29.10.2010

arrow_upward
2
arrow_downward

Вот еще несколько цифр для сравнения:

Python2.7
9.67 user 0.09 system 0:09.78 elapsed 99%CPU (0avgtext+0avgdata 16560maxresident)k
0inputs+0outputs (0major+1169minor)pagefaults 0swaps

ruby 1.8.7 (2010-06-23 patchlevel 299) [x86_64-linux]
28.37 user 0.35 system 0:28.78 elapsed 99% CPU (0avgtext+0avgdata 9200maxresident)k
1896inputs+0outputs (9major+656minor)pagefaults 0swaps

ruby 1.9.2p0 (2010-08-18 revision 29036) [x86_64-linux]
6.21 user 0.08 system 0:06.36 elapsed 98% CPU (0avgtext+0avgdata 14160maxresident)k
4416inputs+0outputs (16major+953minor)pagefaults 0swaps

Python в три раза быстрее, чем ruby1.8, и на 30% медленнее, чем ruby1.9.1 для предоставленного кода.

Другие версии Python для сравнения:

2.4.6 took 10.30 seconds

2.5.5 took 9.93 seconds

2.6.6 took 9.22 seconds

2.7   took 9.35 seconds

3.0.1 took 11.67 seconds

3.1.2 took 11.35 seconds

3.2a3+ (py3k:85895, Oct 29 2010, 01:41:57) 
[GCC 4.4.5] took 13.09 seconds

2.5.2 (77963, Oct 15 2010, 02:00:43)
[PyPy 1.3.0] took 21.26 seconds

2.5.1 (Release_2_5_1:6813, Sep 26 2009, 13:47:54) 
[OpenJDK 64-Bit Server VM (Sun Microsystems Inc.)] took 8.81 seconds
person jfs    schedule 28.10.2010