Проект Эйлер # 211 - проблема эффективности
Я медленно прорабатывал список проблем Project Euler и пришел к той, которую знаю, как решить, но, похоже, не могу (учитывая способ написания моего решения).
Я использую Common Lisp для этого, и мой скрипт работает более 24 часов (что намного превышает их цель в одну минуту).
Для краткости, вот мое решение (это спойлер, но только если у вас чертовски быстрый процессор):
(defun square? (num)
(if (integerp (sqrt num)) T))
(defun factors (num)
(let ((l '()))
(do ((current 1 (1+ current)))
((> current (/ num current)))
(if (= 0 (mod num current))
(if (= current (/ num current))
(setf l (append l (list current)))
(setf l (append l (list current (/ num current)))))))
(sort l #'< )))
(defun o_2 (n)
(reduce #'+ (mapcar (lambda (x) (* x x)) (factors n))))
(defun sum-divisor-squares (limit)
(loop for i from 1 to limit when (square? (o_2 i)) summing i))
(defun euler-211 ()
(sum-divisor-squares 64000000))
Время, необходимое для решения проблемы с использованием меньших, более удобных, тестовых аргументов, кажется, больше, чем экспоненциально ... что является реальной проблемой.
Это заняло:
- 0,007 секунды на решение за 100
- 0,107 секунды на решение для 1000
- 2.020 секунд на решение, чтобы получить 10000
- 56,61 секунды, чтобы собрать 100000
- 1835,385 секунд, чтобы собрать 1000000
- 24+ часа на решение для 64000000
Я действительно пытаюсь понять, какая часть сценария заставляет его так долго работать. Я подумал о том, чтобы запомнить функцию факторов, но я не понимаю, как на самом деле это реализовать.
Для тех, кто хочет взглянуть на саму проблему, вот оно.
Мы будем очень благодарны за любые идеи о том, как сделать эту вещь быстрее.
** извините, если это спойлер для кого-то, этого не должно быть .... но если у вас есть вычислительная мощность, чтобы запустить это в приличное количество времени, вам больше возможностей.
квадрат? неправильно. Common Lisp не указывает, что (sqrt 4) является целым числом 2. Это также может быть float 2.0. Также обратите внимание, что (if (аргумент pred-p) t) совпадает с just (pred-argument) для большинства практических целей.
Ответы 7
Извините, я недостаточно хорошо понимаю LISP, чтобы прочитать ваш ответ. Но мое первое впечатление таково, что временные затраты на решение с использованием грубой силы должны быть:
открытая скобка
sqrt (k), чтобы найти делители k (пробным делением), возвести их в квадрат (постоянное время на фактор) и просуммировать их (постоянное время на фактор). Это σ2 (k), который я назову x.
плюс
не уверен, какова сложность хорошего целочисленного алгоритма квадратного корня, но, конечно, не хуже, чем sqrt (x) (немое пробное умножение). x вполне может быть big-O больше k, поэтому я оставляю за собой суждение здесь, но x, очевидно, ограничен сверху k ^ 3, потому что k имеет не более k делителей, каждый сам по себе не больше k и, следовательно, его квадрат не больше k ^ 2. Я так давно не учился на математике, что понятия не имею, насколько быстро сходится Ньютон-Рафсон, но я подозреваю, что это быстрее, чем sqrt (x), и если все остальное терпит неудачу, двоичная отбивная будет log (x).
закрывающая скобка
умноженное на n (поскольку k находится в диапазоне от 1 до n).
Итак, если ваш алгоритм хуже, чем O (n * sqrt (n ^ 3)) = O (n ^ (5/2)), в случае dumb-sqrt или O (n * (sqrt (n) + log ( n ^ 3)) = O (n ^ 3/2) в случае умного sqrt, я думаю, что что-то пошло не так, что должно быть идентифицировано в алгоритме. На этом этапе я застрял, потому что я не могу отладить ваш LISP .
О, я предположил, что арифметика - это постоянное время для используемых чисел. Это, черт возьми, должно быть для таких маленьких чисел, как 64 миллиона, а куб этого едва ли вписывается в 64-битное целое число без знака. Но даже если ваша реализация LISP делает арифметику хуже, чем O (1), она не должна быть хуже, чем O (log n), поэтому это не сильно повлияет на сложность. Конечно, суперполиномиальной не сделать.
Здесь кто-то приходит и говорит мне, насколько я ошибаюсь.
Ой, я только что посмотрел на ваши фактические данные о сроках. Они не хуже экспоненциальных. Игнорирование первого и последнего значений (потому что малое время не поддается точному измерению и вы еще не закончили, соответственно), умножение n на 10 умножает время не более чем на 30 единиц. 30 составляет примерно 10 ^ 1,5, что примерно соответствует описанному выше грубой силе.
Я думаю, что вы можете решить эту проблему с помощью чего-то вроде простого сита. Но это только мое первое впечатление.
Учитывая источник, более вероятно, что существует какая-то умная математическая связь между сигма-2 (n) и сигма-2 простых множителей n, что делает все это намного, намного быстрее. Конечно, вы правы в том, что расчет простого сита значительно ускоряет поиск факторов.
Я считаю, что ваш алгоритм не самый эффективный из возможных. Подсказка: возможно, вы начали не с той стороны.
редактировать: Я хотел бы добавить, что выбор 64000000 в качестве верхнего предела, вероятно, является способом сообщения о проблеме, который предлагает вам подумать о чем-то лучше.
редактировать: Несколько советов по эффективности:
- вместо
(setf l (append l (...)))
вы можете использовать
(push (...) l)
который деструктивно изменяет ваш список, создавая новую ячейку с вашим значением как car и прежний l как cdr, а затем указывает l на эту ячейку. Это намного быстрее, чем добавление, которое должно проходить по списку один раз. Если вам нужен список в другом порядке, вы можете отменить его после того, как он будет заполнен (но здесь это не требуется).
зачем вы сортируете
l?вы можете сделать
(> current (/ num current))более эффективным, сравнивая его с квадратным корнем из числа (который нужно вычислять только один раз за число).возможно ли найти множители числа более эффективно?
И подсказка по стилю: вы можете указать область действия l в объявлении do:
(do ((l ())
(current 1 (+ current 1)))
((> current (/ num current))
l)
...)
Я бы напал на это, выполнив простое разложение числа (например: 300 = 2 ^ 2 * 3 ^ 1 * 5 ^ 2), что относительно быстро, особенно если вы генерируете это сито. Исходя из этого, относительно просто сгенерировать факторы, повторяя i = 0..2; j = 0..1; k = 0..2, и выполняем 2 ^ i * 3 ^ j * 5 ^ k.
5 3 2 ----- 0 0 0 = 1 0 0 1 = 2 0 0 2 = 4 0 1 0 = 3 0 1 1 = 6 0 1 2 = 12 1 0 0 = 5 1 0 1 = 10 1 0 2 = 20 1 1 0 = 15 1 1 1 = 30 1 1 2 = 60 2 0 0 = 25 2 0 1 = 50 2 0 2 = 100 2 1 0 = 75 2 1 1 = 150 2 1 2 = 300
Это может быть недостаточно быстро
Это определенно достаточно быстро, и это общее решение, которое работает для многих проблем ... вместо этого должен быть принятый ответ ;-)
Вот решение, учитывая дух [проекта] Эйлера. [Предупреждение: спойлер. Я старался делать подсказки медленно, чтобы вы могли прочитать только часть ответа и подумать самостоятельно, если хотите. :)]
Когда вы сталкиваетесь с проблемой, связанной с числами, одна хорошая стратегия (как вы, вероятно, уже знаете из решения 210 задач проекта Эйлера) - это посмотреть на небольшие примеры, найти закономерность и доказать это. [Последняя часть может быть необязательной в зависимости от вашего отношения к математике ;-)]
Однако в этой задаче рассмотрение небольших примеров - для n = 1,2,3,4, ..., вероятно, не даст вам никаких подсказок. Но есть и другой смысл «небольших примеров» при решении теоретико-числовых задач, который вы, вероятно, уже знаете, - простые числа являются строительными блоками натуральных чисел, поэтому начните с простых чисел.
Для простого числа p его единственными делителями являются 1 и p, поэтому сумма квадратов его делителей равна 1 + p2.
Для степени простого pk его единственные делители равны 1, p, p2,… pk, поэтому сумма квадратов его делителей равна 1 + p + p2 +… + pk = (pk+1-1) / (p-1).
Это был самый простой случай: вы решили задачу для всех чисел с одним простым множителем.
Пока ничего особенного. Теперь предположим, что у вас есть число n, которое имеет простые множители два, скажем, n = pq. Тогда его множители равны 1, p, q и pq, поэтому сумма квадратов его делителей равна 1 + p2 + q2 + p2q2 = (1 + p2) (1 + q2).
А как насчет n = paqb? Какова сумма квадратов его множителей?
[............................ Опасно читать под этой строкой ............... ....]
Это ∑0≤c≤a, 0≤d≤b (pcqd) 2 = ((pa+1-1) / (p-1)) ((qb+1-1) / (q-1)).
Это должно дать вам подсказку, как о том, каков ответ, так и о том, как его доказать: сумма делителей n - это просто произведение (ответа) для каждой из степеней простого числа в его факторизации, поэтому все, что вам нужно do - это разложить на множители 64000000 (что очень легко сделать даже в уме :-)) и умножить ответ для каждого (= обоих, потому что единственными простыми числами являются 2 и 5) его простых степеней.
Это решает проблему проекта Эйлера; теперь мораль убрать из этого.
Более общий факт здесь касается мультипликативные функции - функций на натуральных числах, таких что f (mn) = f (m) f (n) всякий раз, когда gcd (m, n) = 1, то есть m и n не имеют общих простых множителей. . Если у вас есть такая функция, значение функции для определенного числа полностью определяется ее значениями при простых степенях (можете ли вы это доказать?)
Немного более сложный факт, который вы можете попытаться доказать [это не сложно для который], заключается в следующем: если у вас есть мультипликативная функция f [здесь f (n) = n2], и вы определяете функцию F как F (n) = ∑d divides nf (d), (как и здесь), тогда F (n) также является мультипликативной функцией.
[На самом деле что-то очень красивое истинно, но пока не смотрите на него, и, вероятно, он вам никогда не понадобится. :-)]
Если честно, я не пробовал 210, я просто выполнил 67. Это привлекло мое внимание, поэтому я попробовал. Но спасибо за понимание того, как сделать это более эффективно.
Формула обращения Мёбиуса очень и очень красива; к сожалению, это также очень и очень сложно интуитивно понять. Это было рассмотрено на моем вводном курсе теории чисел, но менее половины студентов смогли правильно применить его, даже когда им давали подсказки. Иногда мне тоже кажется, что это темная магия. :)
"Для простой степени pk ее единственными делителями являются 1, p, p2,… pk, поэтому сумма квадратов ее делителей равна 1 + p + p2 +… + pk = (pk + 1-1) / (p- 1) ". В приведенном выше утверждении есть опечатка, должно быть "... поэтому сумма квадратов его делителей равна 1 + p ^ 2 + p ^ 2 ^ 2 + p ^ 3 ^ 2 + ... + pk ^ 2 = (pk ^ (2 + 1) -1) / (pk-1) ".
Извините, должно быть "1 + p ^ 2 + p ^ 2 ^ 2 + p ^ 3 ^ 2 + ... + pk ^ 2 = (p (k + 1) ^ 2-1) / (p ^ 2-1 ) ". Но мне действительно интересно, как это выводится ... Ура.
Я переработал программу с некоторыми заметками, взятыми из комментариев здесь. Функция 'Factors' теперь немного более эффективна, и мне также пришлось изменить функцию σ_ (2) (n), чтобы принять новый вывод.
'факторы' пошли от вывода вроде:
$ (factors 10) => (1 2 5 10)
чтобы иметь такой как
$ (factors 10) => ((2 5) (1 10))
Доработанная функция выглядит так:
(defun o_2 (n)
"sum of squares of divisors"
(reduce #'+ (mapcar (lambda (x) (* x x)) (reduce #'append (factors n)))))
После скромных переписываний, которые я сделал, я сэкономил всего около 7 секунд в расчете на 100000.
Похоже, мне придется встать с ума и написать более прямой подход.
Вам не нужно; вы можете сделать, как сказал FryGuy: сначала напишите функцию простых множителей, которая выполняет (простые множители 64000000) => (2 2 2 2 2 2 2 2 2 2 2 2 5 5 5 5 5 5), затем сгенерируйте список факторы с использованием, которые работают на простые множители. Это должно помочь вам и в других проблемах Project Euler.
Умный трюк, которого вам не хватает, заключается в том, что вам вообще не нужно множить числа Сколько чисел от 1 до N кратно 1? N Сколько чисел от 1 до N кратно 2? N / 2
Уловка состоит в том, чтобы суммировать множители каждого числа в списке. Для 1 добавьте 1 ^ 2 к каждому числу в списке. Для 2 прибавьте 2 ^ 2 к каждому другому числу. Для 3 прибавьте 3 ^ 2 к каждому третьему числу.
Не проверяйте делимость вообще. В конце вы должны проверить, является ли сумма идеальным квадратом, и все. В C++ это сработало для меня за 58 секунд.
Ваши тайминги увеличиваются примерно геометрически с увеличением числа. Приблизительное значение составляет 0,00001 * n ^ (1,36). Это означает, что 64M займет около 4,6 дней.