Вот простая проблема программирования от SPOJ: http://www.spoj.com/problems/PROBTRES/ .
По сути, вас просят вывести самый большой цикл Коллатца для чисел от i до j. (Цикл Коллатца с числом $ n $ - это число шагов, которые в итоге получатся от $ n $ до 1.)
Я искал способ Haskell для решения проблемы со сравнительной производительностью по сравнению с Java или C ++ (чтобы соответствовать допустимому пределу времени выполнения). Хотя простое Java-решение, которое запоминает продолжительность циклов любых уже вычисленных циклов, будет работать, мне не удалось применить идею для получения решения на Haskell.
Я попробовал Data.Function.Memoize, а также самодельную технику запоминания времени регистрации, используя идею из этого поста: /programming/3208258/memoization-in-haskell . К сожалению, на самом деле запоминание делает вычисление цикла (n) еще медленнее. Я полагаю, что замедление происходит из-за накладных расходов пути Хаскелла. (Я попытался запустить скомпилированный двоичный код вместо интерпретации.)
Я также подозреваю, что простая итерация чисел от i до j может быть дорогой ($ i, j \ le10 ^ 6 $). Поэтому я даже попытался предварительно вычислить все для запроса диапазона, используя идею из http://blog.openendings.net/2013/10/range-trees-and-profiling-in-haskell.html . Тем не менее, это все еще дает ошибку «Превышение лимита времени».
Можете ли вы помочь информировать об этом аккуратную конкурентоспособную программу на Haskell?
источник
Ответы:
Я отвечу на Scala, потому что мой Haskell не такой свежий, и поэтому люди поверят, что это общий вопрос алгоритма функционального программирования. Я буду придерживаться структур данных и концепций, которые легко переносимы.
Мы можем начать с функции, которая генерирует последовательность Коллатца, которая относительно проста, за исключением необходимости передавать результат в качестве аргумента, чтобы сделать его рекурсивным:
Это на самом деле помещает последовательность в обратном порядке, но это идеально подходит для нашего следующего шага, который заключается в сохранении длин на карте:
Вы бы назвали это ответом из первого шага, начальной длиной и пустой картой, например
calculateLengths(collatz(22), 1, Map.empty))
. Так вы запоминаете результат. Теперь нам нужно изменить,collatz
чтобы иметь возможность использовать это:Мы исключаем
n == 1
проверку, потому что мы можем просто инициализировать карту с помощью1 -> 1
, но нам нужно добавить1
к длинам, которые мы помещаем в карту внутриcalculateLengths
. Теперь он также возвращает запомненную длину, где он прекратил рекурсию, которую мы можем использовать для инициализацииcalculateLengths
, например:Теперь у нас есть относительно эффективные реализации кусков, нам нужно найти способ подать результаты предыдущего вычисления на вход следующего вычисления. Это называется
fold
, и выглядит так:Теперь, чтобы найти фактический ответ, нам просто нужно отфильтровать ключи на карте между заданным диапазоном и найти максимальное значение, дающее окончательный результат:
В моем REPL для диапазонов размером 1000 или около того, как в примере ввода, ответ возвращается почти мгновенно.
источник
Карл Билефельд уже хорошо ответил на вопрос, я просто добавлю версию на Haskell.
Сначала простая, не запоминающаяся версия базового алгоритма, демонстрирующая эффективную рекурсию:
Это должно быть почти самоочевидным.
Я тоже буду использовать простой
Map
для хранения результатов.Мы всегда можем посмотреть наши окончательные результаты в магазине, поэтому для одного значения подпись
Давайте начнем с конца дела
Да, мы могли бы добавить это заранее, но мне все равно. Следующий простой случай, пожалуйста.
Если значение есть, то оно есть. Все еще ничего не делает.
Если значение не там, мы должны что- то сделать . Давайте поместим в локальную функцию. Обратите внимание, как эта часть выглядит очень близко к «простому» решению, только рекурсия немного сложнее.
Теперь мы наконец-то что-то делаем. Если мы находим вычисленное значение в
store''
(sidenote: есть два средства подсветки синтаксиса haskell, но один уродлив, другой запутывается в простом символе. Это единственная причина двойного простого.), Мы просто добавляем новый значение. Но теперь это становится интересным. Если мы не найдем значение, мы должны как вычислить его, так и выполнить обновление. Но у нас уже есть функции для обоих! ТакИ теперь мы можем эффективно вычислить одно значение. Если мы хотим вычислить несколько, мы просто передаем магазин через сгиб.
(Именно здесь вы можете инициализировать случай 1/1.)
Теперь все, что нам нужно сделать, это извлечь максимум. На данный момент в магазине не может быть значения, превышающего единицу в диапазоне, поэтому достаточно сказать,
Конечно, если вы хотите вычислить несколько диапазонов и разделить хранилище между этими вычислениями (сгибы - ваш друг), вам понадобится фильтр, но здесь это не главное.
источник
Data.IntMap.Strict
следует использовать.