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 []
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 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
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
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
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
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<'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 []
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 bitsConfig : 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
property Array.Length: int
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
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 [,]
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
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 []
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
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
type: int
implements: System.IComparable
implements: System.IFormattable
implements: System.IConvertible
implements: System.IComparable<int>
implements: System.IEquatable<int>
inherits: System.ValueType
val c1 : string []
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 c2 : string []
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 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.