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

Question

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

1. Рекурсивные вызовы генераторов подпоследовательностей с использованием yield !.Это приводит к элегантно выглядящим решениям, но создание подпоследовательности для каждого элемента снижает производительность.

2. Действительно загадочный и не поддерживаемый код с глубоко укомплектованными переключателями совпадений, несколькими практически идентичными блоками кода.и т. д.

3. Код, который переводит F # в чисто процедурный режим (множество изменяемых значений и т. д.).

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

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

Answer 1

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

Ленивый означает медленный, но вот решение с использованием ленивых списков:

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)

Answer 2

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

К счастью, одним из преимуществ 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 -> ()
    }

Answer 3

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

EDIT

не совсем так, но близко: http://cs.hubfs.net/forums/thread/8136.aspx