Почему Python настолько медленный для простого цикла?

Ответ 1

Я думаю, что делаю ошибки, потому что знаю, что Python используется многими научными проектами.

Они сильно используют SciPy (NumPy - самый известный компонент, но я слышал, что экосистема, разработанная вокруг NumPy API, еще важнее), что значительно ускоряет все виды операций, которые требуются этим проектам. Там, что вы делаете неправильно: вы не пишете свой критический код в C. Python отлично подходит для разработки в целом, но хорошо укомплектованные модули расширения - это важная оптимизация в своем собственном праве (по крайней мере, когда вы хрустаете цифры), Python - действительно дерьмовый язык для реализации жестких внутренних циклов.

По умолчанию (и на данный момент является самой популярной и широко поддерживаемой) реализация является простым интерпретатором байт-кода. Даже самые простые операции, такие как целочисленное деление, могут принимать сотни циклов процессора, несколько обращений к памяти (например, проверки типов являются популярным примером), несколько вызовов функций C и т.д. Вместо нескольких (или даже одиночных, в случае целых чисел разделение). Кроме того, язык разработан с множеством абстракций, которые добавляют накладные расходы. Ваш цикл выделяет 9999 объектов в куче, если вы используете xrange - гораздо больше, если вы используете range (9999 * 9999 целых минус около 256 * 256 для небольших целых чисел, которые кэшируются). Кроме того, версия xrange вызывает метод на каждой итерации для продвижения - версия range тоже, если итерация по последовательностям не была оптимизирована специально. Он по-прежнему принимает всю отправку байт-кода, хотя и сам по себе очень сложный (по сравнению с целым делением, конечно).

Было бы интересно посмотреть, что такое JIT (я бы порекомендовал PyPy над Psyco, последний не стал активно развиваться и в любом случае был очень ограниченным по масштабу), но это может хорошо работать для этого простого примера). После крошечной доли итераций он должен создать почти оптимальный цикл машинного кода, дополненный несколькими стражами - простые целочисленные сравнения, прыгая, если они терпят неудачу, - поддерживать правильность, если вы получили строку в этом списке. Java может сделать то же самое, только раньше (сначала не нужно трассировать) и с меньшим количеством защитных элементов (по крайней мере, если вы используете int s). Это почему так намного быстрее.

Ответ 2

Поскольку вы упоминаете научный код, посмотрите numpy. То, что вы делаете, возможно, уже сделано (вернее, использует LAPACK для таких вещей, как SVD). Когда вы слышите о том, что python используется для научного кода, люди, вероятно, не ссылаются на его использование так, как вы делаете в своем примере.

В качестве быстрого примера:

(Если вы используете python3, ваш пример будет использовать float-деление. В моем примере предполагается, что вы используете python2.x и, следовательно, целочисленное деление. Если нет, укажите i = np.arange(9999, dtype=np.float) и т.д.)

import numpy as np
i = np.arange(9999)
j = np.arange(1, 9999)
print np.divide.outer(i,j).sum()

Чтобы дать некоторое представление о времени... (здесь я использую деление с плавающей запятой, а не целочисленное деление, как в вашем примере):

import numpy as np

def f1(num):
    total = 0.0
    for i in range(num): 
        for j in range(1, num):
            total += (float(i) / j)
    return total

def f2(num):
    i = np.arange(num, dtype=np.float)
    j = np.arange(1, num, dtype=np.float)
    return np.divide.outer(i, j).sum()

def f3(num):
    """Less memory-hungry (and faster) version of f2."""
    total = 0.0
    j = np.arange(1, num, dtype=np.float)
    for i in xrange(num):
        total += (i / j).sum()
    return total

Если сравнить тайминги:

In [30]: %timeit f1(9999)
1 loops, best of 3: 27.2 s per loop

In [31]: %timeit f2(9999)
1 loops, best of 3: 1.46 s per loop

In [32]: %timeit f3(9999)
1 loops, best of 3: 915 ms per loop

Ответ 3

Это известное явление - код python является динамическим и интерпретируется, java-код статически типизирован и скомпилирован. Никаких сюрпризов нет.

Причины, по которым люди предпочитают питон, часто:

• меньшая база кода
• меньше избыточности (более DRY)
• код очистки

Однако, если вы используете библиотеку, написанную на C (из python), производительность может быть намного лучше (сравните: pickle до cpickle).

Ответ 4

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

total = sum(i / j for j in xrange(1, 9999) for i in xrange(9999))

Это выполняется через ~ 11 секунд на моей машине против ~ 26 для вашего исходного кода. Тем не менее на порядок медленнее, чем Java, но это больше соответствует тому, что вы ожидаете.

Ваш исходный код может, кстати, немного ускориться, инициализируя total до 0, а не 0.0, чтобы использовать целое число, а не добавление с плавающей запятой. Все ваши деления имеют целочисленные результаты, поэтому нет смысла суммировать результаты с поплавком.

На моей машине Psyco фактически замедляет выражения генератора примерно до той же скорости, что и исходный цикл (который он вообще не ускоряется).

Ответ 5

Использование понятийного списка

total = sum(i / j for j in xrange(1, 9999) for i in xrange(9999))

составляет 10,2 секунды, а с использованием pypy 1.7 - 2,5 секунд. Это смешно, потому что pypy ускоряет оригинальную версию до 2,5 секунд. Таким образом, для pypy-списка понимание было бы преждевременной оптимизацией;). Хорошая работа пипы!

Ответ 6

Преимущество Python в том, что существует гораздо большая гибкость (например, классы - объекты) по сравнению с Java (где у вас есть только этот механизм отражения)

Что не упоминается здесь Cython. Это позволяет вводить типизированные переменные и транс-компилировать ваш пример на C/С++. Тогда это намного быстрее. Я также изменил границы цикла...

from __future__ import division

cdef double total = 0.00
cdef int i, j
for i in range(9999):
    for j in range(1, 10000+i):
        total += (i / j)

from time import time
t = time()
print("total = %d" % total)
print("time = %f[s]" % (time() - t))

Далее

$ cython loops.pyx
$ gcc -I/usr/include/python2.7 -shared -pthread -fPIC -fwrapv -Wall -fno-strict-aliasing -O3 -o loops.so loops.c
$ python -c "import loops"

дает

total = 514219068
time = 0.000047[s]

Ответ 7

Python для циклов статически типизируется и интерпретируется. Не скомпилировано. Java быстрее, потому что у него есть дополнительные возможности ускорения JIT, которых нет у Python.

http://en.wikipedia.org/wiki/Just-in-time_compilation

Чтобы проиллюстрировать, насколько массивна разница в Java JIT, посмотрите на эту программу python, которая занимает около 5 минут:

if __name__ =='__main__':
    total = 0.0
    i=1
    while i<=9999:
        j=1
        while j<=9999:
            total=1
            j+=1
        i+=1
    print total

Хотя эта принципиально эквивалентная Java-программа занимает около 23 миллисекунд:

public class Main{
    public static void main(String args[]){
        float total = 0f; 

        long start_time = System.nanoTime();
        int i=1;

        while (i<=9999){
            int j=1;
            while(j<=9999){
                total+=1;
                j+=1;
            }
            i+=1;
        }
        long end_time = System.nanoTime();

        System.out.println("total: " + total);
        System.out.println("total milliseconds: " + 
           (end_time - start_time)/1000000);
    }
}

С точки зрения выполнения чего-либо в цикле for, Java очищает часы python, будучи на расстоянии от 1 до 1000 порядков быстрее.

Мораль истории: базовый питон для циклов следует избегать любой ценой, если требуется высокая скорость работы. Это может быть связано с тем, что Guido van Rossum хочет побудить людей использовать многопроцессорные дружественные конструкции, такие как сращивание массива, которые работают быстрее, чем Java.

Ответ 8

Выполнение научных вычислений с помощью python часто означает использование некоторых вычислительных программ, написанных на C/С++ в наиболее важных частях, причем python является внутренним языком script, как e.x. Sage (который также содержит много кода на Python).

Я думаю, что это может быть полезно: http://blog.dhananjaynene.com/2008/07/performance-comparison-c-java-python-ruby-jython-jruby-groovy/

Как вы можете видеть, psyco/PyPy может принести определенное улучшение, но все же он, вероятно, будет намного медленнее, чем С++ или Java.

Ответ 9

Не уверен, что была сделана рекомендация, но мне нравится заменять петли на понимание списка. Его быстрее, чище и более питонов.

http://www.pythonforbeginners.com/basics/list-comprehensions-in-python