Drogi Haskella do problemu 3n + 1

Oto prosty problem programistyczny SPOJ: http://www.spoj.com/problems/PROBTRES/ .

Zasadniczo zostaniesz poproszony o podanie największego cyklu Collatza dla liczb między i i j. (Cykl Collatz liczby $ n $ to liczba kroków, które ostatecznie można uzyskać z $ n $ do 1.)

Szukałem sposobu Haskell, aby rozwiązać problem z wydajnością porównawczą niż w Javie lub C ++ (tak, aby pasował do dozwolonego limitu czasu działania). Chociaż proste rozwiązanie Java, które zapamiętuje długość każdego już obliczonego cyklu, będzie działać, nie udało mi się zastosować pomysłu uzyskania rozwiązania Haskell.

Wypróbowałem Data.Function.Memoize, a także technikę zapamiętywania czasu zapisanego w dzienniku domowym, korzystając z pomysłu z tego postu: /programming/3208258/memoization-in-haskell . Niestety zapamiętywanie powoduje, że obliczenia cyklu (n) są jeszcze wolniejsze. Uważam, że spowolnienie pochodzi z górnej części drogi Haskell. (Próbowałem uruchomić ze skompilowanym kodem binarnym, zamiast interpretować.)

Podejrzewam również, że zwykłe iterowanie liczb od i do j może być kosztowne ($ i, j \ le10 ^ 6 $). Próbowałem nawet wstępnie obliczyć wszystko dla zapytania o zakres, używając pomysłu z http://blog.openendings.net/2013/10/range-trees-and-profiling-in-haskell.html . Nadal jednak pojawia się błąd „Przekroczenie limitu czasu”.

Czy możesz pomóc w poinformowaniu o tym porządnego konkurencyjnego programu Haskell?

Odpowiem w Scali, ponieważ mój Haskell nie jest tak świeży, więc ludzie uwierzą, że jest to ogólne pytanie dotyczące algorytmu programowania funkcjonalnego. Będę trzymać się struktur danych i pojęć, które można łatwo przenosić.

Możemy zacząć od funkcji, która generuje sekwencję collatz, która jest względnie prosta, z wyjątkiem konieczności przekazania wyniku jako argumentu, aby rekursywnie się kończył:

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

To faktycznie ustawia sekwencję w odwrotnej kolejności, ale jest to idealne rozwiązanie dla naszego następnego kroku, który polega na zapisaniu długości na mapie:

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

Można to nazwać odpowiedzią z pierwszego kroku, początkową długością i pustą mapą calculateLengths(collatz(22), 1, Map.empty)). W ten sposób zapamiętasz wynik. Teraz musimy zmodyfikować, collatzaby móc użyć tego:

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

Eliminujemy n == 1sprawdzenie, ponieważ możemy po prostu zainicjować mapę 1 -> 1, ale musimy dodać 1do długości, które umieszczamy na mapie calculateLengths. Teraz zwraca również zapamiętaną długość, w której przestał się powtarzać, którą możemy użyć do zainicjowania calculateLengths, na przykład:

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

Teraz mamy stosunkowo wydajne implementacje elementów, musimy znaleźć sposób, aby wprowadzić wyniki poprzednich obliczeń do danych wejściowych następnego obliczenia. Nazywa się to a foldi wygląda następująco:

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)

Teraz, aby znaleźć rzeczywistą odpowiedź, musimy tylko przefiltrować klucze na mapie między podanym zakresem i znaleźć maksymalną wartość, dając końcowy wynik:

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
}

W mojej REPL dla zakresów wielkości około 1000, podobnie jak przykładowe dane wejściowe, odpowiedź zwraca się niemal natychmiast.

Karl Bielefeld już dobrze odpowiedział na pytanie, dodam tylko wersję Haskell.

Najpierw prosta, niepamiętująca wersja podstawowego algorytmu, aby pokazać efektywną rekurencję:

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)

To powinno być prawie oczywiste.

Ja również użyję prostego Mapdo przechowywania wyników.

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

Zawsze możemy sprawdzić nasze ostateczne wyniki w sklepie, więc dla jednej wartości jest to podpis

memoCollatz :: Int -> Store -> Store

Zacznijmy od przypadku końcowego

memoCollatz 1 store = Map.insert 1 1 store

Tak, moglibyśmy to dodać wcześniej, ale mnie to nie obchodzi. Proszę o następną prostą skrzynkę.

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

Jeśli wartość istnieje, to jest. Nadal nic nie robię.

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

Jeśli wartości nie ma, musimy coś zrobić . Ustawmy funkcję lokalną. Zauważ, że ta część wygląda bardzo blisko „prostego” rozwiązania, tylko rekurencja jest nieco bardziej złożona.

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

Teraz wreszcie coś robimy. Jeśli znajdziemy obliczoną wartość w store''(sidenote: istnieją dwa znaczniki składni haskell, ale jeden jest brzydki, drugi jest zdezorientowany przez pierwszy symbol. To jedyny powód podwójnej liczby pierwszej)., Po prostu dodajemy nowy wartość. Ale teraz robi się ciekawie. Jeśli nie znajdziemy wartości, musimy ją obliczyć i wykonać aktualizację. Ale mamy już funkcje dla obu! Więc

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

A teraz możemy efektywnie obliczyć jedną wartość. Jeśli chcemy obliczyć kilka, po prostu przekazujemy sklep przez fold.

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

(Tutaj możesz zainicjować przypadek 1/1.)

Teraz wszystko, co musimy zrobić, to wyodrębnić maksimum. Na razie nie może być w sklepie wartości wyższej niż jedna w zakresie, więc wystarczy powiedzieć

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

Oczywiście, jeśli chcesz obliczyć kilka zakresów i udostępnić sklep również dla tych obliczeń (foldy są twoim przyjacielem), potrzebujesz filtra, ale to nie jest tutaj główny cel.