Как я могу заставить это решение Project Euler выполняться на Python с той же скоростью, что и на Java?

Question

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

Я решил Project Euler 5 на обоих языках, и, хотя мои реализации на обоих языках выглядят довольно схожими на мой взгляд, время выполнения сильно отличается,Java возвращает ответ всего за несколько секунд, тогда как Python может занять до минуты (конечно, на той же машине).Я совершенно уверен, что это не вина Python, а скорее ошибка программиста (меня), который еще не научился мыслить на Python.

Обратите внимание, что Я не прошу вас переписыватьмой код .Я просто ищу несколько толчков в правильном направлении.(И да, я смотрел на некоторые похожие темы , но большинство из них у меня над головой и не сравнивают напрямую один и тот же алгоритм на двух языках. Этот поток полезен, но, опять же, напрямую не сравнивает Java и Python - и, честно говоря, ответы немного сложны.)

Без дальнейших церемоний:

Java

public class Problem5 {

    public static void main(String[] args){
        boolean found = false;

        for (int i = 20; !found; i += 20){
            if (DivisThrough20(i)) {
                found = true;
                System.out.println(i);
            }
        }
    }

    private static boolean DivisThrough20(int number){
        boolean result = true;
        for (int i = 19; result && i > 1; i--){
            if (number % i != 0) result = false;
        }
        return result;
    }
}

Python

def DivisThroughTwenty(number):
    for x in range(20,1,-1):
        if number % x != 0:
            return False
    return True

# the number we're looking for can't be any lower than 20, so we'll
# start there as a small optimization
testNumber = 20

keepLooking = True

while keepLooking:
    if not DivisThroughTwenty(testNumber):
        testNumber += 20
    else:
        keepLooking = False

print testNumber

Забавно, читая их бок о бок, я уже вижу, что версия этого алгоритма на Python немного более оптимизирована, чем версия на Java,все же это все еще намного медленнее.Мне еще интереснее найти другой способ решения проблемы.

Answer 1

Python - это динамически типизированный язык, а Java - статически типизированный язык.Это означает, что во время компиляции Java имеет более доступную информацию о типах переменных, в частности числах.Разработчики Java потратили немало усилий, чтобы определить JVM таким образом, чтобы 32-разрядные (int) и 64-разрядные арифметические (long) вычисления могли работать эффективно.

Python,с другой стороны, не имеет объявлений типов переменных, поэтому такие переменные, как x могут вообще содержать любой объект.В вашем случае бывает, что они всегда содержат числа, но компилятор CPython не пытается это проверить.Когда Python выполняет ваш код, вычисление выражения, такого как number % x, включает поиск оператора % для объекта, представленного number, вызов оператора %, получение типа x, подтверждение того, что оносовместимый тип числа и т. д. Все это требует времени, особенно когда вы делаете это миллионы раз.

Альтернативные реализации Python, такие как PyPy, прилагают большие усилия, чтобы попытаться определить типы ваших переменных.В вашем случае он может определить, что number и x всегда ссылаются на целые числа , и сгенерировать соответствующий низкоуровневый код, который не должен проверять типы.

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

Answer 2

Я не уверен, насколько это может помочь, но ваш рабочий код может быть переписан гораздо более питоническим способом, например:

def divis_through_twenty(n):
  return any(n % x for x in xrange(20,1,-1))

x = 20
while divis_through_twenty(x):
  x += 20

print x

Вы можете оптимизировать его немного больше, если хотите (например, если вы уже тестировали число, делимое на 20, вам не нужно проверять, делится ли оно на 10, 5 или 2).