Làm cách nào để hợp nhất các chuỗi được sắp xếp?

Question

Đây là vấn đề mà tôi thực sự đang gặp khó khăn. Tôi cần phải hợp nhất hai chuỗi sắp xếp thành một chuỗi được sắp xếp đơn. Lý tưởng nhất, thuật toán nên được đánh giá lười biếng, và không yêu cầu bộ nhớ đệm nhiều hơn một mục từ mỗi chuỗi. Đây không phải là vấn đề khó giải quyết, và tôi đã có thể thiết kế một số giải pháp trong F #. Thật không may, mọi giải pháp mà tôi đưa ra đều có một số vấn đề.

1. Gọi đệ quy đến máy phát điện sau đó sử dụng năng suất !. Điều này tạo ra các giải pháp tìm kiếm thanh lịch, nhưng việc tạo ra một chuỗi cho mỗi mục là một kẻ giết người hiệu suất.

2. mã thực sự phức tạp và unmaintainable với công tắc trận đấu sâu-xếp chồng lên nhau, nhiều khối gần giống mã vv

3. Mã mà buộc F # thành một chế độ hoàn toàn thủ tục (rất nhiều giá trị có thể thay đổi, vv).

Và tất cả các ví dụ trực tuyến tôi đều có thể tìm thấy người sáng lập trên cùng một bãi.

Tôi có thiếu một điều gì đó hiển nhiên: như nó thực sự đơn giản hay không rõ ràng là không thể? Có ai biết về một giải pháp thực sự thanh lịch đó cũng là hiệu quả và chủ yếu là chức năng? (Nó không phải là hoàn toàn có chức năng.) Nếu không, tôi có thể sẽ kết thúc bộ nhớ đệm sau đó và sử dụng danh sách hoặc mảng.

Answer 1

Sử dụng loại LazyList trong PowerPack. Tôi nghĩ rằng tôi thậm chí có thể có mã này chính xác nằm xung quanh, hãy để tôi trông ...

EDIT

không chính xác nó, nhưng gần: http://cs.hubfs.net/forums/thread/8136.aspx

Answer 2

Sequences không thực sự phù hợp với mô hình tốt.

May mắn thay, một trong những lợi thế của F # là có thể thả xuống mã bắt buộc khi cần và tôi nghĩ rằng nó vẫn thành ngữ để sử dụng trạng thái có thể thay đổi nội bộ miễn là chức năng vẫn tinh khiết cho khách hàng sử dụng chức năng. Tôi nghĩ phong cách này thực sự phổ biến trong mã nguồn F # ở bất cứ đâu có liên quan.

của nó không đẹp, nhưng hoạt động này:

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

Lý tưởng nhất, thuật toán nên lười biếng đánh giá ... việc tạo ra một dãy cho mỗi mục là một kẻ giết người hiệu suất

Phương tiện lười biếng chậm nhưng đây là giải pháp sử dụng danh sách lười biếng:

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 

Tôi nghĩ bằng cách "đánh giá lười biếng" nghĩa là bạn muốn kết quả được hợp nhất được tạo theo yêu cầu để bạn cũng có thể sử dụng:

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 
} 

Như bạn nói, điều này rất không hiệu quả. Tuy nhiên, giải pháp dựa trên seq không phải chậm.Ở đây, Seq.unfold là bạn của bạn và có thể làm cho điều này hơn 4 × nhanh hơn bằng cách đo của tôi:

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)