Haskell explique le problème 3n + 1

Voici un problème de programmation simple de SPOJ: http://www.spoj.com/problems/PROBTRES/ .

Fondamentalement, vous êtes invité à sortir le plus grand cycle de Collatz pour les nombres entre i et j. (Le cycle de Collatz d'un nombre $ n $ est le nombre d'étapes pour éventuellement passer de $ n $ à 1.)

Je cherchais un moyen Haskell pour résoudre le problème avec des performances comparatives à celles de Java ou C ++ (afin de s'adapter à la limite d'exécution autorisée). Bien qu'une solution Java simple qui mémorise la durée des cycles déjà calculés fonctionnera, je n'ai pas réussi à appliquer l'idée d'obtenir une solution Haskell.

J'ai essayé le Data.Function.Memoize, ainsi que la technique de mémorisation du temps de connexion brassée à la maison en utilisant l'idée de ce post: /programming/3208258/memoization-in-haskell . Malheureusement, la mémorisation rend en fait le calcul du cycle (n) encore plus lent. Je crois que le ralentissement vient des frais généraux de la voie Haskell. (J'ai essayé de courir avec le code binaire compilé, au lieu d'interpréter.)

Je soupçonne également que la simple itération des nombres de i à j peut être coûteuse ($ i, j \ le10 ^ 6 $). J'ai donc même essayé de tout précalculer pour la requête de plage, en utilisant l'idée de http://blog.openendings.net/2013/10/range-trees-and-profiling-in-haskell.html . Cependant, cela donne toujours l'erreur "Time Limit Exceeding".

Pouvez-vous aider à informer un programme Haskell compétitif soigné pour cela?

Je répondrai en Scala, parce que mon Haskell n'est pas aussi frais, et donc les gens vont croire que c'est une question d'algorithme de programmation fonctionnelle générale. Je m'en tiendrai aux structures de données et aux concepts qui sont facilement transférables.

Nous pouvons commencer avec une fonction qui génère une séquence collatz, qui est relativement simple, sauf pour avoir besoin de passer le résultat en argument pour le rendre récursif:

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

Cela met en fait la séquence dans l'ordre inverse, mais c'est parfait pour notre prochaine étape, qui est de stocker les longueurs dans une carte:

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

Vous appelleriez cela avec la réponse de la première étape, la longueur initiale et une carte vide, comme calculateLengths(collatz(22), 1, Map.empty)). C'est ainsi que vous mémorisez le résultat. Maintenant, nous devons modifier collatzpour pouvoir utiliser ceci:

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

Nous éliminons le n == 1contrôle car nous pouvons simplement initialiser la carte avec 1 -> 1, mais nous devons ajouter 1aux longueurs que nous mettons dans la carte à l'intérieur calculateLengths. Il retourne maintenant également la longueur mémorisée où il a cessé de se reproduire, que nous pouvons utiliser pour initialiser calculateLengths, comme:

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

Maintenant que nous avons des implémentations relativement efficaces des pièces, nous devons trouver un moyen d'introduire les résultats du calcul précédent dans l'entrée du calcul suivant. Cela s'appelle un fold, et ressemble à:

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)

Maintenant, pour trouver la réponse réelle, il nous suffit de filtrer les clés de la carte entre la plage donnée et de trouver la valeur maximale, donnant un résultat 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
}

Dans mon REPL pour les plages de taille 1000 ou plus, comme l'exemple d'entrée, la réponse revient à peu près instantanément.

Karl Bielefeld a déjà bien répondu à la question, je vais juste ajouter une version Haskell.

D'abord une version simple et non mémorisante de l'algorithme de base pour montrer la récursivité efficace:

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)

Cela devrait être presque explicite.

Moi aussi, j'utiliserai un simple Mappour stocker les résultats.

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

Nous pouvons toujours rechercher nos résultats finaux dans le magasin, donc pour une seule valeur, la signature est

memoCollatz :: Int -> Store -> Store

Commençons par le cas final

memoCollatz 1 store = Map.insert 1 1 store

Oui, nous pourrions ajouter cela à l'avance, mais je m'en fiche. Prochain cas simple s'il vous plaît.

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

Si la valeur est là, elle l'est. Je ne fais toujours rien.

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

Si la valeur n'est pas là, nous devons faire quelque chose . Mettons le dans une fonction locale. Remarquez à quoi ressemble cette partie très proche de la solution "simple", seule la récursivité est un peu plus complexe.

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

Maintenant, nous faisons enfin quelque chose. Si nous trouvons la valeur calculée dans le store''(sidenote: il y a deux surligneurs de syntaxe haskell, mais l'un est moche, l'autre est confus par le symbole premier. C'est la seule raison du double prime.), Nous ajoutons simplement le nouveau valeur. Mais maintenant ça devient intéressant. Si nous ne trouvons pas la valeur, nous devons à la fois la calculer et faire la mise à jour. Mais nous avons déjà des fonctions pour les deux! Donc

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

Et maintenant, nous pouvons calculer une seule valeur efficacement. Si nous voulons en calculer plusieurs, nous transmettons simplement le magasin via un pli.

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

(C'est ici que vous pouvez initialiser le cas 1/1.)

Il ne nous reste plus qu'à extraire le maximum. Pour l'instant, il ne peut pas y avoir de valeur dans le magasin supérieure à une dans la gamme, il suffit donc de dire

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

Bien sûr, si vous souhaitez calculer plusieurs plages et partager le magasin entre ces calculs également (les plis sont votre ami), vous auriez besoin d'un filtre, mais ce n'est pas l'objectif principal ici.