Как объединить отсортированные последовательности?

Вот проблема, с которой я действительно боролся. Мне нужно объединить две отсортированные последовательности в одну отсортированную последовательность. В идеале алгоритм должен быть ленивым и не требует кэширования более чем одного элемента из каждой последовательности. Это не очень трудная проблема для решения, и я смог разработать ряд решений в F #. К сожалению, у каждого решения Ive есть одна из нескольких проблем.

Рекурсивные вызовы генераторам подпоследовательностей с использованием yield!. Это создает элегантно выглядящие решения, но создание подпоследовательности для каждого элемента является убийцей производительности.
Действительно тайный и незаметный код с глубоко уложенными совпадающими переключателями, несколькими почти идентичными блоками кода и т.д.
Код, который заставляет F # в чисто процедурный режим (много изменяемых значений и т.д.).

И все онлайн-примеры я смог найти основателя на тех же косяках.

Я пропустил что-то очевидное: как это действительно просто или, очевидно, невозможно? Кто-нибудь знает о действительно элегантном решении, которое также эффективно и в основном функционально? (Это не должно быть чисто функциональным.) Если нет, я могу закончить кеширование подпоследовательностей и использование списков или массивов.

Ответы

Ответ 1

Используйте тип LazyList в PowerPack. Я думаю, что, возможно, у меня даже есть этот точный код, дайте мне посмотреть...

ИЗМЕНИТЬ

не совсем это, но close: http://cs.hubfs.net/forums/thread/8136.aspx

Ответ 2

В идеале алгоритм должен лениться... создание подпоследовательности для каждого элемента - убийца производительности

Lazy означает медленный, но вот решение, использующее ленивые списки:

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

Я думаю, что "ленивая оценка" означает, что вы хотите, чтобы полученный результат был сгенерирован по запросу, поэтому вы также можете использовать:

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
}

Как вы говорите, это очень неэффективно. Однако решение на основе seq не должно быть медленным. Здесь Seq.unfold является вашим другом и может сделать это более чем на 4 раза быстрее по моим измерениям:

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)

Ответ 3

Последовательности на самом деле не соответствуют хорошему.

К счастью, одно из преимуществ F # заключается в том, что вы можете отказаться от императивного кода, когда вам это нужно, и я думаю, что все же идиоматично использовать изменяемое состояние внутри, пока функция по-прежнему чиста для клиентов, потребляющих эту функцию. Я думаю, что этот стиль действительно распространен в исходном коде F # везде, где задействованы последовательности.

Его не очень, но это работает:

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