f# - pilas - colas en c ejemplos

Evitar el desbordamiento de pila(con F#secuencias infinitas de secuencias)

Question

Tengo este "código de aprendizaje" que escribí para el morris seq in f # que sufre un desbordamiento de pila que no sé cómo evitar. "morris" devuelve una secuencia infinita de secuencias "ver y decir" (es decir, {{1}, {1,1}, {2,1}, {1,2,1,1}, {1,1,1 , 2,2,1}, {3,1,2,2,1,1}, ...}).

    let printList l =
        Seq.iter (fun n -> printf "%i" n) l
        printfn ""

    let rec morris s = 
        let next str = seq {
            let cnt = ref 1  // Stack overflow is below when enumerating
            for cur in [|0|] |> Seq.append str |> Seq.windowed 2 do
                if cur.[0] <> cur.[1] then
                    yield!( [!cnt ; cur.[0]] )
                    cnt := 0
                incr cnt
        }
        seq {
        yield s
        yield! morris (next s) // tail recursion, no stack overflow
        }

    // "main"
    // Print the nth iteration
    let _ =  [1] |> morris |> Seq.nth 3125 |> printList 

Puede eliminar la enésima itión usando la secuencia número 2, pero solo puede llegar muy lejos antes de llegar a un desbordamiento de pila. La única parte de la recursión que tengo es la de la cola y, en esencia, construye un conjunto vinculado de enumeradores. Ahí no es donde está el problema. Es cuando se llama "enum" en la secuencia 4000a. Tenga en cuenta que con F # 1.9.6.16, la versión anterior superó a 14000). Es porque la forma en que se resuelven las secuencias enlazadas. Las secuencias son perezosas y la "recursión" es perezosa. Es decir, seq n llama a seq n-1 que llama a seq n-2 y así sucesivamente para obtener el primer elemento (el primer número es el peor de los casos).

Entiendo que [|0|] |> Seq.append str |> Seq.windowed 2 , está empeorando mi problema y podría triplicar el # que podría generar si eliminara eso. Prácticamente hablando el código funciona bastante bien. La iteración 3125 de morris tendría más de 10 ^ 359 caracteres de longitud.

El problema que realmente estoy tratando de resolver es cómo conservar la evaluación perezosa y no tener un límite en función del tamaño de pila para la iteración que puedo seleccionar. Estoy buscando el lenguaje F # apropiado para establecer el límite según el tamaño de la memoria.

Actualización oct ''10

Después de aprender F # un poco mejor, un poco de Haskell, pensando e investigando este problema durante más de un año, finalmente puedo responder mi propia pregunta. Pero como siempre con problemas difíciles, el problema comienza con la pregunta equivocada. El problema no son las secuencias de secuencias, en realidad se debe a una secuencia definida recursivamente. Mis habilidades de programación funcional están un poco mejor ahora y, por lo tanto, es más fácil ver lo que está pasando con la versión a continuación, que todavía tiene un flujo de pila

let next str = 
    Seq.append str [0]
    |> Seq.pairwise
    |> Seq.scan (fun (n,_) (c,v) ->
            if (c = v) then (n+1,Seq.empty)
            else (1,Seq.ofList [n;c]) ) (1,Seq.empty)
    |> Seq.collect snd

let morris = Seq.unfold(fun sq -> Some(sq,next sq))

Básicamente, crea una cadena muy larga de llamadas a la función de procesamiento Seq para generar las secuencias. El módulo Seq que viene con F # es lo que no puede seguir la cadena sin usar la pila. Hay una optimización que usa para agregar y secuencias recursivamente definidas, pero esa optimización solo funciona si la recursión está implementando un agregado.

Así que esto funcionará

let rec ints n = seq { yield n; yield! ints (n+1) }
printf "%A" (ints 0 |> Seq.nth 100000);;

Y este tendrá un stackoverflow.

let rec ints n = seq { yield n; yield! (ints (n+1)|> Seq.map id) }
printf "%A" (ints 0 |> Seq.nth 100000);;

Para probar que el problema era F # libary, escribí mi propio módulo Seq que implementó adjuntar, emparejar, escanear y recopilar usando continuciones y ahora puedo comenzar a generar e imprimir los 50,000 seq sin ningún problema (nunca terminará ya que se acabó 10 ^ 5697 dígitos de largo).

Algunas notas adicionales:

• Las continuaciones fueron el idioma que estaba buscando, pero en este caso, tuvieron que ingresar a la biblioteca F #, no a mi código. Aprendí sobre las continuaciones en F # del libro de Programación Funcional del Mundo Real de Tomas Petricek .
• La lista de respuestas perezosas que acepté contenía el otro idioma; evaluación perezosa En mi biblioteca reescrita, también tuve que aprovechar el tipo perezoso para evitar el flujo de pila.
• La versión de la lista lenta de trabajos por suerte (tal vez por diseño, pero eso está más allá de mi capacidad actual de determinar): la coincidencia de patrón activo que utiliza mientras construye e itera hace que las listas calculen valores antes de que la recursión requerida sea demasiado profunda. es perezoso, pero no tan perezoso que necesita continuaciones para evitar el flujo de apilamiento. Por ejemplo, cuando la segunda secuencia necesita un dígito de la primera secuencia, ya se ha calculado. En otras palabras, la versión LL no es estrictamente JIT perezosa para la generación de secuencias, solo administración de listas.

Answer 1

Creo que hay dos problemas principales aquí:

• La pereza es muy ineficiente, por lo que puede esperar una implementación funcional perezosa para ejecutar órdenes de magnitud más lentas. Por ejemplo, la implementación de Haskell que se describe here es 2,400 × más lenta que la F # que doy a continuación. Si desea una solución alternativa, su mejor opción es probablemente amortizar los cálculos agrupándolos en lotes impacientes donde los lotes se producen a pedido.

• La función Seq.append realidad llama al código C # de IEnumerable y, en consecuencia, su llamada de cola no se elimina y pierdes un poco más de espacio en la pila cada vez que lo atraviesas. Esto se muestra cuando se llega a enumerar sobre la secuencia.

Lo siguiente es más de 80 × más rápido que su implementación al calcular la longitud de la subsecuencia 50, pero quizás no sea lo suficientemente perezoso para usted:

let next (xs: ResizeArray<_>) =
  let ys = ResizeArray()
  let add n x =
    if n > 0 then
      ys.Add n
      ys.Add x
  let mutable n = 0
  let mutable x = 0
  for i=0 to xs.Count-1 do
    let x'' = xs.[i]
    if x=x'' then
      n <- n + 1
    else
      add n x
      n <- 1
      x <- x''
  add n x
  ys

let morris =
  Seq.unfold (fun xs -> Some(xs, next xs)) (ResizeArray [1])

El núcleo de esta función es un pliegue sobre un ResizeArray que podría ser factorizado y utilizado funcionalmente sin demasiada degradación del rendimiento si utilizara una estructura como acumulador.

Answer 2

Definitivamente deberías revisar

http://research.microsoft.com/en-us/um/cambridge/projects/fsharp/manual/FSharp.PowerPack/Microsoft.FSharp.Collections.LazyList.html

Pero trataré de publicar una respuesta más completa más tarde.

ACTUALIZAR

Ok, una solución está abajo. Representa la secuencia de Morris como un LazyList of LazyLists of int, ya que supongo que quieres que sea perezoso en "ambas direcciones".

La F # LazyList (en FSharp.PowerPack.dll) tiene tres propiedades útiles:

• es perezoso (la evaluación del elemento n no se realizará hasta que se solicite por primera vez)
• no vuelve a calcular (la reevaluación del elemento nth en la misma instancia de objeto no lo volverá a calcular; almacena en caché cada elemento después de su primer cálculo)
• puede ''olvidar'' los prefijos (a medida que ''se une'' a la lista, el prefijo sin referencia ya está disponible para la recolección de basura)

La primera propiedad es común con seq (IEnumerable), pero las otras dos son exclusivas de LazyList y son muy útiles para problemas computacionales como el que se plantea en esta pregunta.

Sin más preámbulos, el código:

// print a lazy list up to some max depth
let rec PrintList n ll =
    match n with
    | 0 -> printfn ""
    | _ -> match ll with
           | LazyList.Nil -> printfn ""
           | LazyList.Cons(x,xs) ->
               printf "%d" x
               PrintList (n-1) xs

// NextMorris : LazyList<int> -> LazyList<int>
let rec NextMorris (LazyList.Cons(cur,rest)) = 
    let count = ref 1
    let ll = ref rest
    while LazyList.nonempty !ll && (LazyList.hd !ll) = cur do
        ll := LazyList.tl !ll
        incr count
    LazyList.cons !count
        (LazyList.consf cur (fun() ->
            if LazyList.nonempty !ll then
                NextMorris !ll
            else
                LazyList.empty()))

// Morris : LazyList<int> -> LazyList<LazyList<int>>
let Morris s =
    let rec MakeMorris ll =
        LazyList.consf ll (fun () ->
            let next = NextMorris ll
            MakeMorris next
        )
    MakeMorris s

// "main"
// Print the nth iteration, up to a certain depth
[1] |> LazyList.of_list |> Morris |> Seq.nth 3125 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 3126 |> PrintList 10
[1] |> LazyList.of_list |> Morris |> Seq.nth 100000 |> PrintList 35
[1] |> LazyList.of_list |> Morris |> Seq.nth 100001 |> PrintList 35

Actualización2

Si solo quieres contar, eso está bien también:

let LLLength ll =
    let rec Loop ll acc =
        match ll with
        | LazyList.Cons(_,rest) -> Loop rest (acc+1N)
        | _ -> acc
    Loop ll 0N

let Main() =
    // don''t do line below, it leaks
    //let hundredth = [1] |> LazyList.of_list |> Morris |> Seq.nth 100
    // if we only want to count length, make sure we throw away the only
    // copy as we traverse it to count
    [1] |> LazyList.of_list |> Morris |> Seq.nth 100
        |> LLLength |> printfn "%A" 
Main()    

El uso de la memoria se mantiene estable (por debajo de 16M en mi caja) ... aún no se ha ejecutado, pero calculé la longitud 55, incluso en mi caja lenta, así que creo que esto debería funcionar bien. Tenga en cuenta también que usé ''bignum''s'' para la longitud, ya que creo que esto desbordará un ''int''.

Answer 3

Solo guarda el elemento anterior que buscabas.

let morris2 data = seq {
    let cnt = ref 0
    let prev = ref (data |> Seq.nth 0)

     for cur in data do
        if cur <> !prev then
            yield! [!cnt; !prev]
            cnt := 1
            prev := cur
        else
            cnt := !cnt + 1

    yield! [!cnt; !prev]
}

let rec morrisSeq2 cur = seq {
    yield cur
    yield! morrisSeq2 (morris2 cur)
}