rotations « Inviting Epiphany

Posts Tagged: rotations

Fun / Projects — 2 Comments
7
Dec 14

Developing an Algorithm in F#: Fast Rotational Alignments with Gosper’s Hack

This post is for the 7th day of the 2014 F# Advent Calendar.

It has been said that functional languages can’t be as fast as their imperative cousins because of all of the allocation and garbage collection, this is patently false (as far as F# is concerned at least) largely because the CLR has value types.

Recently Louis Thrall and I ran into an interesting problem at work: how do you efficiently compare all rotations of one array to another to select the best? This is easy when the arrays are the same size, just shift the indices around:

Which is equivalent to a nested for loop, the top one rotating and the inner doing comparisons.

But what about differently sized arrays? It turns out this is more complicated, even for comparing a size 2 array to size 3:

Like comparing beads on two strings, there is much shifting as the indices are rotated around. The extra freedom from this shifting means that more comparisons must be made even though there total number of combined elements is smaller.

This problem also has an interesting structure, as it costs the most when one array is about half the size of the other. When the smaller array is size 1 then it simply needs to be moved around, and when the arrays are equal in size it’s a simple matter of rotations.

After some research Lou noted that this we were “counting the number of cyclic suborders of size k of a cyclic order of size n” which produces k(n choose k) different configurations.

Now that we had bounds and knew what we were doing was reasonable we had to figure out an algorithm for this process. It occurred to us that it would be ideal to pre-compute the comparison values to avoid repeated comparisons. Given this matrix of comparison values it wasn’t too difficult to determine a procedure for checking all possible configurations.

Each time a pair is chosen, it further constrains what the rest of the assignments may be. The bottom level is somewhat obvious, just select each of the possible starting combinations down the y-axis. In the next column you potentially have a range of possible “downward” (using clock arithmetic) selections bounded by the difference in lengths and what has already been fixed.

Now it was time to implement, and the first stab was nice and concise and functional and worked pretty well.

 1: open System
 2: 
 3: // arr1 is always equal in size or smaller than arr2
 4: let bestRot (f: 'a -> 'a -> float) (arr1: 'a []) (arr2: 'a []) =
 5:     // Pre-calculate similarities
 6:     let scores = 
 7:         Array2D.init arr1.Length arr2.Length 
 8:                     (fun i j -> f arr1.[i] arr2.[j])
 9:     // inner function for recursively finding paths
10:     // col = previous column, prow = previous row
11:     // df = degrees of freedom, path = path accumulator
12:     let rec inner col prow df path =
13:         seq {
14:             // when we're out of columns to assign we're done
15:             if col >= arr1.Length then yield path |> List.rev
16:             else
17:                 // We have df "degrees of freedom" left
18:                 for d = 1 to df + 1 do 
19:                     // Clock arithmetic for the row
20:                     let nrow = (prow + d) % arr2.Length
21:                     // Recurse yielding out all further paths
22:                     yield! inner (col + 1) nrow (df + 1 - d) 
23:                                  ((col, nrow) :: path)           
24:         }
25:     let res, score =
26:         // the difference in length 
27:         // is the starting "degrees of freedom"
28:         let diff = arr2.Length - arr1.Length
29:         seq {
30:             // for each y-axis starting point
31:             for y = 0 to arr2.Length - 1 do
32:                 // 1 selected, r is the starting point (on y), 
33:                 //    starting is always 0 on x. 
34:                 // ((0, y) :: []) is the accumulator 
35:                 //    with the initial (0, y) coordinates
36:                 yield! inner 1 y diff ((0, y) :: [])
37:         } 
38:         // Sum each path to find total similarity
39:         |> Seq.map 
40:             (fun l -> l, l |> Seq.sumBy (fun (i,j) -> scores.[i,j]))
41:         // Get the path with the highest similarity
42:         |> Seq.maxBy snd
43:     // Create output array and copy in the results
44:     let out = Array.create arr1.Length Int32.MinValue
45:     for (i,j) in res do
46:         out.[i] <- j
47:     // Return results
48:     out, score

namespace System

val bestRot : ('a -> 'a -> float) -> 'a [] -> 'a [] -> int [] * float

Full name: Snippet.bestRot

val f : ('a -> 'a -> float)

Multiple items
val float : 'T -> float (requires member op_Explicit)

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

——————–
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

  type: float<'Measure>
  implements: IComparable
  implements: IConvertible
  implements: IFormattable
  implements: IComparable<float<'Measure>>
  implements: IEquatable<float<'Measure>>
  inherits: ValueType

——————–
type float = Double

Full name: Microsoft.FSharp.Core.float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val arr1 : 'a []

  type: 'a []
  implements: ICloneable
  implements: Collections.IList
  implements: Collections.ICollection
  implements: Collections.IStructuralComparable
  implements: Collections.IStructuralEquatable
  implements: Collections.Generic.IList<'a>
  implements: Collections.Generic.ICollection<'a>
  implements: seq<'a>
  implements: Collections.IEnumerable
  inherits: Array

val arr2 : 'a []

val scores : float [,]

  type: float [,]
  implements: ICloneable
  implements: Collections.IList
  implements: Collections.ICollection
  implements: Collections.IEnumerable
  implements: Collections.IStructuralComparable
  implements: Collections.IStructuralEquatable
  inherits: Array

module Array2D

from Microsoft.FSharp.Collections

val init : int -> int -> (int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init

property Array.Length: int

val i : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val j : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val inner : (int -> int -> int -> (int * int) list -> seq<(int * int) list>)

val col : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val prow : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val df : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val path : (int * int) list

  type: (int * int) list
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<int * int>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<int * int>
  implements: Collections.IEnumerable

Multiple items
val seq : seq<'T> -> seq<'T>

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

——————–
type seq<'T> = Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>

type: seq<'T>
inherits: Collections.IEnumerable

Multiple items
module List

from Microsoft.FSharp.Collections

——————–
type List<'T> =
  | ( [] )
  | ( :: ) of 'T * 'T list
  with
    interface Collections.IEnumerable
    interface Collections.Generic.IEnumerable<'T>
    member Head : 'T
    member IsEmpty : bool
    member Item : index:int -> 'T with get
    member Length : int
    member Tail : 'T list
    static member Cons : head:'T * tail:'T list -> 'T list
    static member Empty : 'T list
  end

Full name: Microsoft.FSharp.Collections.List<_>

  type: List<'T>
  implements: Collections.IStructuralEquatable
  implements: IComparable<List<'T>>
  implements: IComparable
  implements: Collections.IStructuralComparable
  implements: Collections.Generic.IEnumerable<'T>
  implements: Collections.IEnumerable

val rev : 'T list -> 'T list

Full name: Microsoft.FSharp.Collections.List.rev

val d : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val nrow : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val res : (int * int) list

val score : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val diff : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val y : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

module Seq

from Microsoft.FSharp.Collections

val map : ('T -> 'U) -> seq<'T> -> seq<'U>

Full name: Microsoft.FSharp.Collections.Seq.map

val l : (int * int) list

val sumBy : ('T -> 'U) -> seq<'T> -> 'U (requires member ( + ) and member get_Zero)

Full name: Microsoft.FSharp.Collections.Seq.sumBy

val maxBy : ('T -> 'U) -> seq<'T> -> 'T (requires comparison)

Full name: Microsoft.FSharp.Collections.Seq.maxBy

val snd : ('T1 * 'T2) -> 'T2

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

val out : int []

  type: int []
  implements: ICloneable
  implements: Collections.IList
  implements: Collections.ICollection
  implements: Collections.IStructuralComparable
  implements: Collections.IStructuralEquatable
  implements: Collections.Generic.IList<int>
  implements: Collections.Generic.ICollection<int>
  implements: seq<int>
  implements: Collections.IEnumerable
  inherits: Array

type Array =
  class
    member Clone : unit -> obj
    member CopyTo : System.Array * int -> unit
    member CopyTo : System.Array * int64 -> unit
    member GetEnumerator : unit -> System.Collections.IEnumerator
    member GetLength : int -> int
    member GetLongLength : int -> int64
    member GetLowerBound : int -> int
    member GetUpperBound : int -> int
    member GetValue : int [] -> obj
    member GetValue : int -> obj
    member GetValue : int64 -> obj
    member GetValue : int64 [] -> obj
    member GetValue : int * int -> obj
    member GetValue : int64 * int64 -> obj
    member GetValue : int * int * int -> obj
    member GetValue : int64 * int64 * int64 -> obj
    member Initialize : unit -> unit
    member IsFixedSize : bool
    member IsReadOnly : bool
    member IsSynchronized : bool
    member Length : int
    member LongLength : int64
    member Rank : int
    member SetValue : obj * int -> unit
    member SetValue : obj * int [] -> unit
    member SetValue : obj * int64 -> unit
    member SetValue : obj * int64 [] -> unit
    member SetValue : obj * int * int -> unit
    member SetValue : obj * int64 * int64 -> unit
    member SetValue : obj * int * int * int -> unit
    member SetValue : obj * int64 * int64 * int64 -> unit
    member SyncRoot : obj
    static member AsReadOnly<'T> : 'T [] -> System.Collections.ObjectModel.ReadOnlyCollection<'T>
    static member BinarySearch : System.Array * obj -> int
    static member BinarySearch<'T> : 'T [] * 'T -> int
    static member BinarySearch : System.Array * obj * System.Collections.IComparer -> int
    static member BinarySearch<'T> : 'T [] * 'T * System.Collections.Generic.IComparer<'T> -> int
    static member BinarySearch : System.Array * int * int * obj -> int
    static member BinarySearch<'T> : 'T [] * int * int * 'T -> int
    static member BinarySearch : System.Array * int * int * obj * System.Collections.IComparer -> int
    static member BinarySearch<'T> : 'T [] * int * int * 'T * System.Collections.Generic.IComparer<'T> -> int
    static member Clear : System.Array * int * int -> unit
    static member ConstrainedCopy : System.Array * int * System.Array * int * int -> unit
    static member ConvertAll<'TInput,'TOutput> : 'TInput [] * System.Converter<'TInput,'TOutput> -> 'TOutput []
    static member Copy : System.Array * System.Array * int -> unit
    static member Copy : System.Array * System.Array * int64 -> unit
    static member Copy : System.Array * int * System.Array * int * int -> unit
    static member Copy : System.Array * int64 * System.Array * int64 * int64 -> unit
    static member CreateInstance : System.Type * int -> System.Array
    static member CreateInstance : System.Type * int [] -> System.Array
    static member CreateInstance : System.Type * int64 [] -> System.Array
    static member CreateInstance : System.Type * int * int -> System.Array
    static member CreateInstance : System.Type * int [] * int [] -> System.Array
    static member CreateInstance : System.Type * int * int * int -> System.Array
    static member Exists<'T> : 'T [] * System.Predicate<'T> -> bool
    static member Find<'T> : 'T [] * System.Predicate<'T> -> 'T
    static member FindAll<'T> : 'T [] * System.Predicate<'T> -> 'T []
    static member FindIndex<'T> : 'T [] * System.Predicate<'T> -> int
    static member FindIndex<'T> : 'T [] * int * System.Predicate<'T> -> int
    static member FindIndex<'T> : 'T [] * int * int * System.Predicate<'T> -> int
    static member FindLast<'T> : 'T [] * System.Predicate<'T> -> 'T
    static member FindLastIndex<'T> : 'T [] * System.Predicate<'T> -> int
    static member FindLastIndex<'T> : 'T [] * int * System.Predicate<'T> -> int
    static member FindLastIndex<'T> : 'T [] * int * int * System.Predicate<'T> -> int
    static member ForEach<'T> : 'T [] * System.Action<'T> -> unit
    static member IndexOf : System.Array * obj -> int
    static member IndexOf<'T> : 'T [] * 'T -> int
    static member IndexOf : System.Array * obj * int -> int
    static member IndexOf<'T> : 'T [] * 'T * int -> int
    static member IndexOf : System.Array * obj * int * int -> int
    static member IndexOf<'T> : 'T [] * 'T * int * int -> int
    static member LastIndexOf : System.Array * obj -> int
    static member LastIndexOf<'T> : 'T [] * 'T -> int
    static member LastIndexOf : System.Array * obj * int -> int
    static member LastIndexOf<'T> : 'T [] * 'T * int -> int
    static member LastIndexOf : System.Array * obj * int * int -> int
    static member LastIndexOf<'T> : 'T [] * 'T * int * int -> int
    static member Resize<'T> : 'T [] * int -> unit
    static member Reverse : System.Array -> unit
    static member Reverse : System.Array * int * int -> unit
    static member Sort : System.Array -> unit
    static member Sort<'T> : 'T [] -> unit
    static member Sort : System.Array * System.Array -> unit
    static member Sort : System.Array * System.Collections.IComparer -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] -> unit
    static member Sort<'T> : 'T [] * System.Collections.Generic.IComparer<'T> -> unit
    static member Sort<'T> : 'T [] * System.Comparison<'T> -> unit
    static member Sort : System.Array * int * int -> unit
    static member Sort : System.Array * System.Array * System.Collections.IComparer -> unit
    static member Sort<'T> : 'T [] * int * int -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * System.Collections.Generic.IComparer<'TKey> -> unit
    static member Sort : System.Array * System.Array * int * int -> unit
    static member Sort : System.Array * int * int * System.Collections.IComparer -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int -> unit
    static member Sort<'T> : 'T [] * int * int * System.Collections.Generic.IComparer<'T> -> unit
    static member Sort : System.Array * System.Array * int * int * System.Collections.IComparer -> unit
    static member Sort<'TKey,'TValue> : 'TKey [] * 'TValue [] * int * int * System.Collections.Generic.IComparer<'TKey> -> unit
    static member TrueForAll<'T> : 'T [] * System.Predicate<'T> -> bool
  end

Full name: System.Array

  type: Array
  implements: ICloneable
  implements: Collections.IList
  implements: Collections.ICollection
  implements: Collections.IEnumerable
  implements: Collections.IStructuralComparable
  implements: Collections.IStructuralEquatable

val create : int -> 'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create

type Int32 =
  struct
    member CompareTo : obj -> int
    member CompareTo : int -> int
    member Equals : obj -> bool
    member Equals : int -> bool
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> System.TypeCode
    member ToString : unit -> string
    member ToString : string -> string
    member ToString : System.IFormatProvider -> string
    member ToString : string * System.IFormatProvider -> string
    static val MaxValue : int
    static val MinValue : int
    static member Parse : string -> int
    static member Parse : string * System.Globalization.NumberStyles -> int
    static member Parse : string * System.IFormatProvider -> int
    static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> int
    static member TryParse : string * int -> bool
    static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * int -> bool
  end

Full name: System.Int32

  type: Int32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

field Int32.MinValue = -2147483648

However, after real world trials we found that it was taking an astonishing 20% of our runtime. We had to find a better way. We soon found Gosper’s hack which did mostly what we wanted. It gave us the combinations, and we found we could just rotate each of those around to give us all of our cyclic suborders.

And so we went about rewriting our nice functional sample to use Gosper’s Hack to avoid the need to generate paths and also to be (nearly) minimally allocating to avoid garbage collection overhead.

 1: open System
 2: 
 3: // arr1 is always equal in size or smaller than arr2
 4: let bestRotGos (f: 'a -> 'a -> float) (arr1: 'a []) (arr2: 'a []) =
 5:     // Start Gosper's Hack Machinery Bootstrap
 6:     let bitsConfig = Array.create arr1.Length Int32.MinValue
 7:    
 8:     let inline setBits v =
 9:         let inline getBit x i = x &&& (1 <<< i) <> 0
10:         let mutable idx = 0
11:         for i = 0 to 31 do
12:             if getBit v i then
13:                 bitsConfig.[idx] <- i
14:                 idx <- idx + 1
15:  
16:     let inline nextGosper set =
17:         let c = set &&& -set
18:         let r = set + c
19:         r + (((r^^^set)/c)>>>2)
20:         
21:     let limit =
22:         let n = arr2.Length
23:         (1 <<< n)
24:  
25:     let mutable set =
26:         let k = arr1.Length
27:         (1 <<< k) - 1    
28:     // End Gosper's Hack Machinery Bootstrap
29: 
30:     // Pre-calculate sims and init placeholder variables
31:     let scores = Array2D.init arr1.Length arr2.Length 
32:                     (fun i j -> f arr1.[i] arr2.[j])    
33:                         
34:     let mutable maxScore = Double.NegativeInfinity
35:     let bestConfig = Array.create arr1.Length Int32.MinValue
36: 
37:     while (set < limit) do
38:         setBits set // Turn "set" bits into indices in "bitsConfig"
39: 
40:         // For each rotation
41:         for i = 0 to bitsConfig.Length - 1 do
42: 
43:             // calculate score and compare with previous best
44:             let mutable totalScore = 0.0
45:             for i = 0 to bitsConfig.Length - 1 do
46:                 let tokenScore = scores.[i,bitsConfig.[i]]
47:                 totalScore <- totalScore + tokenScore
48:             if totalScore > maxScore then
49:                 // and replace if better
50:                 maxScore <- totalScore
51:                 Array.blit bitsConfig 0 
52:                            bestConfig 0 
53:                            bitsConfig.Length 
54: 
55:             // Rotate the array
56:             let firstElement = bitsConfig.[0]
57:             for i = 0 to bitsConfig.Length - 2 do
58:                 bitsConfig.[i] <- bitsConfig.[i + 1]
59:             bitsConfig.[bitsConfig.Length - 1] <- firstElement
60:         
61:         set <- nextGosper set // Put the next combination in "set"
62:     bestConfig, maxScore

namespace System

val bestRotGos : ('a -> 'a -> float) -> 'a [] -> 'a [] -> int [] * float

Full name: Snippet.bestRotGos

val f : ('a -> 'a -> float)

Multiple items
val float : 'T -> float (requires member op_Explicit)

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

——————–
type float<'Measure> = float

Full name: Microsoft.FSharp.Core.float<_>

——————–
type float = Double

Full name: Microsoft.FSharp.Core.float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val arr1 : 'a []

val arr2 : 'a []

val bitsConfig : int []

Full name: System.Array

val create : int -> 'T -> 'T []

Full name: Microsoft.FSharp.Collections.Array.create

property Array.Length: int

Full name: System.Int32

  type: Int32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

field Int32.MinValue = -2147483648

val setBits : (int -> unit)

val v : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val getBit : (int -> int32 -> bool)

val x : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val i : int32

  type: int32
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val mutable idx : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val i : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val nextGosper : ('b -> 'd) (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))

val set : 'b (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))

val c : 'b (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))

val r : 'b (requires member ( ~- ) and member ( &&& ) and member ( + ) and member ( ^^^ ) and member ( / ) and member ( + ) and member ( >>> ))

val limit : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val n : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val mutable set : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val k : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val scores : float [,]

module Array2D

from Microsoft.FSharp.Collections

val init : int -> int -> (int -> int -> 'T) -> 'T [,]

Full name: Microsoft.FSharp.Collections.Array2D.init

val j : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

val mutable maxScore : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

type Double =
  struct
    member CompareTo : obj -> int
    member CompareTo : float -> int
    member Equals : obj -> bool
    member Equals : float -> bool
    member GetHashCode : unit -> int
    member GetTypeCode : unit -> System.TypeCode
    member ToString : unit -> string
    member ToString : string -> string
    member ToString : System.IFormatProvider -> string
    member ToString : string * System.IFormatProvider -> string
    static val MinValue : float
    static val MaxValue : float
    static val Epsilon : float
    static val NegativeInfinity : float
    static val PositiveInfinity : float
    static val NaN : float
    static member IsInfinity : float -> bool
    static member IsNaN : float -> bool
    static member IsNegativeInfinity : float -> bool
    static member IsPositiveInfinity : float -> bool
    static member Parse : string -> float
    static member Parse : string * System.Globalization.NumberStyles -> float
    static member Parse : string * System.IFormatProvider -> float
    static member Parse : string * System.Globalization.NumberStyles * System.IFormatProvider -> float
    static member TryParse : string * float -> bool
    static member TryParse : string * System.Globalization.NumberStyles * System.IFormatProvider * float -> bool
  end

Full name: System.Double

  type: Double
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

field Double.NegativeInfinity = -Infinity

val bestConfig : int []

val mutable totalScore : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val tokenScore : float

  type: float
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<float>
  implements: IEquatable<float>
  inherits: ValueType

val blit : 'T [] -> int -> 'T [] -> int -> int -> unit

Full name: Microsoft.FSharp.Collections.Array.blit

val firstElement : int

  type: int
  implements: IComparable
  implements: IFormattable
  implements: IConvertible
  implements: IComparable<int>
  implements: IEquatable<int>
  inherits: ValueType

A quick test shows that the new algorithm is about seven times faster across a variety of test inputs:

 1: let f x y = if x = y then 1.0 else 0.0
 2: 
 3: let cmp = [|"one"; "two"; "three"; "four"|]
 4: let cmps = 
 5:     [| for i = 0 to cmp.Length - 1 do 
 6:            for j = i to cmp.Length - 1 do 
 7:                // Longer array is second
 8:                yield cmp.[j..], cmp.[i..] 
 9:     |] 
10: 
11: #time
12: for i = 0 to 1000000 do
13:     for c1,c2 in cmps do 
14:         bestRot f c1 c2 |> ignore
15: //Real: 00:00:41.800, CPU: 00:00:41.812, 
16: // GC gen0: 10175, gen1: 6, gen2: 1
17: #time 
18: 
19: #time
20: for i = 0 to 1000000 do
21:     for c1,c2 in cmps do 
22:         bestRotGos f c1 c2 |> ignore
23: //Real: 00:00:06.378, CPU: 00:00:06.375, 
24: // GC gen0: 689, gen1: 1, gen2: 0
25: #time 
26:

val f : 'a -> 'a -> float (requires equality)

Full name: Snippet.f

val x : 'a (requires equality)

val y : 'a (requires equality)

val cmp : string []

Full name: Snippet.cmp

  type: string []
  implements: System.ICloneable
  implements: System.Collections.IList
  implements: System.Collections.ICollection
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.IStructuralEquatable
  implements: System.Collections.Generic.IList<string>
  implements: System.Collections.Generic.ICollection<string>
  implements: seq<string>
  implements: System.Collections.IEnumerable
  inherits: System.Array

val cmps : (string [] * string []) []

Full name: Snippet.cmps

  type: (string [] * string []) []
  implements: System.ICloneable
  implements: System.Collections.IList
  implements: System.Collections.ICollection
  implements: System.Collections.IStructuralComparable
  implements: System.Collections.IStructuralEquatable
  implements: System.Collections.Generic.IList<string [] * string []>
  implements: System.Collections.Generic.ICollection<string [] * string []>
  implements: seq<string [] * string []>
  implements: System.Collections.IEnumerable
  inherits: System.Array

val i : int

  type: int
  implements: System.IComparable
  implements: System.IFormattable
  implements: System.IConvertible
  implements: System.IComparable<int>
  implements: System.IEquatable<int>
  inherits: System.ValueType

property System.Array.Length: int

val j : int

val c1 : string []

val c2 : string []

val ignore : 'T -> unit

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

Of course, there are a few more things that could be done to make this even faster mostly related to further reducing allocations. For example, we could potentially use larger fixed sized arrays if we knew our input was bounded and pass in the arrays as references letting the calling function handle proper recycling.

However, at this point the function no longer appeared anywhere near significant when profiling our overall usage and so we found this was fast enough. It’s not worth making things uglier and more prone to breakage for minor gains when what we have right now is a referentially transparent function with predictable behavior.

Inviting Epiphany
A programmer's chronicle of insights and discoveries

Posts Tagged: rotations

Developing an Algorithm in F#: Fast Rotational Alignments with Gosper’s Hack

Meta

Rick's

Recent Posts

User

Inviting Epiphany A programmer's chronicle of insights and discoveries

Posts Tagged: rotations

Developing an Algorithm in F#: Fast Rotational Alignments with Gosper’s Hack

Meta

Rick's

Recent Posts

User

Inviting Epiphany
A programmer's chronicle of insights and discoveries