Могу ли я уменьшить вычислительную сложность этого?
https://stackoverflow.com/questions/383728
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Ну, у меня есть этот фрагмент кода, который сильно замедляет работу программы, потому что он линейной сложности, но вызывается много раз, что делает программу квадратичной сложности.Если возможно, я хотел бы уменьшить его вычислительную сложность, но в противном случае я просто оптимизирую его там, где смогу.До сих пор я сводился к:
def table(n):
a = 1
while 2*a <= n:
if (-a*a)%n == 1: return a
a += 1
Кто-нибудь видит что-нибудь, что я пропустил?Спасибо!
Редактировать:Я забыл упомянуть:n всегда является простым числом.
ПРАВКА 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...
Решение
Основано на второй правке 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))*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.(Академический, поскольку есть алгоритм получше.)
Возможно ли у вас кэшировать результаты?
Когда вы вычисляете большое n, вам выдаются результаты для меньших n практически бесплатно.
Одна вещь, которую вы делаете, - это повторение вычисления -a * a снова и снова.
Создайте таблицу значений один раз, а затем выполните поиск в основном цикле.
Также, хотя это, вероятно, к вам не относится, потому что имя вашей функции - table, но если вы вызываете функцию, для вычисления которой требуется время, вам следует кэшировать результат в таблице и просто выполнить поиск по таблице, если вы вызовете ее снова с тем же значением.Это экономит вам время на вычисление всех значений при первом запуске, но вы не тратите время на повторение вычисления более одного раза.
Я просмотрел и исправил гарвардскую версию, чтобы заставить ее работать с python 3. http://modular.fas.harvard.edu/ent/ent_py
Я внес некоторые незначительные изменения, чтобы результаты были точно такими же, как у функции OP.Есть два возможных ответа, и я заставил его вернуть меньший ответ.
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
Редактирование ОПЕРАЦИЙ 2 745 мс
Принятый ответ 522 мс
Вышеуказанная функция составляет 0,2 мс
