¿Cómo combinar secuencias ordenadas?

Question

Aquí hay un problema con el que realmente he estado luchando. Necesito unir dos secuencias ordenadas en una sola secuencia ordenada. Idealmente, el algoritmo debería ser evaluado de forma diferida, y no requerir el almacenamiento en caché de más de un elemento de cada secuencia. Este no es un problema terriblemente difícil de resolver, y he podido diseñar una serie de soluciones en F #. Desafortunadamente, cada solución que he encontrado tiene uno de varios problemas.

1. Llamadas recursivas a las subsecuencias de los generadores con rendimiento !. Esto produce soluciones de aspecto elegante, pero la creación de una subsecuencia para cada elemento es un asesino de rendimiento.

2. código Realmente arcano y inmantenible con interruptores de los partidos apilados profundamente, múltiples bloques casi idénticas de código, etc.

   Código

3. que fuerza F # en un modo puramente de procedimiento (un montón de valores mutables, etc.).

Y todos los ejemplos en línea que he podido encontrar se fundan en los mismos cardúmenes.

Me falta algo obvio: como si fuera realmente simple o obviamente imposible? ¿Alguien sabe de una solución realmente elegante que también es eficiente y funcional en su mayoría? (No tiene que ser puramente funcional). De lo contrario, podría terminar en caché de subsecuencias y usar listas o matrices.

Answer 1

Utilice el tipo de LazyList en el PowerPack. Creo que tal vez tenga este código exacto por ahí, déjame ver ...

EDITAR

no exactamente, pero cerca: http://cs.hubfs.net/forums/thread/8136.aspx

Answer 2

secuencias realmente no coincidencia de patrón también.

Afortunadamente una de las ventajas de F # es ser capaz de bajar a código imperativo cuando se necesita, y yo creo que todavía idiomática a utilizar el estado mutable internamente siempre que la función sigue siendo pura a los clientes que consumen la función. Creo que este estilo es muy común en el código fuente F # donde quiera que haya secuencias involucradas.

No es bonito, pero esto funciona:

open System.Collections.Generic 
let merge (a : #seq<'a>) (b : #seq<'a>) = 
    seq { 
     use a = a.GetEnumerator() 
     use b = b.GetEnumerator() 

     let aNext = ref <| a.MoveNext() 
     let bNext = ref <| b.MoveNext() 

     let inc (enumerator : IEnumerator<'a>) flag =  // ' 
      let temp = enumerator.Current 
      flag := enumerator.MoveNext() 
      temp 
     let incA() = inc a aNext 
     let incB() = inc b bNext 

     while !aNext || !bNext do 
      match !aNext, !bNext with 
      | true, true -> 
       if a.Current > b.Current then yield incB() 
       elif a.Current < b.Current then yield incA() 
       else yield incA(); yield incB() 
      | true, false -> yield incA() 
      | false, true -> yield incB() 
      | false, false ->() 
    } 

Answer 3

Idealmente, el algoritmo debe ser perezoso a evaluar ... la creación de una subsecuencia para cada artículo es un asesino rendimiento

Lazy significa lenta pero aquí es una solución utilizando listas perezosas:

let (++) = LazyList.consDelayed 

let rec merge xs ys() = 
    match xs, ys with 
    | Cons(x, xs'), Cons(y, _) when x<y -> x ++ merge xs' ys 
    | Cons(x, _), Cons(y, ys') -> y ++ merge xs ys' 
    | Nil, xs | xs, Nil -> xs 

creo por "perezosa evaluado" quiere decir que desea que el resultado combinado que se genere en la demanda por lo que también puede utilizar:

let rec merge xs ys = seq { 
    match xs, ys with 
    | x::xs, y::_ when x<y -> 
     yield x 
     yield! merge xs ys 
    | x::_, y::ys -> 
     yield y 
     yield! merge xs ys 
    | [], xs | xs, [] -> yield! xs 
} 

Como usted dice, esto es muy ineficiente. Sin embargo, una solución basada en seq no tiene por qué ser lenta.Aquí, Seq.unfold es su amigo y puede hacer esto durante 4 × más rápido por mis medidas:

let merge xs ys = 
    let rec gen = function 
    | x::xs, (y::_ as ys) when x<y -> Some(x, (xs, ys)) 
    | xs, y::ys -> Some(y, (xs, ys)) 
    | [], x::xs | x::xs, [] -> Some(x, ([], xs)) 
    | [], [] | [], [] -> None 
    Seq.unfold gen (xs, ys)