一些基本的序列，並列出問題

可能重複：
Linked list partition function and reversed results 一些基本的序列，並列出問題

其實我不在乎輸入類型或輸出類型，任何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，然後採取tail N次......這仍然是O（n）的

（如果有一個C＃列表，然後我會用，如果沒有爲扭轉這種局面......）

A面的問題，什麼是Array.ofList和List.toArray，或者更一般地說，A.ofB和List, Seq, ArrayB.ofA區別？

是seq myList是否與List.toSeq myList相同？

另一方面的問題是嵌套Seq.append與Seq.concat具有相同的複雜性？

例如

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

來源

2012-10-26 colinfang

@JohnPalmer謝謝，我很快就會刪除這個問題。 – colinfang

不需要刪除它 - 其他人可能會出現同一個問題 –

如果'List.rev'確實會出錯，請參閱[我的答案]（http://stackoverflow.com/a/7199989/162396）以解決類似的問題爲基於延續的版本。 – Daniel

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-26 11:38:43

是'seq myList'與'List.toSeq myList'相同嗎？ – colinfang

@colinfang - 看起來這樣，但我不確定 –

這個怎麼樣：

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

它使用一個單一的庫函數List.partition，這是有效地實現。希望這是你的意思:)

來源

2012-10-26 11:21:32

我懷疑它是*高效的，因爲你總是必須遍歷整個列表和'ref'單元的開銷。 – pad

只需謹慎一點 - 在函數式編程中，變量名稱「cont」通常用於* continuation *，並且在用於其他變量時可能會有點混淆。下次你可能想要選擇一個不同的變量名稱（例如'finished'或'done'）。 –

回答您的問題：

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在內部使用相同的功能（請參閱here和here）。 3）。我認爲Seq.concat與一堆Seq.append具有相同的複雜性。在List和Array的情況下，concat比append更有效，因爲您有更多信息爲輸出預先分配空間。

來源

2012-10-26 11:21:34 pad

是'seq myList'與'List.toSeq myList'完全相同嗎？ – colinfang

一些基本的序列，並列出問題

回答

相關問題