Могу ли я уменьшить вычислительную сложность этого?
Ну, у меня есть немного кода, который сильно замедляет программу, потому что это линейная сложность, но многократно вызываемая программа, делающая программу квадратичной сложностью. Если возможно, я бы хотел уменьшить его вычислительную сложность, но в противном случае я просто оптимизирую его, где смогу. До сих пор я сократил до:
def table(n):
a = 1
while 2*a <= n:
if (-a*a)%n == 1: return a
a += 1
Кто-нибудь видит что-то, что я пропустил? Спасибо!
РЕДАКТИРОВАТЬ: я забыл упомянуть: п всегда простое число.
РЕДАКТИРОВАТЬ 2: Вот моя новая улучшенная программа (спасибо за все вклады!):
def table(n):
if n == 2: return 1
if n%4 != 1: return
a1 = n-1
for a in range(1, n//2+1):
if (a*a)%n == a1: return a
РЕДАКТИРОВАТЬ 3: И проверить его в реальном контексте это гораздо быстрее! Ну, этот вопрос кажется решенным, но есть много полезных ответов. Я должен также сказать, что, как и вышеописанные оптимизации, я запомнил функцию, используя словари Python...
10 ответов
На основании второго редактирования OP:
def table(n):
if n == 2: return 1
if n%4 != 1: return
mod = 0
a1 = n - 1
for a in xrange(1, a1, 2):
mod += a
while mod >= n: mod -= n
if mod == a1: return a//2 + 1
Игнорируя алгоритм на мгновение (да, я знаю, плохая идея), время работы этого может быть значительно уменьшено, просто переключаясь с while в for,
for a in range(1, n / 2 + 1)
(Надеюсь, что в этом нет единой ошибки. Я склонен делать это.)
Еще одна вещь, которую я бы попробовал - посмотреть, можно ли увеличить ширину шага.
Взгляните на http://modular.fas.harvard.edu/ent/ent_py. Функция sqrtmod делает работу, если вы установите a = -1 и p = n.
Небольшой момент, который вы пропустили, заключается в том, что время работы вашего улучшенного алгоритма все еще находится в порядке квадратного корня из n. Пока у вас есть только небольшие простые числа n (скажем, менее 2^64), это нормально, и вы, вероятно, предпочтете свою реализацию более сложной.
Если простое число n становится больше, вам, возможно, придется переключиться на алгоритм, использующий немного теории чисел. Насколько мне известно, ваша проблема может быть решена только с помощью вероятностного алгоритма во времени log(n)^3. Если я правильно помню, предполагая, что гипотеза Римана верна (что большинство людей делают), можно показать, что время выполнения следующего алгоритма (в ruby - извините, я не знаю python) - это log(log(n))* журнал (п)^3:
class Integer
# calculate b to the power of e modulo self
def power(b, e)
raise 'power only defined for integer base' unless b.is_a? Integer
raise 'power only defined for integer exponent' unless e.is_a? Integer
raise 'power is implemented only for positive exponent' if e < 0
return 1 if e.zero?
x = power(b, e>>1)
x *= x
(e & 1).zero? ? x % self : (x*b) % self
end
# Fermat test (probabilistic prime number test)
def prime?(b = 2)
raise "base must be at least 2 in prime?" if b < 2
raise "base must be an integer in prime?" unless b.is_a? Integer
power(b, self >> 1) == 1
end
# find square root of -1 modulo prime
def sqrt_of_minus_one
return 1 if self == 2
return false if (self & 3) != 1
raise 'sqrt_of_minus_one works only for primes' unless prime?
# now just try all numbers (each succeeds with probability 1/2)
2.upto(self) do |b|
e = self >> 1
e >>= 1 while (e & 1).zero?
x = power(b, e)
next if [1, self-1].include? x
loop do
y = (x*x) % self
return x if y == self-1
raise 'sqrt_of_minus_one works only for primes' if y == 1
x = y
end
end
end
end
# find a prime
p = loop do
x = rand(1<<512)
next if (x & 3) != 1
break x if x.prime?
end
puts "%x" % p
puts "%x" % p.sqrt_of_minus_one
Медленная часть теперь находит простое число (для этого требуется прибл. Log(n)^4 целочисленная операция); нахождение квадратного корня из -1 занимает 512-разрядных простых чисел, все еще меньше секунды.
Рассмотрите возможность предварительного вычисления результатов и сохранения их в файле. В настоящее время многие платформы имеют огромную емкость диска. Тогда получение результата будет O(1) операцией.
(Основываясь на ответе Адама.) Посмотрите на страницу Википедии о квадратичной взаимности:
x ^ 2 ≡ −1 (mod p) разрешима тогда и только тогда, когда p ≡ 1 (mod 4).
Тогда вы можете избежать поиска корня именно для тех нечетных простых n, которые не совпадают с 1 по модулю 4:
def table(n):
if n == 2: return 1
if n%4 != 1: return None # or raise exception
...
Похоже, вы пытаетесь найти квадратный корень из -1 по модулю n, К сожалению, это не простая проблема, в зависимости от того, какие значения n вход в вашу функцию. В зависимости от n, может даже не быть решения. Посмотрите Википедию для получения дополнительной информации по этой проблеме.
Редактировать 2: Удивительно, но уменьшение силы возведения в квадрат значительно сокращает время, по крайней мере, на моей установке Python2.5. (Я удивлен, потому что я думал, что накладные расходы интерпретатора занимают большую часть времени, и это не уменьшает количество операций во внутреннем цикле.) Сокращает время с 0,572 с до 0,146 с для таблицы (1234577).
def table(n):
n1 = n - 1
square = 0
for delta in xrange(1, n, 2):
square += delta
if n <= square: square -= n
if square == n1: return delta // 2 + 1
Стрэджер опубликовал ту же идею, но я думаю, что менее жестко закодированы Опять же, ответ кувшина лучший.
Оригинальный ответ: Еще одна тривиальная настройка кода над Конрадом Рудольфом:
def table(n):
n1 = n - 1
for a in xrange(1, n // 2 + 1):
if (a*a) % n == n1: return a
Ускоряет это на моем ноутбуке. (Около 25% для таблицы (1234577).)
Изменить: я не заметил тег python3.0; но главное изменение заключалось в том, чтобы вывести часть расчета из цикла, а не использовать xrange, (Академический, так как есть лучший алгоритм.)
Я прошел и исправил версию Гарварда, чтобы она работала с Python 3. http://modular.fas.harvard.edu/ent/ent_py
Я сделал несколько небольших изменений, чтобы результаты были точно такими же, как и у функции ОП. Есть два возможных ответа, и я заставил его вернуть меньший ответ.
import timeit
def table(n):
if n == 2: return 1
if n%4 != 1: return
a1=n-1
def inversemod(a, p):
x, y = xgcd(a, p)
return x%p
def xgcd(a, b):
x_sign = 1
if a < 0: a = -a; x_sign = -1
x = 1; y = 0; r = 0; s = 1
while b != 0:
(c, q) = (a%b, a//b)
(a, b, r, s, x, y) = (b, c, x-q*r, y-q*s, r, s)
return (x*x_sign, y)
def mul(x, y):
return ((x[0]*y[0]+a1*y[1]*x[1])%n,(x[0]*y[1]+x[1]*y[0])%n)
def pow(x, nn):
ans = (1,0)
xpow = x
while nn != 0:
if nn%2 != 0:
ans = mul(ans, xpow)
xpow = mul(xpow, xpow)
nn >>= 1
return ans
for z in range(2,n) :
u, v = pow((1,z), a1//2)
if v != 0:
vinv = inversemod(v, n)
if (vinv*vinv)%n == a1:
vinv %= n
if vinv <= n//2:
return vinv
else:
return n-vinv
tt=0
pri = [ 5,13,17,29,37,41,53,61,73,89,97,1234577,5915587277,3267000013,3628273133,2860486313,5463458053,3367900313 ]
for x in pri:
t=timeit.Timer('q=table('+str(x)+')','from __main__ import table')
tt +=t.timeit(number=100)
print("table(",x,")=",table(x))
print('total time=',tt/100)
Эта версия занимает около 3 мс, чтобы пройти через тестовые примеры выше.
Для сравнения используем простое число 1234577
OP Edit2 745мс
Принятый ответ 522мс
Выше функция 0,2 мс
Можно ли кешировать результаты?
Когда вы вычисляете большое n, вы получаете результаты для более низких n почти бесплатно.
Одна вещь, которую вы делаете, это повторение расчета -a*a снова и снова.
Создайте таблицу значений один раз, а затем посмотрите в главном цикле.
Кроме того, хотя это, вероятно, не относится к вам, потому что ваше имя функции - таблица, но если вы вызываете функцию, для вычисления которой требуется время, вы должны кэшировать результат в таблице и просто выполнить поиск таблицы, если вы вызовете ее снова с тем же значение. Это сэкономит вам время вычисления всех значений при первом запуске, но вы не тратите время на повторение расчета более одного раза.