Sıralı diziler nasıl birleştirilir?

Question

Gerçekten uğraştığım bir sorun var. Sıralanan iki diziyi tek sıralı bir sıra halinde birleştirmem gerekiyor. İdeal olarak, algoritma tembel olarak değerlendirilmeli ve her diziden birden fazla öğeyi önbelleğe almayı gerektirmemelidir. Bu, çözülmesi çok zor bir problem değildir ve F # 'de bir dizi çözümü üretebildim. Ne yazık ki, bulduğum her çözümün bir çok problemi var.

1. Verim kullanarak alt dizgelere yinelemeli çağrılar !. Bu zarif görünümlü çözümler üretir, ancak her öğe için bir alt dizinin oluşturulması bir performans katilidir. vb bütünüyle usule modunda (değişebilir değerlerinin çok, vs.) halinde F # zorlar

2. Kod derin yığılmış eşleme anahtarlarla

3. Gerçekten gizli ve unmaintainable kodu, kod çoklu hemen hemen aynı blok.

Ve tüm çevrimiçi örnekler aynı shoals üzerinde bulucu bulabildim.

Belirgin bir şeyi kaçırıyor muyum: gerçekten çok basit ya da açıkçası imkansız gibi mi? Aynı zamanda verimli ve çoğunlukla işlevsel olan gerçekten zarif bir çözümü bilen var mı? (Tamamen işlevsel olmak zorunda değildir.) Aksi takdirde, önbelleklerin önbelleğe alınmasına ve listelerin veya dizilerin kullanımına son verebilirim.

Answer 1

PowerPack'de LazyList türünü kullanın. Ben yakın

DÜZENLEME

değil aynen ... Ben belki de bakayım, tam olarak bu kod ortalıkta var, ama: http://cs.hubfs.net/forums/thread/8136.aspx

Answer 2

Diziler gerçekten iyi desen maçı yok.

Neyse F # avantajlarından biri size gerektiğinde aşağı zorunlu koduna dusurmeden ve ben hala deyimsel tüketen müşterilere kadar uzun işlev hala saf olarak içten kesilebilir devlet kullanmak düşünüyorum işlevi. Bu tarzın, dizilerin yer aldığı F # kaynak kodunda gerçekten yaygın olduğunu düşünüyorum.

Onun güzel değil, ama bu işleri:

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 ->() 
    } 

İdeal

Answer 3

, algoritma olmalı tembel değerlendirmek ... her öğe için bir alt dizisinin yaratılması bir performans katil

olduğunu

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 

bence:

tembel tembel listelerini kullanarak bir çözüm yavaş demektir ama burada tarafından "tembel değerlendirdi" sen de kullanabilmesi, birleştirme sonucu talep üzerine oluşturulmasını istediğiniz demek:

Dediğiniz gibi

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 
} 

, bu çok verimsiz. Bununla birlikte, seq tabanlı bir çözümün yavaş olması gerekmez.Burada Seq.unfold senin arkadaşın ve benim ölçümler daha hızlı × 4 üzerinden bu yapabilirsiniz:

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)