3

F# List と Seq を使用して、2 つの並べ替えられたリスト/シーケンスをマージしました。値は、セカンダリ メモリから 2 つのファイルを読み取ることによって取得されます。ファイル読み取りの結果は、2 つのシーケンスで格納されます。テスト目的で整数が保存されていると仮定すると、これらをマージして、次のコードを使用して並べ替えられたシリーズを出力しようとしています。

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);

このコードはもともと、2 つのソート済みリストをマージするために作成されました。

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

toyvoが述べたように、これはステートフル列挙子を使用して大幅に簡略化できます。

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 に答える
4

Seq.skip はアンチパターンです。F# PowerPack の LazyList を使用するか、列挙子 (GetEnumerator...MoveNext...Current) を使用して Seq を効率的にトラバースします。他の同様の Q&A を参照してください。

于 2012-06-26T06:57:46.940 に答える
3

あなたの質問に対する答えは、F# シーケンス操作は List に比べて大幅に遅いですか? いいえです。リスト コードは線形時間で実行されますが、シーケンスの再トラバーサルにより、シーケンス コードは多項式時間で実行されます。

記録のために、2 つの並べ替えられたシーケンスを線形時間でマージすることが可能です。例えば：

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
    }

コンシングを減らすことでそれを改善できます。に似た可変状態のカスタム IEnumerator を設計し、それをState<'T>マージされたシーケンスの基礎として使用します。

于 2012-06-26T13:31:05.880 に答える