Kann ich die Rechenkomplexität dieses reduzieren?

StackOverflow https://stackoverflow.com/questions/383728

Frage

Nun, ich habe dieses Stück Code, der das Programm enorm verlangsamt sich, weil sie lineare Komplexität ist aber eine Menge Zeit machen das Programm quadratische Komplexität genannt. Wenn möglich, würde Ich mag seine Rechenkomplexität reduzieren, aber sonst werde ich es nur optimieren, wo ich kann. Bisher habe ich reduziert bis auf: 

def table(n):
    a = 1
    while 2*a <= n:
      if (-a*a)%n == 1: return a

      a += 1

Jeder sehen, was ich verpasst habe? Dank!

EDIT: Ich vergaß zu erwähnen: n. Ist immer eine Primzahl

EDIT 2: Hier ist mein neues verbessertes Programm (danken der für alle Beiträge!): 

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: Und es testet in ihrem realen Kontext heraus, es ist viel schneller! Nun, diese Frage scheint gelöst, aber es gibt viele nützliche Antworten. Ich sollte auch so gut wie die oben Optimierungen, sagen, dass ich die Funktion mit Python-Dictionaries memoized haben ...

War es hilfreich?

Lösung

Basierend off OP zweit bearbeiten: 

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

Andere Tipps

Das Ignorieren des Algorithmus für einen Moment (ja, ich weiß, schlechte Idee), kann die Laufzeit dieses verringert werden sehr groß nur durch von while Umstellung auf for. 

for a in range(1, n / 2 + 1)

(Hoffe, dass dies nicht ein Off-by-one Fehler hat. Ich bin anfällig für diese zu machen.)

Eine andere Sache, die ich versuchen würde, ist zu sehen, wenn die Schrittweite erhöht werden kann.

Hier finden Sie aktuelle http://modular.fas.harvard.edu/ent/ent_py . Die Funktion sqrtmod macht den Job, wenn Sie setzen a = -1 und p = n.

Ein kleiner Punkt, den Sie verpasst ist, dass die Laufzeit des verbesserten Algorithmus immer noch in der Größenordnung der Quadratwurzel von n ist. Solange Sie nur kleine Primzahlen haben n (sagen wir mal weniger als 2 ^ 64) das ist in Ordnung, und Sie sollten wahrscheinlich Ihre Implementierung einer komplexeren vorziehen.

Wenn die Primzahl n größer wird, können Sie auf einen Algorithmus wechseln haben ein wenig Zahlentheorie verwendet wird. Meines Wissens kann Ihr Problem nur mit einem probabilistischen Algorithmus in der Zeit log (n) ^ 3 gelöst werden. Wenn ich mich richtig erinnere, hält die Riemann Hypothese angenommen (was die meisten Menschen tun), kann man zeigen, dass die Laufzeit des folgenden Algorithmus (in Ruby - sorry, ich weiß nicht, Python) ist 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

Der langsame Teil jetzt ist das Haupt Auffinden (., Das ca. nimmt lügt (n) ^ 4 Ganzzahl-Operation); von -1 nimmt für 512-Bit-Primzahlen immer noch weniger als eine Sekunde, um die Quadratwurzel zu finden.

Beachten Sie die Ergebnisse vor der Berechnung und sie in einer Datei zu speichern. Heutzutage haben viele Plattformen eine riesige Plattenkapazität. Dann wird das Ergebnis zu erhalten, wird, um ein O (1) Betrieb.

(Aufbauend auf Adams Antwort.) Schauen Sie sich die Wikipedia-Seite über quadratische Reziprozität :

  

x ^ 2 ≡ -1 (mod p) ist lösbar, wenn und nur wenn p ≡ 1 (mod 4).

Dann können Sie die Suche nach einer Wurzel genau für diejenigen, ungerade Primzahl n Vermeiden, die mit nicht deckungsgleich sind 1 modulo 4: 

def table(n):
    if n == 2: return 1
    if n%4 != 1: return None   # or raise exception
    ...

Es sieht aus wie Sie versuchen, die Quadratwurzel von -1 modulo n zu finden. Leider ist dies kein einfaches Problem, je nachdem, welche Werte von n eingegeben werden in Ihrer Funktion. Je nach n könnte es nicht einmal eine Lösung sein. Siehe Wikipedia für weitere Informationen zu diesem Problem.

Edit 2: Überraschenderweise festigkeitsmindernde die Quadratur reduziert eine Menge Zeit, zumindest auf meiner python2.5 Installation. (Ich bin überrascht, weil ich Dolmetscher Kopf gedacht wurde, die meiste Zeit nehmen, und dies verringert nicht die Anzahl der Operationen in der inneren Schleife.) Reduziert die Zeit von 0.572s auf 0.146s für Tisch (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 posted href="https://stackoverflow.com/questions/383728/can-i-reduce-the-computational-complexity-of-this#383983"> aber ich denken weniger fest codiert. Wieder Antwort Krug ist am besten.

Original Antwort: Eine andere trivial Codierung zwicken oben auf Konrad Rudolph: 

def table(n):
    n1 = n - 1
    for a in xrange(1, n // 2 + 1):
          if (a*a) % n == n1: return a

Beschleunigt es meßbar auf meinem Laptop auf. (Ca. 25% für die Tabelle (1.234.577).)

Edit: Ich habe nicht den python3.0-Tag bemerken; aber die Hauptänderung Teil der Berechnung aus der Schleife wurde Hissen, nicht die Verwendung von xrange. (Academic da es ein besserer Algorithmus.)

Ist es möglich, dass Sie die Ergebnisse zwischenzuspeichern?

Wenn Sie berechnen einen großen n Sie die Ergebnisse für die untere Gegeben n ist fast kostenlos.

Eine Sache, die Sie tun, ist die Berechnung -a Wiederholung * a immer und immer wieder.

Erstellen Sie eine Tabelle der Werte einmal und dann in die Hauptschleife nachschauen kann.

Auch obwohl dies wahrscheinlich für Sie nicht gilt, weil Ihre Funktion Namentabelle ist aber, wenn Sie eine Funktion aufrufen, die Zeit zu berechnen dauert, sollten Sie das Ergebnis in einer Tabelle zwischenzuspeichern und eine Tabelle nachschlagen nur tun, wenn Sie es wieder anrufen mit dem gleichen Wert. Dies erspart Ihnen die Zeit alle Werte berechnet wird, wenn Sie zum ersten Mal ausgeführt, aber Sie haben keine Zeit, die Berechnung mehr als einmal zu wiederholen verschwenden.

Ich ging durch und fixierte die Harvard-Version nur noch mit 3 mit Python arbeiten.   http://modular.fas.harvard.edu/ent/ent_py

habe ich einige geringfügige Änderungen die Ergebnisse die gleichen wie die OP der Funktion genau zu machen. Es gibt zwei mögliche Antworten und ich gezwungen, es die kleinere Antwort zurück. 

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)

Diese Version nimmt 3 ms über oben durch die Testfälle zu laufen.

Zum Vergleich mit der Primzahl 1234577
OP EDIT2 745ms
Die akzeptierte Antwort 522ms
Die obige Funktion 0,2 ms

Lizenziert unter: CC-BY-SA mit Zuschreibung
Nicht verbunden mit StackOverflow
scroll top