0

重複の可能性：
リンクリストのパーティション関数と逆の結果

実際、私は入力タイプや出力タイプを気にしませseq, array, listん。（一般的である必要はありません）現在、私のコードはlist入力と(list * list)出力として受け取ります

let takeWhile predicator list =
   let rec takeWhileRec newList remain =
       match remain with
       | [] -> (newList |> List.rev, remain)
       | x::xs -> if predicator x then
                     takeWhileRec (x::newList) xs
                  else
                     (newList |> List.rev, remain)
   takeWhileRec [] list

ただし、落とし穴があります。私が見るようにList.rev、全体的な速度を支配する可能性が高いO（n ^ 2）はありますか？私はそれが醜い解決策よりもさらに遅いと思います：Seq.takeWhile、そしてcount、そしてそれからtailn回かかります...それはまだO（n）です

（C＃リストがある場合は、それを逆にすることなく使用します...）

Array.ofList副次的な質問ですが、とList.toArray、またはより一般的には、A.ofBとB.ofAの違いは何List, Seq, Arrayですか？

とseq myList同じList.toSeq myListですか？

もう1つの副次的な質問は、ネストされているのは？Seq.appendと同じ複雑さです。Seq.concat

例えば

  Seq.append (Seq.append (Seq.append a b) c) d // looks aweful
  Seq.concat [a;b;c;d]
4

3 に答える 3

2

あなたの質問に答えるには：

1）List.revの時間計算量はでありO(n)、最悪の場合の複雑さtakeWhileもO(n)です。したがって、使用List.revしても関数の複雑さは増しません。を使用ResizeArrayすると回避するのに役立ちますList.revが、少しの突然変異を許容する必要があります。

let takeWhile predicate list =
   let rec loop (acc: ResizeArray<_>) rest =
       match rest with       
       | x::xs when predicate x -> acc.Add(x); loop acc xs
       | _ -> (acc |> Seq.toList, rest)
   loop (ResizeArray()) list

2）違いはありません。内部で同じ関数Array.ofListを使用します（こことここを参照）。List.toArray

3）。私Seq.concatはたくさんのと同じ複雑さを持っていると思いますSeq.append。Listおよびのコンテキストでは、出力用のスペースを事前に割り当てるための情報が多いためArray、 concatより効率的です。append

于 2012-10-26T11:21:34.113 に答える
2

1）の関連する実装はList.revコンパイラlocal.fsにあります-それは

// optimized mutation-based implementation. This code is only valid in fslib, where mutation of private
// tail cons cells is permitted in carefully written library code.
let rec revAcc xs acc =
    match xs with
    | [] -> acc
    | h::t -> revAcc t (h::acc)

let rev xs =
    match xs with
    | [] -> xs
    | [_] -> xs
    | h1::h2::t -> revAcc t [h2;h1]

明らかな突然変異がないので、コメントは奇妙に見えます。これは実際にはそうでO(n)はないことに注意してくださいO(n^2)

2）パッドが言ったように違いはありません-私はto..私が思うようにを使用することを好みます

A
|> List.map ...
|> List.toArray

より良く見えます

A
|> List.map ...
|> Array.ofList

でもそれは私だけです。

3）

追加（コンパイラソース）：

[<CompiledName("Append")>]
let append (source1: seq<'T>) (source2: seq<'T>) =
    checkNonNull "source1" source1
    checkNonNull "source2" source2
    fromGenerator(fun () -> Generator.bindG (toGenerator source1) (fun () -> toGenerator source2))

追加ごとに、ウォークスルーする必要のある追加のジェネレーターを取得することに注意してください。比較すると、concatの実装には、1つの追加関数が含まれるだけなnので、使用するconcat方がおそらく優れています。

于 2012-10-26T11:38:43.550 に答える
1

これはどう：

let takeWhile pred =
    let cont = ref true
    List.partition (pred >> fun r -> !cont && (cont := r; r))

これは、効率的に実装される単一のライブラリ関数List.partitionを使用します。これがあなたの意図したことだといいのですが:)

于 2012-10-26T11:21:32.737 に答える