如何有效地找出一个序列是否至少有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个项目？

回答

相关问题