CODEWITHSUNDEEP
f#
Gene Belitski
Gene Belitski

Reputation: 10350

How to efficiently find out if a sequence has at least n items?

Just naively using Seq.length may be not good enough as will blow up on infinite sequences.

Getting more fancy with using something like ss |> Seq.truncate n |> Seq.length will work, but behind the scene would involve double traversing of the argument sequence chunk by IEnumerator's MoveNext().

The best approach I was able to come up with so far is:

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

This involves only single sequence traverse (more accurately, performing e.MoveNext() n times) and correctly handles boundary cases of empty and infinite sequences. I can further throw in few small improvements like explicit processing of specific cases for lists, arrays, and ICollections, or some cutting on traverse length, but wonder if any more effective approach to the problem exists that I may be missing?

Thank you for your help.

EDIT: Having on hand 5 overall implementation variants of hasAtLeast function (2 my own, 2 suggested by Daniel and one suggested by Ankur) I've arranged a marathon between these. Results that are tie for all implementations prove that Guvante is right: a simplest composition of existing algorithms would be the best, there is no point here in overengineering.

Further throwing in the readability factor I'd use either my own pure F#-based

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

or suggested by Ankur the fully equivalent Linq-based one that capitalizes on .NET integration

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

Upvotes: 3

Views: 554

Answers (3)

Daniel
Daniel

Reputation: 47904

Here's a short, functional solution:

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

Example:

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

And here's an optimally efficient one:

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

Upvotes: 3

Guvante
Guvante

Reputation: 19203

Functional programming breaks up work loads into small chunks that do very generic tasks that do one simple thing. Determining if there are at least n items in a sequence is not a simple task.

You already found both the solutions to this "problem", composition of existing algorithms, which works for the majority of cases, and creating your own algorithm to solve the issue.

However I have to wonder whether your first solution wouldn't work. MoveNext() is only called n times on the original method for certain, Current is never called, and even if MoveNext() is called on some wrapper class the performance implications are likely tiny unless n is huge.

EDIT:

I was curious so I wrote a simple program to test out the timing of the two methods. The truncate method was quicker for a simple infinite sequence and one that had Sleep(1). It looks like I was right when your correction sounded like overengineering.

I think clarification is needed to explain what is happening in those methods. Seq.truncate takes a sequence and returns a sequence. Other than saving the value of n it doesn't do anything until enumeration. During enumeration it counts and stops after n values. Seq.length takes an enumeration and counts, returning the count when it ends. So the enumeration is only enumerated once, and the amount of overhead is a couple of method calls and two counters.

Upvotes: 1

Ankur
Ankur

Reputation: 33637

Using Linq this would be as simple as:

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

Seq take method blows up if there are not enough elements.

Example usage to show it traverse seq only once and till required elements:

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

Upvotes: 1

Related Questions