Функция Haskell, занимающая много времени для обработки

Question

Я делаю вопрос 12 эйлера проекта, где должен найти первый номер треугольника с 501 делителями. Поэтому я взломал это с помощью Haskell:

divS n = [ x | x <- [1..(n)], n `rem` x == 0 ] 
tri n = (n* (n+1)) `div` 2 
divL n = length (divS (tri n)) 
answer = [ x | x <- [100..] , 501 == (divL x)] 

Первая функция находит делители числа.

Вторая функция вычисляет п-й номер треугольника

3-я функция находит длину списка, которые являются делителями треугольника числа

4-функция должна возвращать значение числа треугольника, который имеет 501 делителей.

Но пока это работает некоторое время, не возвращая результата. Является ли ответ очень большим или мне нужна какая-то серьезная оптимизация, чтобы сделать эту работу в реалистичное время?

Answer 1

Вы должны использовать свойства функции делителей: http://en.wikipedia.org/wiki/Divisor_function

Обратите внимание, что п и п + 1 всегда взаимно просты, так что вы можете получить д (п * (п + 1)/2) путем умножения ранее вычисленные значения.

Answer 2

Некоторые советы по оптимизации:

• проверки для делителей между 1 и SQRT (п). Я обещаю, что вы не найдете ничего выше этого предела (кроме самого номера).
• не создавайте список делителей и подсчитывайте список, но считайте их напрямую.

Answer 3

Вероятно, скорее всего простое умножение числа, а затем использование факторизации для нахождения делителей, чем использование пробного деления со всеми числами < = sqrt (n).

Sieve of Eratosthenes - классический способ нахождения простых чисел, которые могут быть слегка изменены, чтобы найти количество делителей каждого натурального числа. Вместо того, чтобы просто маркировать каждый не-простой как «не простой», вы могли бы составить список всех простых чисел, делящих каждый номер. Затем вы можете использовать эти простые числа, чтобы вычислить полный набор делителей или просто их число, поскольку это все, что вам нужно.

Другим вариантом будет отметить не только кратность простых чисел, но и кратность всех натуральных чисел. Затем вы можете просто использовать счетчик, чтобы отслеживать количество делителей для каждого номера.

Вы также можете проверить The Genuine Sieve of Eratosthenes, что объясняет, почему пробное деление намного медленнее, чем реальное сито.

Последнее, вы должны внимательно изучить различные типы массивов в Haskell. Я думаю, что, возможно, проще использовать монаду ST для реализации решета, но может быть возможно достичь правильной сложности, используя accumArray, если вы можете убедиться, что ваша функция обновления является строгой. Мне никогда не удавалось заставить это работать, так что вы сами здесь.

Answer 4

Если вы использовали C вместо Haskell, ваша функция все равно займет много времени.

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

Если вы хотите, я могу портить проблему, поделившись своим решением.

Сейчас я дам вам свой код верхнего уровня:

main = 
    print . 
    head . filter ((> 500) . length . divisors) . 
    map (figureNum 3) $ [1..] 

алгоритмическая улучшение заключается в функции divisors. Вы можете улучшить его, используя предложение rawicki, но это уже занимает менее 100 мс.