Я столкнулся с очень любопытным случаем значительного ускорения в коде после изменения, казалось бы, незначительной детализации.У меня есть следующий код, который является реализацией алгоритма Боровейна для вычисления факториала, реализованного в SageMath (но кроме некоторых незначительных вещей, таких как ^ для возведения в степень, он должен работать в чистом Python 2.7)
def sieve(n): #My implementation of the sieve of Eratosthenes
T = [1]*n
for i in xrange(2,n):
if T[i]==1:
for j in xrange(2,ceil(n/i)):
T[i*j]=0
return [i for i in xrange(2,n) if T[i]]
def expp(n,p): #Exponent of p in the factorization of n!
k = p
s = 0
while k<=n:
s += n//k
k = k*p
return s
def quick_prod(T): #Computing product of the elements of an array using binary splitting
if len(T)==1:
return T[0]
if len(T)==2:
return T[0]*T[1]
if len(T)>2:
s = len(T)//2
return quick_prod(T[0:s])*quick_prod(T[s:len(T)])
n = 10^6
P = sieve(n) #Array of primes up to n
exps = [expp(n,p) for p in P] #exponents of all primes in P
l = len(bin(abs(n)))-2
nums = [quick_prod([P[j] for j in xrange(len(P)) if (exps[j] >> i)%2])^(2^i) for i in range(l)] #Array of numbers appearing in Borwein's algorithm, whose product is n!
quick_prod(nums)
(Извините за мои ужасные соглашения об именах (и, возможно, другие плохие практики кодирования), я - любитель и на самом деле кодирую вещи "быстро и грязно")
Я не ожидал, что этот код будет особенно эффективным,поэтому я не был удивлен, увидев, что это заняло 10 минут, чтобы бежать.Но когда я начал возиться с кодом, чтобы попытаться улучшить его, я заметил, что замена строки P = sieve(n) на P = prime_range(n) (которая производит тот же массив, за исключением того, что использует функцию, встроенную в SageMath) сократил время выполнения до 3,5 секунд.
Теперь, когда я увидел это, моей первой мыслью было, что объяснение очевидно - моя реализация сита должна быть настолько ужасной, что потребовалась целая вечность, а prime_range делаетэто намного эффективнее.Но результаты меня удивили - sieve(10^6) заняло 4 секунды, а prime_range(10^6) - 2 секунды.Это даже не близко к объяснению разницы в 10 минут!
Некоторые идеи, которые я и мои друзья могли объяснить, могут:
- Два массива могут быть разными,например, они могут быть заказаны по-разному.Это не так, поскольку
sieve(10^6)==prime_range(10^6) возвращает True - Несмотря на равенство, массивы могут храниться в разных типах.
type(...) возвращает list для обоих. - Промежуточные результаты получают в кеше.Вероятно, это не так, поскольку результаты примерно одинаковы, независимо от порядка компиляции, даже после перезапуска ядра.
Единственный способ такого значительного ускорения (или замедления, в зависимости от того, как выПосмотрите на это), может случиться так, если исходный код каким-то образом вернется к тому способу, которым P был сгенерирован после его вычисления.Что может объяснить это поведение?