Comment fusionner des séquences triées?

Question

Voici un problème avec lequel j'ai vraiment eu des problèmes. J'ai besoin de fusionner deux séquences triées en une seule séquence triée. Idéalement, l'algorithme devrait être paresseux et ne nécessiterait pas la mise en cache de plus d'un élément de chaque séquence. Ce n'est pas un problème terriblement difficile à résoudre, et j'ai pu concevoir un certain nombre de solutions en F #. Malheureusement, toutes les solutions que j'ai trouvées posent un problème parmi d'autres.

1. Appels récursifs aux générateurs de sous-séquences en utilisant le rendement !. Cela produit des solutions élégantes, mais la création d'une sous-séquence pour chaque article est un tueur de performance.

2. vraiment le code Arcane et ingérable avec des commutateurs match profondément empilés, plusieurs blocs presque identiques de code, etc.

3. Code qui force F # dans un mode purement procédural (beaucoup de valeurs mutables, etc.).

Et tous les exemples en ligne que j'ai pu trouver sur les mêmes bas-fonds. Suis-je en train de manquer quelque chose d'évident: comme si c'était vraiment simple ou bien évidemment impossible? Est-ce que quelqu'un connaît une solution vraiment élégante, efficace et surtout fonctionnelle? (Il ne doit pas être purement fonctionnel.) Sinon, je pourrais finir par mettre en cache des sous-séquences et utiliser des listes ou des tableaux.

Answer 1

Utilisez le type LazyList dans le PowerPack. Je pense que je peut-être ai même ce code exact qui traînent, laissez-moi regarder ...

EDIT

pas exactement, mais à proximité: http://cs.hubfs.net/forums/thread/8136.aspx

Answer 2

Sequences ne sont pas vraiment bien correspondance de motif.

Heureusement l'un des avantages de F # est pouvoir descendre à code impératif lorsque vous avez besoin, et je pense qu'il encore idiomatiques à utiliser l'état mutable interne tant que la fonction est encore pure aux clients consommateurs du fonction. Je pense que ce style est très commun dans le code source F # où les séquences sont impliquées.

Son pas joli, mais cela fonctionne:

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

Idéalement, l'algorithme devrait être paresseux-évaluer ... la création d'une sous pour chaque élément est un tueur de performance

Lazy signifie lent, mais voici une solution en utilisant des listes paresseux:

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 

Je pense par « paresseux évalué » vous voulez dire que vous voulez que le résultat de la fusion à générer à la demande de sorte que vous pouvez également utiliser:

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 
} 

Comme vous le dites, ce qui est très inefficace. Cependant, une solution basée sur seq ne doit pas être lente.Ici, Seq.unfold est votre ami et peut faire ce plus de 4 × plus rapidement par mes mesures:

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)