The code below shows two ways to code a binary search. The difference is not great, but to my mind at least, the first example is a more traditional implementation, while the second has more of a functional flavor. In the first example (suffixed with “0”), the test value is passed around as a parameter and the comparison function takes two arguments. In the second example (suffixed with “1”), the test value is bound to a comparison function which only takes a single argument. (As always, all the code here is presented "as-is" and without warranty or implied fitness of any kind; use at your own risk.)

My questions were: what are the differences between the generated IL, and which method is more efficient? Looking at the IL using reflection, the result was obvious:

**In the version of F# that ships with VS2010, compiled in release mode, the two examples generate identical code.**

Which I must admit was a pleasant surprise.

let inline bsearch0 (cmp:'V0->'V1->int) (a:'V0[]) (v:'V1) =

let rec f lo hi =

match lo>hi with

| true -> None

` | _ ->`

let mid = lo+(hi-lo)/2

match cmp a.[mid] v with

| 0 -> Some(a.[mid])

| x when x<0 -> f (mid+1) hi

| _ -> f lo (mid-1)

f 0 (a.Length-1)

let inline bsearch1 (cmp:'V0->int) (a:'V0[]) =

let rec f lo hi =

match lo>hi with

| true -> None

` | _ ->`

let mid = lo+(hi-lo)/2

match cmp a.[mid] with

| 0 -> Some(a.[mid])

| x when x<0 -> f (mid+1) hi

| _ -> f lo (mid-1)

f 0 (a.Length-1)

type T = { A:int; B:int; }

let search0 (a:T[]) i =

let f (t:T) i = t.A-i

bsearch0 f a i

let search1 (a:T[]) i =

let f (t:T) = t.A-i

bsearch1 f a

`printfn "Your breakpoint here."`

## No comments:

Post a Comment