代码之家 › 专栏 › 技术社区 › TechNeilogy

如何合并排序序列?

TechNeilogy · 技术社区 · 14 年前

这是我一直在努力解决的一个问题。我需要将两个排序序列合并为一个排序序列。理想情况下,应该对算法进行延迟计算,并且不需要从每个序列中缓存多个项。这不是一个非常难解决的问题,我已经在f中设计了许多解决方案。不幸的是,我提出的每个解决方案都有几个问题之一。

使用yield递归调用子序列生成器!。这将产生美观的解决方案,但为每个项目创建子序列是一个性能杀手。
非常神秘和不可维护的代码,带有高度堆叠的匹配开关、多个几乎相同的代码块等。
强制f进入纯过程模式(大量可变值等)的代码。

所有的在线例子我都能在同一个浅滩上找到创始人。

我是否遗漏了一些明显的东西:比如说它不是很简单,就是不可能?有没有人知道一个真正优雅的解决方案,它也是有效的,而且主要是功能性的?(它不必纯粹是功能性的。)如果不是,我可能最终会缓存子序列并使用列表或数组。

3 回复 | 直到 12 年前

Brian 14 年前

使用电源组中的lazylist类型。我想我甚至可能有这个确切的密码,让我看看…

编辑

不完全正确,但接近: http://cs.hubfs.net/forums/thread/8136.aspx

J D 12 年前

理想情况下,算法应该是惰性评估…为每个项目创建子序列是一个性能杀手。

懒惰意味着慢,但这里有一个使用懒惰列表的解决方案:

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

我认为“lazy evaluated”是指您希望根据需要生成合并结果,这样您还可以使用:

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
}

如你所说,这是非常低效的。然而,A 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)

Juliet 14 年前

序列没有很好的模式匹配。

幸运的是,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 -> ()
    }