Haskell пути к проблеме 3n + 1

12

Вот простая проблема программирования от 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?

Haskell выглядит великолепно
источник
10
Этот пост мне кажется нормальным. Это алгоритмическая проблема, которая требует правильного проектирования для достижения адекватной производительности. Чего мы на самом деле не хотим, так это вопросов «как исправить неисправный код».
Роберт Харви

Ответы:

7

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

Мы можем начать с функции, которая генерирует последовательность Коллатца, которая относительно проста, за исключением необходимости передавать результат в качестве аргумента, чтобы сделать его рекурсивным:

def collatz(n: Int, result: List[Int] = List()): List[Int] = {
   if (n == 1) {
     1 :: result
   } else if ((n & 1) == 1) {
     collatz(3 * n + 1, n :: result)
   } else {
     collatz(n / 2, n :: result)
   }
 }

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

def calculateLengths(sequence: List[Int], length: Int,
  lengths: Map[Int, Int]): Map[Int, Int] = sequence match {
    case Nil     => lengths
    case x :: xs => calculateLengths(xs, length + 1, lengths + ((x, length)))
}

Вы бы назвали это ответом из первого шага, начальной длиной и пустой картой, например calculateLengths(collatz(22), 1, Map.empty)). Так вы запоминаете результат. Теперь нам нужно изменить, collatzчтобы иметь возможность использовать это:

def collatz(n: Int, lengths: Map[Int, Int], result: List[Int] = List()): (List[Int], Int) = {
  if (lengths contains n) {
     (result, lengths(n))
  } else if ((n & 1) == 1) {
    collatz(3 * n + 1, lengths, n :: result)
  } else {
    collatz(n / 2, lengths, n :: result)
  }
}

Мы исключаем n == 1проверку, потому что мы можем просто инициализировать карту с помощью 1 -> 1, но нам нужно добавить 1к длинам, которые мы помещаем в карту внутри calculateLengths. Теперь он также возвращает запомненную длину, где он прекратил рекурсию, которую мы можем использовать для инициализации calculateLengths, например:

val initialMap = Map(1 -> 1)
val (result, length) = collatz(22, initialMap)
val newMap = calculateLengths(result, lengths, initialMap)

Теперь у нас есть относительно эффективные реализации кусков, нам нужно найти способ подать результаты предыдущего вычисления на вход следующего вычисления. Это называется fold, и выглядит так:

def iteration(lengths: Map[Int, Int], n: Int): Map[Int, Int] = {
  val (result, length) = collatz(n, lengths)
  calculateLengths(result, length, lengths)
}

val lengths = (1 to 10).foldLeft(Map(1 -> 1))(iteration)

Теперь, чтобы найти фактический ответ, нам просто нужно отфильтровать ключи на карте между заданным диапазоном и найти максимальное значение, дающее окончательный результат:

def answer(start: Int, finish: Int): Int = {
  val lengths = (start to finish).foldLeft(Map(1 -> 1))(iteration)
  lengths.filterKeys(x => x >= start && x <= finish).values.max
}

В моем REPL для диапазонов размером 1000 или около того, как в примере ввода, ответ возвращается почти мгновенно.

Карл Билефельдт
источник
3

Карл Билефельд уже хорошо ответил на вопрос, я просто добавлю версию на Haskell.

Сначала простая, не запоминающаяся версия базового алгоритма, демонстрирующая эффективную рекурсию:

simpleCollatz :: Int -> Int -> Int
simpleCollatz count 1 = count + 1
simpleCollatz count n | odd n     = simpleCollatz (count + 1) (3 * n + 1)
                      | otherwise = simpleCollatz (count + 1) (n `div` 2)

Это должно быть почти самоочевидным.

Я тоже буду использовать простой Mapдля хранения результатов.

-- double imports to make the namespace pretty
import           Data.Map  ( Map )
import qualified Data.Map as Map

-- a new name for the memoizer
type Store = Map Int Int

Мы всегда можем посмотреть наши окончательные результаты в магазине, поэтому для одного значения подпись

memoCollatz :: Int -> Store -> Store

Давайте начнем с конца дела

memoCollatz 1 store = Map.insert 1 1 store

Да, мы могли бы добавить это заранее, но мне все равно. Следующий простой случай, пожалуйста.

memoCollatz n store | Just _ <- Map.lookup n store = store

Если значение есть, то оно есть. Все еще ничего не делает.

                    | odd n     = processNext store (3 * n + 1)
                    | otherwise = processNext store (n `div` 2)

Если значение не там, мы должны что- то сделать . Давайте поместим в локальную функцию. Обратите внимание, как эта часть выглядит очень близко к «простому» решению, только рекурсия немного сложнее.

  where processNext store'' next | Just count <- Map.lookup next store''
                                 = Map.insert n (count + 1) store''

Теперь мы наконец-то что-то делаем. Если мы находим вычисленное значение в store''(sidenote: есть два средства подсветки синтаксиса haskell, но один уродлив, другой запутывается в простом символе. Это единственная причина двойного простого.), Мы просто добавляем новый значение. Но теперь это становится интересным. Если мы не найдем значение, мы должны как вычислить его, так и выполнить обновление. Но у нас уже есть функции для обоих! Так

                                | otherwise
                                = processNext (memoCollatz next store'') next

И теперь мы можем эффективно вычислить одно значение. Если мы хотим вычислить несколько, мы просто передаем магазин через сгиб.

collatzRange :: Int -> Int -> Store
collatzRange lower higher = foldr memoCollatz Map.empty [lower..higher]

(Именно здесь вы можете инициализировать случай 1/1.)

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

collatzRangeMax :: Int -> Int -> Int
collatzRangeMax lower higher = maximum $ collatzRange lower higher

Конечно, если вы хотите вычислить несколько диапазонов и разделить хранилище между этими вычислениями (сгибы - ваш друг), вам понадобится фильтр, но здесь это не главное.

MarLinn
источник
1
Для дополнительной скорости, Data.IntMap.Strictследует использовать.
Олат