Euler № 211 проекта - проблема эффективности

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

править: Я хотел бы добавить, что при выборе 64000000, поскольку верхний предел вероятен проблемный плакат способ сказать Вам думать о чем-то лучше.

править: Несколько подсказок эффективности:

• вместо

(setf l (append l (...)))

можно использовать

(push (...) l)

который пагубно изменяет Ваш список путем концентрирования новой ячейки со значением как автомобиль и первый l как CDR, затем указывает l к этой ячейке. Это намного быстрее, чем добавление, которое должно пересечь список однажды каждый. При необходимости в списке в другом порядке Вы можете nreverse он после того, как это завершено (но это не нужно здесь).

• почему Вы сортируете l?

• можно сделать (> current (/ num current)) более эффективный путем сравнения квадратному корню цифры вместо этого (который только должен быть вычислен однажды на цифру).

• возможно, возможно найти факторы числа более эффективно?

И подсказка стиля: можно поместить объем l в делают объявление:

(do ((l ())
     (current 1 (+ current 1)))
    ((> current (/ num current))
     l)
  ...)

Умный прием, который Вы пропускаете, - то, что Вы не должны учитывать числа вообще Сколько чисел от 1.. N являются кратными числами 1? N, Сколько чисел от 1.. N являются кратными числами 2? N/2

Прием должен суммировать факторы каждого числа в списке. Для 1, добавьте 1^2 к каждому числу в списке. Для 2, добавьте 2^2 к любому числу. Для 3, добавьте 3^2 к каждому 3-му числу.

Не проверяйте на делимость вообще. В конце действительно необходимо проверить, является ли сумма полным квадратом, и вот именно. В C++ это работало за 58 секунд на меня.

Я напал бы на это путем выполнения главной факторизации числа (например: 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

Это не могло бы быть достаточно быстро

Извините, я не понимаю LISP достаточно хорошо для чтения ответа. Но мое первое впечатление - то, что стоимость времени решения для грубой силы должна быть:

открытая скобка

sqrt (k), чтобы найти делители k (испытательным подразделением), квадрат каждый (постоянное время на фактор), и суммировать их (постоянное время на фактор). Это - _σ2 (k), который я назову x.

плюс

не уверенный, какова сложность хорошего целочисленного алгоритма квадратного корня, но конечно не хуже, чем sqrt (x) (немое испытательное умножение). x мог бы хорошо быть большой-O больше, чем k, таким образом, я резервирую решение здесь, но x, очевидно, ограничен выше k^3, потому что k имеет в большинстве k делителей, каждый сам не больше, чем k и следовательно его квадрат, не больше, чем k^2. Это было таким длинным начиная с моего градуса математики, что я понятия не имею, как быстрый Ньютон-Raphson сходится, но я подозреваю, что это быстрее, чем sqrt (x), и если все остальное перестало работать, поиск делением пополам является журналом (x).

закрывающая квадратная скобка

умноженный на n (поскольку k располагается 1.. n).

Таким образом, если Ваш алгоритм хуже, чем O (n * sqrt (n^3)) = O (n ^ (5/2)) в немом-sqrt случае или O (n * (sqrt (n) + журнал (n^3)) = O (n ^ 3/2) в умном-sqrt случае, я думаю, что что-то пошло не так, как надо, который должен идентифицироваться в алгоритме. В этой точке я застреваю, потому что я не могу отладить Ваш LISP.

О, я предположил, что арифметика является постоянно-разовой для используемых чисел. Это чинит, хорошо должны быть для чисел всего 64 миллиона, и куб этого помещается в целое число без знака на 64 бита, едва. Но даже если Ваша реализация LISP делает арифметику хуже, чем O (1), это не должно быть хуже, чем O (зарегистрируйте n), таким образом, это не будет иметь большого влияния на сложности. Конечно, не сделает это супермногочленом.

Это - то, где кто-то приезжает и говорит мне, как неправильно я.

Ой, я просто посмотрел на Ваши фактические фигуры синхронизации. Они не хуже, чем экспоненциал. Игнорирование первых и последних значений (потому что маленькие времена не точно измеримы и Вы не закончили, соответственно), умножаясь n на 10 умножает время на не больше, чем с 30 выходами. 30 о 10^1.5, который является о прямо для грубой силы, как описано выше.

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

Я переделал программу с некоторыми заметками, сделанными из комментариев здесь. Функция 'факторов' теперь очень немного более эффективна, и я также должен был изменить σ _ (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 секунд в вычислении для 100 000.

Похож я оказываюсь перед необходимостью выходить задницы и писать более прямой подход.