如何有效地找出一個序列是否至少有n個項目？

只是天真地使用Seq.length可能不夠好，會炸燬無限序列。如何有效地找出一個序列是否至少有n個項目？

使用諸如ss |> Seq.truncate n |> Seq.length之類的東西可以起作用，但幕後會涉及IEnumerator的MoveNext()對參數序列塊的雙重遍歷。

我能弄出迄今最好的辦法是：

let hasAtLeast n (ss: seq<_>) = 
    let mutable result = true 
    use e = ss.GetEnumerator() 
    for _ in 1 .. n do result <- e.MoveNext() 
    result

這僅涉及單個序列移動（更準確地，在執行e.MoveNext()n次）和正確處理空和無限序列的邊界情況。我可以進一步拋出一些小的改進，比如顯式處理列表，數組和特定的例子，或者減少遍歷長度，但是想知道是否有更有效的方法來解決我可能會丟失的問題？

謝謝你的幫助。

編輯：hasAtLeast功能，手邊5個整體實施變型（2我自己，通過2丹尼爾和一個接ANKUR建議建議）我給你佈置這些之間的馬拉松比賽。所有實施方案的結果都證明，Guvante是正確的：現有算法的最簡單組合是最好的，在過度工程中沒有任何意義。

的可讀性因素進一步投擲我會請使用我自己的純F＃基礎的

let hasAtLeast n (ss: seq<_>) = 
    Seq.length (Seq.truncate n ss) >= n

或建議通過ANKUR完全等同基於的LINQ一個.NET的集成大寫

let hasAtLeast n (ss: seq<_>) = 
    ss.Take(n).Count() >= n

來源

2011-09-23 Gene Belitski

我不禁在想，如果你的算法應該使用更合適的類型，而不是遍歷序列。 – ChaosPandion

@ChaosPandion：相信我，我已經考慮過這件事。在我的辯護中，我想參考Luke Hoban標準偏差和基於事件的編程（http://blogs.msdn.com/b/lukeh/archive/2008/10/10/standard-deviation- and-event-based-programming.aspx） –

函數式編程打破了工作量成小塊並且做做一個簡單的事情非常通用的任務。確定序列中是否至少有n項目不是一項簡單的任務。

你已經找到了這個「問題」的解決方案，現有算法的組成，它適用於大多數情況，並創建自己的算法來解決問題。

但是我不得不懷疑你的第一個解決方案是行不通的。 MoveNext()在原始方法上僅被稱爲n倍，Current永遠不會被調用，即使在某些包裝類上調用了MoveNext()，性能影響可能很小，除非n很大。

編輯：

我很好奇，所以我寫了一個簡單的程序來測試這兩種方法的時機。截斷方法對於一個簡單的無限序列和一個有Sleep(1)更快。當你的修正聽起來像過度工程時，看起來我是正確的。

我認爲需要澄清以解釋這些方法中發生了什麼。 Seq.truncate接受一個序列並返回一個序列。除了保存n的值之外，枚舉之前它不會執行任何操作。在枚舉過程中，它計數並在n之後停止。 Seq.length需要枚舉並計數，並在計數結束時返回。所以枚舉只枚舉一次，開銷的數量是幾個方法調用和兩個計數器。

來源

2011-09-23 17:34:32 Guvante

使用LINQ這將是簡單：

let hasAtLeast n (ss: seq<_>) = 
    ss.Take(n).Count() >= n

如果沒有足夠的元素，Seq take方法會爆炸。

使用例子來顯示它遍歷序列只有一次，直到所需的元素：

seq { for i = 0 to 5 do 
     printfn "Generating %d" i 
     yield i } 
|> hasAtLeast 4 |> printfn "%A"

來源

2011-09-23 17:30:33 Ankur

這不等同於第一個例子中包含的原始海報麼？ – Guvante

是的，我想這應該是，但這並不意味着它會兩次遍歷Seq。我已經更新了一個例子的答案，以顯示它只被遍歷一次。即使是OP的第一個例子 – Ankur

@Ankur：我的意思是「第二」遍歷，更確切地說，是遍歷懶惰的原始序列，找到並返回它的長度。您可以通過查看Seq模塊實現來了解Seq.length是如何工作的。 –

這裏是一個簡短的，實用的解決方案：

let hasAtLeast n items = 
    items 
    |> Seq.mapi (fun i x -> (i + 1), x) 
    |> Seq.exists (fun (i, _) -> i = n)

例子：

let items = Seq.initInfinite id 
items |> hasAtLeast 10000

這裏是一個最爲有效的一個：

let hasAtLeast n (items:seq<_>) = 
    use e = items.GetEnumerator() 
    let rec loop n = 
    if n = 0 then true 
    elif e.MoveNext() then loop (n - 1) 
    else false 
    loop n

來源

2011-09-23 18:39:46 Daniel

+1任何想法，性能差異是什麼樣的？ –

海量。對於'n = 10,000,000'，第一個解決方案慢5倍。 – Daniel

如何有效地找出一個序列是否至少有n個項目？

回答

相關問題