f# - 如何合并排序的序列？

Question

这是我一直在努力解决的一个问题。我需要将两个排序序列合并为一个排序序列。理想情况下，该算法应该是惰性求值的，并且不需要从每个序列中缓存一个以上的项目。这不是一个很难解决的问题，而且我已经能够在 F# 中设计出许多解决方案。不幸的是，我提出的每个解决方案都有几个问题之一。

使用 yield! ​​递归调用子序列生成器。这会产生外观优雅的解决方案，但为每个项目创建子序列是性能杀手。

真正神秘且难以维护的代码，具有深度堆叠的匹配开关、多个几乎相同的代码块等。

强制 F# 进入纯程序模式的代码(大量可变值等)。

以及我能够在同一个浅滩上找到创始人的所有在线示例。

我是否遗漏了一些明显的东西:就像它要么非常简单，要么显然不可能？有谁知道一个非常优雅的解决方案，它也很有效并且主要是功能性的？ (它不必纯粹是功能性的。)如果不是，我最终可能会缓存子序列并使用列表或数组。

Answer 1

Ideally, the algorithm should be lazy-evaluate... the creation of a subsequence for every item is a performance killer

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

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是你的 friend ，通过我的测量可以使这个速度提高 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)