un problema de aplicación de F # Sec

Question

estoy cavando en C# código fuente recientemente.

en Seq.fs:

// Binding. 
// 
// We use a type defintion to apply a local dynamic optimization. 
// We automatically right-associate binding, i.e. push the continuations to the right. 
// That is, bindG (bindG G1 cont1) cont2 --> bindG G1 (cont1 o cont2) 
// This makes constructs such as the following linear rather than quadratic: 
// 
// let rec rwalk n = { if n > 0 then 
//       yield! rwalk (n-1) 
//       yield n } 

Después de ver el código anterior, he probado dos código:

let rec rwalk n = seq { if n > 0 then 
         yield n 
         yield! rwalk (n-1) 
         } 

y

let rec rwalk n = seq { if n > 0 then 
         yield! rwalk (n-1) 
         yield n 
         } 

me encontré con la primera es muy rápido , mientras que el segundo es muy lento. Si n = 10000, cuesta 3 segundos en mi máquina generar esta secuencia, por lo tanto, tiempo cuadrático.

El tiempo cuadrática es razonable, como por ejemplo,

seq { yield! {1; 2; ...; n-1}; yield n } se traduce en

Seq.append {1; 2; ...; n-1} {n} 

Esta operación de anexión debe tomar el tiempo lineal, supongo. Mientras está en el primer código, la operación de agregar es así: seq { yield n; yield! {n-1; n-2; ...; 1} }, que cuesta tiempo constante.

Los comentarios de los códigos dicen que es linear (tal vez esto no es lineal del tiempo lineal). Quizás esto linear se relaciona con el uso de implementación personalizada para la secuencia en lugar de la expresión de cálculo Moand/F # (como se menciona en la especificación F #; sin embargo, la especificación no menciona el motivo para hacerlo ...).

Podría alguien aclarar la falta de claridad en esta lista? ¡Muchas gracias!

(ps porque se trata de un diseño de lenguaje y problemas de optimización, que la etiqueta Haskell también se adjunta para ver si las personas no tienen puntos de vista.)

Answer 1

Cuando yield! aparece en una posición no de llamada final, que essentiall significa lo mismo que:

for v in <expr> do yield v 

el problema con esto (y la razón por la que es cuadrática) es que para las llamadas recursivas, esto crea una cadena de iteradores con for bucles anidados. Debe iterar sobre toda la secuencia generada por <expr> para cada elemento individual, de modo que si la iteración es lineal, obtendrá un tiempo cuadrático (porque la iteración lineal ocurre para cada elemento).

Digamos que la función rwalk genera [ 9; 2; 3; 7 ]. En la primera iteración, la secuencia generada recursivamente tiene 4 elementos, por lo que iterarías sobre 4 elementos y agregarías 1. En la llamada recursiva, iterarías sobre 3 elementos y agregarías 1, etc. Usando un diagrama, puedes ver cómo eso es cuadrática:

x 
x x 
x x x 
x x x x 

además, cada una de las llamadas recursivas crea una nueva instancia del objeto (IEnumerator) por lo que también es cierto costo de memoria (aunque sólo lineal).

En una posición de cola de llamada, el compilador de F #/librar hace una optimización. Se "sustituye" la corriente IEnumerable con el devuelto por la llamada recursiva, por lo que no tiene que recorrer overe para generar todos los elementos - se devuelve simplemente (y esto también elimina el coste de la memoria).

Relacionados. El mismo problema se ha discutido en el diseño de C# lanaugage y hay un interesting paper about it (su nombre para yield! es yield foreach).

Answer 2

No estoy seguro del tipo de respuesta que está buscando. Como habrás notado, el comentario no coincide con el comportamiento del compilador. No puedo decir si esto es una instancia de un comentario que no se sincroniza con la implementación o si en realidad es un error de rendimiento (por ejemplo, la especificación no parece indicar requisitos de rendimiento específicos).

Sin embargo, debería ser posible en teoría que la maquinaria del compilador genere una implementación que funcione con su ejemplo en tiempo lineal. De hecho, incluso es posible construir dicha implementación en una biblioteca utilizando expresiones de cálculo. He aquí un ejemplo aproximado, basado en gran medida en el papel Tomas citó:

open System.Collections 
open System.Collections.Generic 

type 'a nestedState = 
/// Nothing to yield 
| Done 
/// Yield a single value before proceeding 
| Val of 'a 
/// Yield the results from a nested iterator before proceeding 
| Enum of (unit -> 'a nestedState) 
/// Yield just the results from a nested iterator 
| Tail of (unit -> 'a nestedState) 

type nestedSeq<'a>(ntor) = 
    let getEnumerator() : IEnumerator<'a> = 
    let stack = ref [ntor] 
    let curr = ref Unchecked.defaultof<'a> 
    let rec moveNext() = 
     match !stack with 
     | [] -> false 
     | e::es as l -> 
      match e() with 
      | Done -> stack := es; moveNext() 
      | Val(a) -> curr := a; true 
      | Enum(e) -> stack := e :: l; moveNext() 
      | Tail(e) -> stack := e :: es; moveNext() 
    { new IEnumerator<'a> with 
     member x.Current = !curr 
     interface System.IDisposable with 
     member x.Dispose() =() 
     interface IEnumerator with 
     member x.MoveNext() = moveNext() 
     member x.Current = box !curr 
     member x.Reset() = failwith "Reset not supported" } 
    member x.NestedEnumerator = ntor 
    interface IEnumerable<'a> with 
    member x.GetEnumerator() = getEnumerator() 
    interface IEnumerable with 
    member x.GetEnumerator() = upcast getEnumerator() 

let getNestedEnumerator : 'a seq -> _ = function 
| :? ('a nestedSeq) as n -> n.NestedEnumerator 
| s -> 
    let e = s.GetEnumerator() 
    fun() -> 
     if e.MoveNext() then 
     Val e.Current 
     else 
     Done 

let states (arr : Lazy<_[]>) = 
    let state = ref -1 
    nestedSeq (fun() -> incr state; arr.Value.[!state]) :> seq<_> 

type SeqBuilder() = 
    member s.Yield(x) = 
    states (lazy [| Val x; Done |]) 
    member s.Combine(x:'a seq, y:'a seq) = 
    states (lazy [| Enum (getNestedEnumerator x); Tail (getNestedEnumerator y) |]) 
    member s.Zero() = 
    states (lazy [| Done |]) 
    member s.Delay(f) = 
    states (lazy [| Tail (f() |> getNestedEnumerator) |]) 
    member s.YieldFrom(x) = x 
    member s.Bind(x:'a seq, f) = 
    let e = x.GetEnumerator() 
    nestedSeq (fun() -> 
       if e.MoveNext() then 
        Enum (f e.Current |> getNestedEnumerator) 
       else 
        Done) :> seq<_> 

let seq = SeqBuilder() 

let rec walkr n = seq { 
    if n > 0 then 
    return! walkr (n-1) 
    return n 
} 

let rec walkl n = seq { 
    if n > 0 then 
    return n 
    return! walkl (n-1) 
} 

let time = 
    let watch = System.Diagnostics.Stopwatch.StartNew() 
    walkr 10000 |> Seq.iter ignore 
    watch.Stop() 
    watch.Elapsed 

Nota que mi SeqBuilder no es sólida; le faltan varios miembros de flujo de trabajo y no hace nada con respecto a la eliminación de objetos o el manejo de errores. Sin embargo, demuestra que SequenceBuilder s no necesita para exhibir tiempo de ejecución cuadrático en ejemplos como el suyo.

También tenga en cuenta que aquí hay una compensación de espacio-tiempo: el iterador anidado para walkr n iterará a través de la secuencia en el tiempo O (n), pero requiere O (n) espacio para hacerlo.