6 people like it.

Generating numerical ranges

Different ways of generating numerical ranges in F#. It turns out that the built-in syntax generates fairly slow code, so the snippet shows two alternative ways that are faster. Any compiler optimizations making the built-in one faster would be nice :-)

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
36: 
37: 
38: 
39: 
40: 
41: 
42: 
// Using built-in sequence range
// (This takes about 3.5-4sec on my machine)
let s = seq { for i in 0L .. 10000000L -> i }
s |> Seq.length

// Using a range generated by an imperative loop
// using inline to make this more reusable
// (This takes about 0.5sec on my machine)
let inline range lo hi = 
  seq { let i = ref lo
        while i.Value < hi do
          yield i.Value
          i.Value <- i.Value + LanguagePrimitives.GenericOne }

range 0L 10000000L
|> Seq.length

// We can make this even faster if we just write the
// interface implementation directly. This is ugly, but
// it takes some 250ms on my machine...
open System.Collections
open System.Collections.Generic

let inline range2 (lo:^T) (hi:^T) = 
  let one = LanguagePrimitives.GenericOne
  { new IEnumerable< ^T > with
      member x.GetEnumerator() =
        let current = ref (lo - one)
        { new IEnumerator< ^T > with
            member x.Current = current.Value
          interface IEnumerator with
            member x.Current = box current.Value
            member x.MoveNext() = 
              if current.Value > hi then false
              else current.Value <- current.Value + one; true
            member x.Reset() = current.Value <- lo - one
          interface System.IDisposable with
            member x.Dispose() = ()  }
    interface IEnumerable with
      member x.GetEnumerator() = (x :?> IEnumerable< ^T >).GetEnumerator() :> _ }

range2 0L 10000000L |> Seq.length
val s : seq<int64>

Full name: Script.s
Multiple items
val seq : sequence:seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
val i : int64
module Seq

from Microsoft.FSharp.Collections
val length : source:seq<'T> -> int

Full name: Microsoft.FSharp.Collections.Seq.length
val range : lo:'a -> hi:'a -> seq<'a> (requires member ( + ) and comparison and member get_One)

Full name: Script.range
val lo : 'a (requires member ( + ) and comparison and member get_One)
val hi : 'a (requires member ( + ) and comparison and member get_One)
val i : 'a ref (requires member ( + ) and comparison and member get_One)
Multiple items
val ref : value:'T -> 'T ref

Full name: Microsoft.FSharp.Core.Operators.ref

--------------------
type 'T ref = Ref<'T>

Full name: Microsoft.FSharp.Core.ref<_>
property Ref.Value: 'a
module LanguagePrimitives

from Microsoft.FSharp.Core
val GenericOne<'T (requires member get_One)> : 'T (requires member get_One)

Full name: Microsoft.FSharp.Core.LanguagePrimitives.GenericOne
namespace System
namespace System.Collections
namespace System.Collections.Generic
val range2 : lo:'T -> hi:'T -> IEnumerable<'T> (requires member ( - ) and comparison and member ( + ) and member get_One)

Full name: Script.range2
val lo : 'T (requires member ( - ) and comparison and member ( + ) and member get_One)
val hi : 'T (requires member ( - ) and comparison and member ( + ) and member get_One)
val one : 'a (requires member get_One and member ( - ) and member ( + ) and comparison)
Multiple items
type IEnumerable =
  member GetEnumerator : unit -> IEnumerator

Full name: System.Collections.IEnumerable

--------------------
type IEnumerable<'T> =
  member GetEnumerator : unit -> IEnumerator<'T>

Full name: System.Collections.Generic.IEnumerable<_>
val x : IEnumerable<'T> (requires member ( - ) and comparison and member ( + ) and member get_One)
IEnumerable.GetEnumerator() : IEnumerator<'T>
val current : 'T ref (requires member ( - ) and comparison and member ( + ) and member get_One)
Multiple items
type IEnumerator =
  member Current : obj
  member MoveNext : unit -> bool
  member Reset : unit -> unit

Full name: System.Collections.IEnumerator

--------------------
type IEnumerator<'T> =
  member Current : 'T

Full name: System.Collections.Generic.IEnumerator<_>
val x : IEnumerator<'T> (requires member ( - ) and comparison and member ( + ) and member get_One)
property IEnumerator.Current: 'T
property Ref.Value: 'T
val x : IEnumerator
property IEnumerator.Current: obj
val box : value:'T -> obj

Full name: Microsoft.FSharp.Core.Operators.box
IEnumerator.MoveNext() : bool
IEnumerator.Reset() : unit
type IDisposable =
  member Dispose : unit -> unit

Full name: System.IDisposable
val x : System.IDisposable
System.IDisposable.Dispose() : unit
val x : IEnumerable
IEnumerable.GetEnumerator() : IEnumerator
Raw view Test code New version

More information

Link:http://fssnip.net/no
Posted:10 years ago
Author:Tomas Petricek
Tags: range , sequences