Очень большие различия во времени выполнения для практически одного и того же кода на C ++ и Python
Я пытался написать решение для Задача 12 (Проект Эйлера) в Python. Решение было слишком медленным, поэтому я попытался проверить решение других людей в Интернете. я нашел этот код написанный на C ++, который делает практически то же самое, что и мой код на python, с несколькими незначительными отличиями.
Python:
def find_number_of_divisiors(n):
if n == 1:
return 1
div = 2 # 1 and the number itself
for i in range(2, n/2 + 1):
if (n % i) == 0:
div += 1
return div
def tri_nums():
n = 1
t = 1
while 1:
yield t
n += 1
t += n
t = tri_nums()
m = 0
for n in t:
d = find_number_of_divisiors(n)
if m < d:
print n, ' has ', d, ' divisors.'
m = d
if m == 320:
exit(0)
C ++:
#include <iostream>
int main(int argc, char *argv[])
{
unsigned int iteration = 1;
unsigned int triangle_number = 0;
unsigned int divisor_count = 0;
unsigned int current_max_divisor_count = 0;
while (true) {
triangle_number += iteration;
divisor_count = 0;
for (int x = 2; x <= triangle_number / 2; x ++) {
if (triangle_number % x == 0) {
divisor_count++;
}
}
if (divisor_count > current_max_divisor_count) {
current_max_divisor_count = divisor_count;
std::cout << triangle_number << " has " << divisor_count
<< " divisors." << std::endl;
}
if (divisor_count == 318) {
exit(0);
}
iteration++;
}
return 0;
}
Код Python выполняется на моей машине 1 минуту и 25,83 секунды. В то время как код C ++ занимает около 4,628 секунд. Это как в 18 раз быстрее. Я ожидал, что код C ++ будет быстрее, но не с таким большим отрывом, и это слишком просто для простого решения, которое состоит всего из 2 циклов и нескольких приращений и модов.
Хотя я был бы признателен за ответы о том, как решить эту проблему, основной вопрос, который я хочу задать, Почему код на C ++ намного быстрее? Я использую / делаю что-то неправильно в Python?
Замена диапазона на xrange:
После замены range на xrange выполнение кода Python занимает около 1 минуты 11,48 секунды. (Примерно в 1,2 раза быстрее)
Решение
Это именно тот код, в котором C ++ будет сиять по сравнению с Python: один довольно узкий цикл, выполняющий арифметические операции. (Я собираюсь игнорировать алгоритмические ускорения здесь, потому что ваш код C ++ использует тот же алгоритм, и кажется, что вы явно не просите об этом …)
C ++ компилирует этот вид кода до сравнительно небольшого числа инструкций для процессора (и все, что он делает, вероятно, вписывается в супер-быстрые уровни кэша процессора), в то время как Python имеет много уровней косвенности, которые он проходит для каждого операция. Например, каждый раз, когда вы увеличиваете число, он проверяет, что число не просто переполнено, и его нужно перенести в больший тип данных.
Тем не менее, не обязательно все потеряно! Это также тот код, который как раз вовремя система компилятора, как PyPy преуспеет в этом, поскольку, пройдя через цикл несколько раз, он компилирует код в нечто похожее на то, с чего начинается код C ++. На моем ноутбуке:
$ time python2.7 euler.py >/dev/null
python euler.py 72.23s user 0.10s system 97% cpu 1:13.86 total
$ time pypy euler.py >/dev/null
pypy euler.py > /dev/null 13.21s user 0.03s system 99% cpu 13.251 total
$ clang++ -o euler euler.cpp && time ./euler >/dev/null
./euler > /dev/null 2.71s user 0.00s system 99% cpu 2.717 total
используя версию кода Python с xrange вместо range, Уровни оптимизации не имеют значения для меня с кодом C ++, и ни один не использует GCC вместо Clang.
Пока мы на это, это также тот случай, когда Cython может очень хорошо, который компилирует почти-Python-код в C-код, который использует API-интерфейсы Python, но использует сырой C, когда это возможно. Если мы немного изменим ваш код, добавив некоторые объявления типов и удалив итератор, так как я не знаю, как эффективно обрабатывать их в Cython, получим
cdef int find_number_of_divisiors(int n):
cdef int i, div
if n == 1:
return 1
div = 2 # 1 and the number itself
for i in xrange(2, n/2 + 1):
if (n % i) == 0:
div += 1
return div
cdef int m, n, t, d
m = 0
n = 1
t = 1
while True:
n += 1
t += n
d = find_number_of_divisiors(t)
if m < d:
print n, ' has ', d, ' divisors.'
m = d
if m == 320:
exit(0)
тогда на моем ноутбуке я получаю
$ time python -c 'import euler_cy' >/dev/null
python -c 'import euler_cy' > /dev/null 4.82s user 0.02s system 98% cpu 4.941 total
(в 2 раза больше кода C ++).
Другие решения
Переписать алгоритм подсчета делителей для использования функция делителя делает время выполнения сокращается до менее 1 секунды. Все еще возможно сделать это быстрее, но не действительно необходимо.
Это должно показать, что: перед тем, как приступить к оптимизации с помощью языковых возможностей и компилятора, вы должны проверить, является ли ваш алгоритм узким местом или нет. Уловка с компилятором / интерпретатором действительно довольно мощная, как показано в ответе Дугала, где разрыв для Python и C ++ закрыт для эквивалентного кода. Однако, как вы можете видеть, изменение в алгоритме немедленно дает огромный прирост производительности и снижает время выполнения до уровня алгоритмически неэффективного кода C ++ (я не тестировал версию C ++, но на своем 6-летнем компьютере код ниже заканчивается через ~ 0.6s).
Код ниже написан и протестирован с Python 3.2.3.
import math
def find_number_of_divisiors(n):
if n == 1:
return 1
num = 1
count = 1
div = 2
while (n % div == 0):
n //= div
count += 1
num *= count
div = 3
while (div <= pow(n, 0.5)):
count = 1
while n % div == 0:
n //= div
count += 1
num *= count
div += 2
if n > 1:
num *= 2
return num
Вот мой собственный вариант, построенный на оптимизации подсчета факторов nhahtdh, плюс мой собственный основной код факторизации:
def prime_factors(x):
def factor_this(x, factor):
factors = []
while x % factor == 0:
x /= factor
factors.append(factor)
return x, factors
x, factors = factor_this(x, 2)
x, f = factor_this(x, 3)
factors += f
i = 5
while i * i <= x:
for j in (2, 4):
x, f = factor_this(x, i)
factors += f
i += j
if x > 1:
factors.append(x)
return factors
def product(series):
from operator import mul
return reduce(mul, series, 1)
def factor_count(n):
from collections import Counter
c = Counter(prime_factors(n))
return product([cc + 1 for cc in c.values()])
def tri_nums():
n, t = 1, 1
while 1:
yield t
n += 1
t += n
if __name__ == '__main__':
m = 0
for n in tri_nums():
d = factor_count(n)
if m < d:
print n, ' has ', d, ' divisors.'
m = d
if m == 320:
break
detector