Могу ли я уменьшить вычислительную сложность этого?

Что ж, у меня есть этот фрагмент кода, который сильно замедляет программу, потому что это линейная сложность, но вызывается много раз, делая программу квадратичной сложностью. Если возможно, я хотел бы уменьшить его вычислительную сложность, но в противном случае я просто оптимизирую его, где смогу. Пока что я сократил до:

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

      a += 1

Кто-нибудь видит что-нибудь, что я пропустил? Спасибо!

Обновлено: я забыл упомянуть: n всегда является простым числом.

Обновлено еще раз: Вот моя новая улучшенная программа (спасибо за все вклады!):

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 ...

Вы вызываете это много раз: для множества различных значений n? Это образец для значений n?

David Nehme 20.12.2008 23:55

Вероятно ли, что некоторые значения n будут вызываться несколько раз? (в этом случае может быть какое-то значение в сохранении вычисленных значений, чтобы сохранить повторный запуск вычисления)

hamishmcn 21.12.2008 00:13

Какое значение имеет максимальное значение n и какое оно обычно?

Lasse V. Karlsen 21.12.2008 00:30

Я добавил улучшенную (более быструю) версию вашего кода ... Проверьте это в моем ответе.

strager 21.12.2008 07:28

Эта функция вызывается (и запоминается) для множества различных простых чисел n. Некоторые большие, некоторые маленькие ... страннее, спасибо!

PythonPower 21.12.2008 20:21

Я откатил его, так как "опечатка" на самом деле не была опечаткой. В Python три // выполняет «целочисленное деление», где / не усекает. Мы хотим, чтобы последнее было так, как положено.

PythonPower 21.12.2008 20:24

@PythonPower, держу пари, вас смутила подсветка синтаксиса Stackoverflow. // комментарии в стиле C++. Это меня тоже смутило (я не знал оператора Python) и сначала подумал, что это опечатка. Потом я понял, что это целочисленное деление.

strager 21.12.2008 22:42
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
9
7
2 597
10
Перейти к ответу Данный вопрос помечен как решенный

Ответы 10

Игнорируя алгоритм на мгновение (да, я знаю, плохая идея), время его работы можно уменьшить чрезвычайно, просто переключившись с while на for.

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

(Надеюсь, здесь нет ошибки разницы на единицу. Я склонен делать это.)

Еще я бы попробовал посмотреть, можно ли увеличить ширину шага.

Вы имели в виду, что время работы может быть уменьшился?

Robert Gamble 21.12.2008 00:06

Похоже, вы пытаетесь найти квадратный корень из -1 по модулю n. К сожалению, это непростая проблема, в зависимости от того, какие значения n вводятся в вашу функцию. В зависимости от n решения может и не быть. См. Википедия для получения дополнительной информации об этой проблеме.

n всегда является простым числом, так что это может помочь.

PythonPower 21.12.2008 00:09

Возможно ли кеширование результатов?

Когда вы вычисляете большое n, вам почти бесплатно выдаются результаты для меньших n.

(Основываясь на ответе Адама.) Взгляните на страницу Википедии на квадратичная взаимность:

x^2 ≡ −1 (mod p) is solvable if and only if p ≡ 1 (mod 4).

Тогда вы можете избежать поиска корня именно для тех нечетных простых чисел n, которые не сравнимы с 1 по модулю 4:

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

Рассмотрите возможность предварительного вычисления результатов и сохранения их в файле. В настоящее время многие платформы имеют огромную дисковую емкость. Тогда получение результата будет операцией O (1).

Я бы не стал делать это на диск, только на память.

Loren Pechtel 21.12.2008 01:48

@ me.yahoo.com / loren.pechtel, он имеет ввиду загружать файл в память при запуске, а не вычислять таблицу каждый раз при запуске приложения.

strager 21.12.2008 01:54

Это непрактично: их вычисление изначально было слишком медленным. Но обычно это вариант.

PythonPower 21.12.2008 20:25

Изменить 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

Strager отправил та же идея, но я думаю, что он менее жестко закодирован. Опять же, ответ кувшина лучше всего.

Оригинальный ответ: Еще одна тривиальная настройка кода поверх настроек Конрада Рудольфа:

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.0, только более старых версий. Однако использование //, конечно, лучше.

Konrad Rudolph 21.12.2008 01:49

Я имел в виду изменение n-1 (или -a) из цикла. Это составляет большую часть ускорения.

Darius Bacon 21.12.2008 03:13

Взгляните на 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-битных простых чисел меньше секунды.

Одна вещь, которую вы делаете, - это повторяете вычисление -a * a снова и снова.

Создайте таблицу значений один раз, а затем выполните поиск в основном цикле.

Кроме того, хотя это, вероятно, не относится к вам, потому что имя вашей функции - таблица, но если вы вызываете функцию, которая требует времени для вычисления, вы должны кэшировать результат в таблице и просто выполнить поиск таблицы, если вы снова вызовете ее с тем же значение. Это сэкономит вам время на вычисление всех значений при первом запуске, но вы не будете тратить время на повторение расчета более одного раза.

Поиск, вероятно, будет медленнее, чем умножение. Умножение довольно дешево по сравнению с модулем без знака.

strager 21.12.2008 01:58

Это академично, так как есть лучший алгоритм, но мой ответ вывел часть вычисления -a * из цикла.

Darius Bacon 21.12.2008 03:14
Ответ принят как подходящий

На основе второго редактирования 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

должно быть пока mod> = n: mod - = n

Rex Logan 21.12.2008 20:42

@Rex Logan, Хм ... Думаю, ты прав, но когда я тестировал значения 0..31337, все они работали. Я думаю, это потому, что a1 = n-1: если бы это было a1 = n-1, я, возможно, мог бы сделать mod> n-1. Думаю, странный побочный эффект в мою пользу. Я исправлю это в любом случае. Спасибо!

strager 21.12.2008 22:39

Я просмотрел и исправил версию для Гарварда, чтобы она работала с 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
OP Edit2 745 мс
Принятый ответ 522ms
Вышеупомянутая функция 0,2 мс

Другие вопросы по теме