3

使用 F# List 和 Seq 合并两个排序的列表/序列。这些值是通过从辅助存储器中读取两个文件来获得的 - 文件读取的结果存储在两个序列中。假设整数存储用于测试目的，现在尝试合并这些以使用以下代码打印出排序序列：

let rec printSortedSeq l1 l2 = 
    match ( l1, l2) with
    | l1,l2 when Seq.isEmpty l1 && Seq.isEmpty l2 -> printfn "";
    | l1, l2 when Seq.isEmpty l1 -> printf "%d " (Seq.head l2);  printSortedSeq l1 (Seq.skip 1 l2);
    | l1, l2 when Seq.isEmpty l2-> printf "%d " (Seq.head l1);  printSortedSeq (Seq.skip 1 l1) [];

    | l1,l2 -> if Seq.head l1 = Seq.head l2 then printf "%d " (Seq.head l1);  printSortedSeq (Seq.skip 1 l1) (Seq.skip 1 l2); 
                               elif Seq.head l1 < Seq.head l2 then printf "%d " (Seq.head l1);  printSortedSeq (Seq.skip 1 l1) (Seq.skip 1 l2); 
                               else printf "%d " (Seq.head l2);  printSortedSeq (Seq.skip 1 l1) (Seq.skip 1 l2);

该代码最初是为了合并两个排序列表而编写的：

let rec printSortedList l1 l2 = 
    match ( l1, l2) with
    | h1 :: t1 , h2 :: t2 -> if h1 = h2 then printf "%d " h1;  printSortedList t1 t2; 
                               elif h1 < h2 then printf "%d " h1;  printSortedList t1 l2; 
                               else printf "%d " h2;  printSortedList l1 t2;
    | [] , h2 :: t2 ->  printf "%d " h2;  printSortedList [] t2;
    | h1 :: t1, [] -> printf "%d " h1;  printSortedList t1 [];
    | [], [] -> printfn"";

使用它们的性能大大优于列表。我在做#time之后给出计时结果；；在 FSI 中关于一些试验输入。

let x = [0..2..500];
let y = [1..2..100];

let a = {0..2..500}
let b = {1..2..100}

printSortedList xy;; 真实：00:00:00.012，CPU：00:00:00.015

printSortedSeq ab；；真实：00:00:00.504，CPU：00:00:00.515

问题是 - 有没有办法使用序列使事情变得更快？因为虽然列表要快得多，但由于提供输入的文件非常大（> 2 GB），它们不适合主内存，所以我从文件中读取值作为惰性序列。在合并之前将它们转换为列表有点违背了整个目的。

4

3 回答 3

4

Seq.skip 是一种反模式。使用 F# PowerPack 中的 LazyList，或使用枚举器 (GetEnumerator...MoveNext...Current) 来有效地遍历 Seq。查看其他类似的问答。

于 2012-06-26T06:57:46.940 回答
4

As toyvo mentioned, this can be greatly simplified using a stateful enumerator:

let mkStatefulEnum (e: IEnumerator<'T>) =
  let x = ref None
  fun move ->
    if move then x := (if e.MoveNext() then Some e.Current else None)
    !x

let merge (a: seq<'T>) (b: seq<'T>) =
  seq {
    use x = a.GetEnumerator()
    use y = b.GetEnumerator()
    let nextX = mkStatefulEnum x
    let nextY = mkStatefulEnum y
    yield! Seq.unfold (fun (a, b) ->
      match a, b with
      | Some a, Some b -> 
        if a < b then Some (a, (nextX true, nextY false))
        else Some (b, (nextX false, nextY true))
      | Some a, None -> Some (a, (nextX true, nextY false))
      | None, Some b -> Some (b, (nextX false, nextY true))
      | None, None -> None
    ) (nextX true, nextY true)
  }
于 2012-06-26T17:19:46.817 回答
3

您的问题的答案是，与 List 相比，F# 序列操作主要慢，是否。由于序列重新遍历，您的序列代码以多项式时间运行，而您的列表代码以线性时间运行。

为了记录，可以在线性时间内合并两个排序的序列。例如：

open System.Collections.Generic

type State<'T> =
    | Neutral
    | Left of 'T
    | Right of 'T
    | Tail

let mergeSeqs (a: seq<'T>) (b: seq<'T>) =
    let cmp x y =
        match compare x y with
        | 1 -> Some (y, Left x)
        | _ -> Some (x, Right y)
    seq {
        use x = a.GetEnumerator()
        use y = b.GetEnumerator()
        let step st =
            match st with
            | Neutral ->
                match x.MoveNext(), y.MoveNext() with
                | true, true -> cmp x.Current y.Current
                | true, false -> Some (x.Current, Tail)
                | false, true -> Some (y.Current, Tail)
                | false, false -> None
            | Left v ->
                match y.MoveNext() with
                | true -> cmp v y.Current
                | false -> Some (v, Neutral)
            | Right v ->
                match x.MoveNext() with
                | true -> cmp x.Current v
                | false -> Some (v, Neutral)
            | Tail ->
                match x.MoveNext(), y.MoveNext() with
                | false, false -> None
                | true, _ -> Some (x.Current, Tail)
                | _, true -> Some (y.Current, Tail)
        yield! Seq.unfold step Neutral
    }

You can improve on that by reducing consing. Design a custom IEnumerator with mutable state similar to State<'T>, and use that as the basis for the merged sequence.

于 2012-06-26T13:31:05.880 回答