如何有效地找出一个序列是否至少有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
函数式编程打破了工作量成小块并且做做一个简单的事情非常通用的任务。确定序列中是否至少有n
项目不是一项简单的任务。
你已经找到了这个“问题”的解决方案,现有算法的组成,它适用于大多数情况,并创建自己的算法来解决问题。
但是我不得不怀疑你的第一个解决方案是行不通的。 MoveNext()
在原始方法上仅被称为n
倍,Current
永远不会被调用,即使在某些包装类上调用了MoveNext()
,性能影响可能很小,除非n
很大。
编辑:
我很好奇,所以我写了一个简单的程序来测试这两种方法的时机。截断方法对于一个简单的无限序列和一个有Sleep(1)
更快。当你的修正听起来像过度工程时,看起来我是正确的。
我认为需要澄清以解释这些方法中发生了什么。 Seq.truncate
接受一个序列并返回一个序列。除了保存n
的值之外,枚举之前它不会执行任何操作。在枚举过程中,它计数并在n
之后停止。 Seq.length
需要枚举并计数,并在计数结束时返回。所以枚举只枚举一次,开销的数量是几个方法调用和两个计数器。
使用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"
这里是一个简短的,实用的解决方案:
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
+1任何想法,性能差异是什么样的? –
海量。对于'n = 10,000,000',第一个解决方案慢5倍。 – Daniel
我不禁在想,如果你的算法应该使用更合适的类型,而不是遍历序列。 – ChaosPandion
@ChaosPandion:相信我,我已经考虑过这件事。在我的辩护中,我想参考Luke Hoban标准偏差和基于事件的编程(http://blogs.msdn.com/b/lukeh/archive/2008/10/10/standard-deviation- and-event-based-programming.aspx) –