F # System.OutOfMemoryException с рекурсивным вызовом

Question

На самом деле это решение Project Euler Задача 14 в F #.Тем не менее, я сталкиваюсь с исключением System.OutOfMemory при попытке вычислить итерационную последовательность для больших чисел.Как вы можете видеть, я пишу свою рекурсивную функцию с помощью хвостовых вызовов.

У меня возникла проблема со StackOverFlowException, потому что я отлаживал в Visual Studio (которая отключает хвостовые вызовы).Я задокументировал это в другом вопросе .Здесь я работаю в режиме выпуска - но у меня возникают исключения из памяти, когда я запускаю это как консольное приложение (на Windows XP с 4 ГБ оперативной памяти).

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

let E14_interativeSequence x =

  let rec calc acc startNum =
    match startNum with
    | d when d = 1      -> List.rev (d::acc)
    | e when e%2 = 0    -> calc (e::acc) (e/2)
    | _                 -> calc (startNum::acc) (startNum * 3 + 1)

  let maxNum pl=

    let rec maxPairInternal acc pairList =
        match pairList with
        | []        ->  acc
        | x::xs     ->  if (snd x) > (snd acc) then maxPairInternal x xs
                        else maxPairInternal acc xs

    maxPairInternal (0,0) pl
    |> fst

  // if I lower this to like [2..99999] it will work.
  [2..99999] 
  |> List.map (fun n -> (n,(calc [] n)))
  |> List.map (fun pair -> ((fst pair), (List.length (snd pair))))
  |> maxNum
  |> (fun x-> Console.WriteLine(x))

---

РЕДАКТИРОВАТЬ

Учитывая предложениячерез ответы я переписал использовать ленивый список, а также использовать Int64.

#r "FSharp.PowerPack.dll"

let E14_interativeSequence =

  let rec calc acc startNum =
    match startNum with
    | d when d = 1L         -> List.rev (d::acc) |> List.toSeq
    | e when e%2L = 0L      -> calc (e::acc) (e/2L)
    | _                     -> calc (startNum::acc) (startNum * 3L + 1L)

  let maxNum (lazyPairs:LazyList<System.Int64*System.Int64>) =

    let rec maxPairInternal acc (pairs:seq<System.Int64*System.Int64>) =
        match pairs with
        | :? LazyList<System.Int64*System.Int64> as p ->
            match p with
            | LazyList.Cons(x,xs)->  if (snd x) > (snd acc) then maxPairInternal x xs
                                     else maxPairInternal acc xs
            | _                         ->  acc
        | _ -> failwith("not a lazylist of pairs")

    maxPairInternal (0L,0L) lazyPairs
    |> fst

  {2L..999999L}
  |> Seq.map (fun n -> (n,(calc [] n)))
  |> Seq.map (fun pair -> ((fst pair), (Convert.ToInt64(Seq.length (snd pair)))))
  |> LazyList.ofSeq
  |> maxNum

, которая решает проблему.Я также посмотрел бы на решение Инь Чжу, которое лучше, хотя бы.

Answer 1

Как упомянул Брайан, List.* операции здесь неуместны.Они стоят слишком много памяти.

Проблема переполнения стека возникает из другого места.У вас есть два возможных варианта переполнения стека: calc и maxPairInternal.Он должен быть первым, так как второй имеет ту же глубину, что и первый.Тогда проблема сводится к числам, число в задаче 3n+1 может легко перейти к очень большим.Итак, сначала вы получаете переполнение int32, а затем переполнение стека.Вот в чем причина.После смены номера на 64бит, программа работает.

Вот страница моего решения , где вы можете увидеть трюк с памяткой.

open System
let E14_interativeSequence x =

  let rec calc acc startNum =
    match startNum with
    | d when d = 1L      -> List.rev (d::acc)
    | e when e%2L = 0L    -> calc (e::acc) (e/2L)
    | _                 -> calc (startNum::acc) (startNum * 3L + 1L)

  let maxNum pl=

    let rec maxPairInternal acc pairList =
        match pairList with
        | []        ->  acc
        | x::xs     ->  if (snd x) > (snd acc) then maxPairInternal x xs
                        else maxPairInternal acc xs

    maxPairInternal (0L,0) pl
    |> fst

  // if I lower this to like [2..99999] it will work.
  [2L..1000000L] 
  |> Seq.map (fun n -> (n,(calc [] n)))
  |> Seq.maxBy (fun (n, lst) -> List.length lst)
  |> (fun x-> Console.WriteLine(x))

Answer 2

Если вы измените List.map на Seq.map (и переработаете maxPairInternal для итерации по seq), это, вероятно, поможет тоннам. Прямо сейчас вы представляете все данные сразу в гигантской структуре, а затем обрабатываете всю структуру, чтобы получить результат с одним числом. Гораздо лучше сделать это лениво с помощью Seq, просто создать одну строку, сравнить ее со следующей строкой, создать по одной строке за раз и затем отбросить ее.

У меня нет времени, чтобы закодировать мое предложение сейчас, но дайте мне знать, если у вас все еще есть проблемы, и я вернусь к этому.

Answer 3

Хватит пытаться использовать списки везде, это не Haskell! И перестань писать fst pair и snd pair везде, это не Лисп!

Если вам нужно простое решение на F #, вы можете сделать это напрямую, не создавая промежуточных структур данных:

let rec f = function
  | 1L -> 0
  | n when n % 2L = 0L -> 1 + f(n / 2L)
  | n -> 1 + f(3L * n + 1L)

let rec g (li, i) = function
  | 1L -> i
  | n -> g (max (li, i) (f n, n)) (n - 1L)

let euler14 n = g (0, 1L) n

Это займет около 15 секунд на моем нетбуке. Если вы хотите что-то более эффективное по времени, используйте предыдущие результаты через массив:

let rec inside (a : _ array) n =
  if n <= 1L || a.[int n] > 0s then a.[int n] else
    let p =
      if n &&& 1L = 0L then inside a (n >>> 1) else
        let n = 3L*n + 1L
        if n < int64 a.Length then inside a n else outside a n
    a.[int n] <- 1s + p
    1s + p
and outside (a : _ array) n =
  let n = if n &&& 1L = 0L then n >>> 1 else 3L*n + 1L
  1s + if n < int64 a.Length then inside a n else outside a n

let euler14 n =
  let a = Array.create (n+1) 0s
  let a = Array.Parallel.init (n+1) (fun n -> inside a (int64 n))
  let i = Array.findIndex (Array.reduce max a |> (=)) a
  i, a.[i]

Это занимает около 0,2 с на моем нетбуке.

Answer 4

Нашел это, ища Microsoft.FSharp.Core.Operators.Checked.Я только изучаю F #, поэтому я подумал, что приму вызов Project Euler 14.

В нем используется рекурсия, а не хвостовая рекурсия.У меня уходит около 3,1 с, но у меня есть преимущество в том, что я почти понимаю это.

let Collatz (n:int64) = if n % 2L = 0L then n / 2L else n * 3L + 1L

let rec CollatzLength (current:int64) (acc:int) =
    match current with 
    | 1L -> acc
    | _ -> CollatzLength (Collatz current) (acc + 1)

let collatzSeq (max:int64) = 
    seq{
        for i in 1L..max do
            yield i, CollatzLength i 0
    }

let collatz = Seq.toList(collatzSeq 1000000L)

let result, steps = List.maxBy snd collatz