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

Question

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

У меня возникла проблема с StackOverFlowException, потому что я отлаживал визуальную студию (которая отключает хвостовые вызовы). Я зарегистрировал это in another question. Здесь я запускаюсь в режиме выпуска, но я получаю исключения из памяти, когда запускаю это как консольное приложение (на 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)) 

---

EDIT

Учитывая предложения через ответы, я переписал использовать ленивый список, а также использовать 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.* здесь не уместны. Они стоят слишком много памяти.

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

Here is my solution page, где вы можете увидеть мемофильный трюк.

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.2s на моем нетбуке.

Answer 4

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

Используется рекурсия, но не хвостовая рекурсия. Занимает около 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