Есть ли способ оптимизировать эту программу в Haskell?

Question

Я занимаюсь проектом Вопрос Эйлера 224 . И вычеркнул этот список понимания в Haskell:

prob39 = length [ d | d <- [1..75000000], c <- [1..37500000], b <-[1..c], a <- [1..b], a+b+c == d, a^2 + b^2 == (c^2 -1)]

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

РЕДАКТИРОВАТЬ: мне также неясно определение «интегральной длины», означает ли это, что длина стороны имеет величину, которая попадает в положительный набор целых чисел, то есть: 1,2,3,4,5 .. .?

Answer 1

Мой Haskell не удивителен, но я думаю, что это будет n ^ 5, как написано.

Похоже, что вы говорите для каждого n от 1 до 75 миллионов, проверьте каждый «едва тупой» треугольник с периметром, меньшим или равным 75 миллионам, чтобы увидеть, имеет ли он периметр n.

Также я не уверен, достаточно ли умны списки для того, чтобы перестать искать, если текущее значение c ^ 2 -1 больше, чем ^ 2 + b ^ 2.

Простой рефакторинг должен быть

prob39 = length [ (a, b, c) | c <- [1..37500000], b <-[1..c], a <- [1..b], a^2 + b^2 == (c^2 -1), (a + b + c) <= 75000000]

Вы можете сделать это лучше, но это в буквальном смысле должно быть в 75 миллионов раз быстрее.

Менее уверен в этом рефакторинге, но он также должен значительно ускорить процесс:

prob39 = length [ (a, b, c) | a <- [1..25000000], b <-[a..(75000000 - 2*a)], c <- [b..(75000000 - a - b)], a^2 + b^2 == (c^2 -1)]

Синтаксис может быть не на 100%. Идея состоит в том, что а может быть только от 1 до 25 миллионов (так как a <= b <= c и a + b + c <= 75 миллионов). b может быть только между a и на полпути от a до 75 миллионов (поскольку b <= c), а c может быть только от b до 75 миллионов - (a + b), в противном случае периметр будет превышать 75 миллионов. </p>

Редактировать: обновленные фрагменты кода, там было несколько ошибок.

Еще одно быстрое предложение: вы можете заменить c <- [b .. (75000000 - a - b)] на что-то вроде c <- [b..min ((75000000 - a - b), sqrt ( a <em>a + b b) + 1)]. Нет необходимости проверять любые значения c, превышающие потолок квадратного корня из (a ^ 2 + b ^ 2). Не могу вспомнить, если это правильные имена функций min / sqrt в haskell.

Получив ОКР, у меня есть еще пара предложений.

1) вы можете установить верхнюю границу b как минимум текущей верхней границы и a ^ 2 * 2 + 1. Это основано на принципе, что (x + 1) ^ 2 - x ^ 2 = 2x + 1. b не может быть намного больше, чем a, поэтому мы можем гарантировать, что (a ^ 2) + (b ^ 2) <(b + 1) ^ 2. </p>

2) установите нижнюю границу c равной максимуму b + 1 и floor (sqrt (a ^ 2 + b ^ 2) - 1). Как и верхний предел на C, нет необходимости проверять значения, которые не могут быть правильными.

Answer 2

Вместе с предложениями, данными @patros. Я хотел бы поделиться своими наблюдениями по этой проблеме.

Если мы напечатаем значения a, b и c для некоторого периметра, скажем, 100000, то мы можем заметить, что a и b всегда принимают четные значения, а c всегда принимают нечетные значения. Поэтому, если мы оптимизируем наш код с этими ограничениями, то почти половина проверки может быть пропущена.