Posso reduzir a complexidade computacional deste?
https://stackoverflow.com/questions/383728
-
23-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Bem, eu tenho este pedaço de código que está a abrandar o programa extremamente porque é a complexidade linear, mas chamado de um monte de vezes tornando o programa complexidade quadrática. Se possível, eu gostaria de reduzir a sua complexidade computacional mas por outro lado eu vou apenas otimizá-lo sempre que posso. Até agora, tenho reduzido a:
def table(n):
a = 1
while 2*a <= n:
if (-a*a)%n == 1: return a
a += 1
Alguém viu alguma coisa que eu perdi? Obrigado!
EDIT: eu esqueci de mencionar: n é sempre um número primo
.EDIT 2: Aqui está o meu novo programa melhorado (obrigado de para todas as contribuições!):
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
EDIT 3: E testá-lo em seu contexto real, é muito mais rápido! Bem, esta questão parece resolvido, mas há muitas respostas úteis. Gostaria também de dizer que, assim como aqueles otimizações acima, tenho memoized a função usando Python dicionários ...
Solução
Com base off segunda edição do 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
Outras dicas
Ignorando o algoritmo por um momento (sim, eu sei, má idéia), o tempo de execução deste pode ser diminuída imensamente apenas alternando entre while para for.
for a in range(1, n / 2 + 1)
(Hope isso não tem um erro off-por-um. Estou propenso a torná-los.)
Outra coisa que eu tentaria é olhar se a largura do passo pode ser incrementado.
Dê uma olhada http://modular.fas.harvard.edu/ent/ent_py . A função sqrtmod faz o trabalho se você definir a = -1 e p = n.
Um pequeno ponto você perdeu é que o tempo de execução de seu algoritmo melhorado ainda está no fim da raiz quadrada de n. Contanto que você tem apenas pequenas primos n (digamos menos de 2 ^ 64) que é ok e você provavelmente deve preferir a implementação de um mais complexo.
Se o nobre n se torna maior, você pode ter que mudar para um algoritmo usando um pouco de teoria dos números. Para meu conhecimento o seu problema pode ser resolvido apenas com um algoritmo probabilístico no log de tempo (n) ^ 3. Se bem me lembro, assumindo a hipótese de Riemann detém (que a maioria das pessoas fazem), pode-se mostrar que o tempo de execução do algoritmo seguinte (em ruby ??- desculpe, eu não sei 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
A parte lenta agora é encontrar o prime (. Que leva aproximadamente log (n) ^ 4 operação inteiro); encontrar a raiz quadrada de -1 leva para primos de 512 bits ainda menos de um segundo.
Considere pré-computar os resultados e armazená-los em um arquivo. Hoje em dia muitas plataformas têm uma capacidade de disco enorme. Em seguida, obtendo-se o resultado será uma junta (1) operação.
(Com base na resposta de Adão.) Olhada na página da Wikipedia sobre quadrática reciprocidade :
x ^ 2 = -1 (mod p) é solúvel se e somente se p = 1 (mod 4).
Em seguida, você pode evitar a busca de uma raiz precisamente para aquelas estranhas principais n de que não são congruentes com 1 módulo 4:
def table(n):
if n == 2: return 1
if n%4 != 1: return None # or raise exception
...
Parece que você está tentando encontrar a raiz quadrada de -1 n modulo. Infelizmente, este não é um problema fácil, dependendo do que os valores de n são introduzidos em sua função. Dependendo n, não poderia mesmo ser uma solução. Consulte Wikipedia para mais informações sobre este problema.
Editar 2: Surpreendentemente, a força-reduzindo a quadratura reduz o tempo muito, pelo menos no meu instalação python2.5. (Eu estou surpreso porque eu pensei intérprete sobrecarga estava tomando a maior parte do tempo, e isso não reduz a contagem de operações no circuito interno.) Reduz o tempo de 0.572s para 0.146s para mesa (1.234.577).
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
strager postou a mesma idéia mas eu pensar menos firmemente codificada. Mais uma vez, do jarro resposta é melhor.
resposta Original: Outra emenda codificação trivial em cima de Konrad Rudolph:
def table(n):
n1 = n - 1
for a in xrange(1, n // 2 + 1):
if (a*a) % n == n1: return a
Acelera-lo mensurável no meu laptop. (Cerca de 25% para a tabela (1.234.577).)
Editar: Não notei a tag python3.0; mas a principal mudança foi içar parte do cálculo fora do circuito, e não o uso de xrange. (Academic uma vez que há um algoritmo melhor.)
É possível para você para armazenar em cache os resultados?
Quando você calcular um grande n você é dado os resultados para o menor n é quase de graça.
Uma coisa que você está fazendo é repetir o -a cálculo * uma e outra vez.
Criar uma tabela com os valores de uma vez, então não olhar para cima no circuito principal.
Além disso, embora isso provavelmente não se aplica a você, porque o seu nome da função é a tabela, mas se você chamar uma função que leva tempo para calcular você deve armazenar em cache o resultado em uma tabela e apenas fazer um olhar tabela acima se você chamá-lo novamente com o mesmo valor. Este poupar o tempo de cálculo todos os valores quando você executar primeiro, mas você não perder tempo repetindo o cálculo mais de uma vez.
Eu atravessei e fixa a versão Harvard para torná-lo trabalhar com python 3. http://modular.fas.harvard.edu/ent/ent_py
Eu fiz algumas pequenas alterações para tornar os resultados exatamente o mesmo que a função do OP. Há duas respostas possíveis e eu a obrigou a retornar a resposta menor.
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)
Esta versão leva cerca de 3ms para percorrer os casos de teste acima.
Para efeito de comparação usando o Prime Number 1234577
OP Edit2 745ms
Os 522ms resposta aceita
A função acima 0.2ms
