Maneiras de Haskell para o problema 3n + 1

Aqui está um simples problema de programação do SPOJ: http://www.spoj.com/problems/PROBTRES/ .

Basicamente, você é solicitado a produzir o maior ciclo de Collatz para números entre iej. (O ciclo de Collatz de um número $ n $ é o número de etapas para, eventualmente, passar de $ n $ a 1.)

Eu estava procurando uma maneira Haskell de resolver o problema com desempenho comparativo do que o Java ou C ++ (para se encaixar no limite de tempo de execução permitido). Embora uma solução Java simples que memorize a duração do ciclo de qualquer ciclo já calculado funcione, não tive êxito em aplicar a ideia de obter uma solução Haskell.

Eu tentei o Data.Function.Memoize, bem como a técnica de memorização de tempo de registro feita em casa, usando a ideia desta publicação: /programming/3208258/memoization-in-haskell . Infelizmente, a memorização realmente torna o cálculo do ciclo (n) ainda mais lento. Eu acredito que a desaceleração vem do alto do caminho Haskell. (Tentei executar com o código binário compilado, em vez de interpretar.)

Eu também suspeito que simplesmente iterar números de i a j pode ser caro ($ i, j \ le10 ^ 6 $). Então, tentei pré-calcular tudo para a consulta de intervalo, usando a idéia de http://blog.openendings.net/2013/10/range-trees-and-profiling-in-haskell.html . No entanto, isso ainda dá o erro "Tempo limite excedido".

Você pode ajudar a informar um bom programa Haskell competitivo para isso?

Responderei em Scala, porque meu Haskell não é tão recente e as pessoas acreditam que essa é uma questão geral de algoritmo de programação funcional. Vou me ater às estruturas e conceitos de dados que são prontamente transferíveis.

Podemos começar com uma função que gera uma sequência de collatz, que é relativamente direta, exceto pela necessidade de passar o resultado como argumento para torná-lo recursivo:

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)
   }
 }

Na verdade, isso coloca a sequência na ordem inversa, mas é perfeita para o próximo passo, que é armazenar os comprimentos em um mapa:

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)))
}

Você poderia chamar isso com a resposta da primeira etapa, o comprimento inicial e um mapa vazio, como calculateLengths(collatz(22), 1, Map.empty)). É assim que você memoriza o resultado. Agora precisamos modificar collatzpara poder usar isso:

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)
  }
}

Eliminamos a n == 1verificação porque podemos apenas inicializar o mapa com 1 -> 1, mas precisamos adicionar 1os comprimentos que inserimos no mapa calculateLengths. Agora, ele também retorna o comprimento memorizado onde parou de se repetir, que podemos usar para inicializar calculateLengths, como:

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

Agora que temos implementações relativamente eficientes das peças, precisamos encontrar uma maneira de alimentar os resultados do cálculo anterior na entrada do próximo cálculo. Isso é chamado de folde se parece com:

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)

Agora, para encontrar a resposta real, basta filtrar as chaves no mapa entre o intervalo especificado e encontrar o valor máximo, fornecendo um resultado final de:

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
}

No meu REPL para intervalos de tamanho 1000 ou mais, como na entrada de exemplo, a resposta retorna praticamente instantaneamente.

Karl Bielefeld já respondeu bem à pergunta, vou apenas adicionar uma versão Haskell.

Primeiro, uma versão simples e sem memorização do algoritmo básico para mostrar a recursão eficiente:

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)

Isso deve ser quase autoexplicativo.

Eu também vou usar um simples Mappara armazenar os resultados.

-- 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

Sempre podemos procurar nossos resultados finais na loja, portanto, para um único valor, a assinatura é

memoCollatz :: Int -> Store -> Store

Vamos começar com o caso final

memoCollatz 1 store = Map.insert 1 1 store

Sim, podemos adicionar isso de antemão, mas eu não me importo. Próximo caso simples, por favor.

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

Se o valor estiver lá, está. Ainda não fazendo nada.

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

Se o valor não estiver lá, temos que fazer alguma coisa . Vamos colocar em uma função local. Observe como essa parte parece muito próxima da solução "simples", apenas a recursão é um pouco mais complexa.

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

Agora finalmente fazemos algo. Se encontrarmos o valor calculado em store''(nota de rodapé: existem dois marcadores de sintaxe haskell, mas um é feio, o outro fica confuso com o símbolo primo. Essa é a única razão para o duplo primo.), Basta adicionar o novo valor. Mas agora fica interessante. Se não encontrarmos o valor, precisamos calculá-lo e fazer a atualização. Mas já temos funções para ambos! então

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

E agora podemos calcular um único valor com eficiência. Se quisermos calcular vários, apenas passamos a loja através de uma dobra.

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

(É aqui que você pode inicializar o caso 1/1.)

Agora tudo o que precisamos fazer é extrair o máximo. Por enquanto, não pode haver um valor na loja que seja maior que um no intervalo, portanto basta dizer

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

Obviamente, se você quiser calcular vários intervalos e compartilhar a loja entre esses cálculos (as dobras são suas amigas), seria necessário um filtro, mas esse não é o foco principal aqui.