Monday, April 23, 2012

On using BinarySearch and IComparer in Powershell:Part I

The Binary Search algorithm is exposed in Powershell v3.0 . It is not clear to me how to implement System.Collections.IComparer  as of yet. However, even without IComparer, Powershell's BinarySearch  has some usefulness.  Here are the overloads: 

 [Array]::BinarySearch.OverloadDefinitions
static int BinarySearch(array array, System.Object value)
static int BinarySearch(array array, int index, int length, System.Object value)
static int BinarySearch(array array, System.Object value, System.Collections.IComparer comparer)
static int BinarySearch(array array, int index, int length, System.Object value, System.Collections.IComparer comparer)
static int BinarySearch[T](T[] array, T value)
static int BinarySearch[T](T[] array, T value, System.Collections.Generic.IComparer[T] comparer)
static int BinarySearch[T](T[] array, int index, int length, T value)
static int BinarySearch[T](T[] array, int index, int length, T value, System.Collections.Generic.IComparer[T] comparer)


The key to using static int BinarySearch(array array, System.Object value) appears to be using it in a sorted list composed of items of similar types.  For this, it is much faster than 'where-object'.

[code]
[array]$array=0..10000
measure-command {$array | where {$_ -eq "5000"}}
measure-command {[Array]::BinarySearch($array,5000)}

$string_array="abcd","defg","hijk","lmno","pqrs","tuvw","xyza"
measure-command {$string_array | where {$_ -eq "abcd"}}
measure-command {[Array]::BinarySearch($array,"abcd")}

[results]
PS>measure-command {[Array]::BinarySearch($array,5000)}
Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 1
Ticks             : 15343
TotalDays         : 1.77581018518519E-08
TotalHours        : 4.26194444444444E-07
TotalMinutes      : 2.55716666666667E-05
TotalSeconds      : 0.0015343
TotalMilliseconds : 1.5343

PS>measure-command {$array | where {$_ -eq "5000"}}
Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 807
Ticks             : 8076803
TotalDays         : 9.34815162037037E-06
TotalHours        : 0.000224355638888889
TotalMinutes      : 0.0134613383333333
TotalSeconds      : 0.8076803
TotalMilliseconds : 807.6803


PS C:\cygwin\var\log> $string_array="abcd","defg","hijk","lmno","pqrs","tuvw","xyza"
PS C:\cygwin\var\log> measure-command {$string_array | where {$_ -eq "abcd"}}
Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 5
Ticks             : 51289
TotalDays         : 5.93622685185185E-08
TotalHours        : 1.42469444444444E-06
TotalMinutes      : 8.54816666666667E-05
TotalSeconds      : 0.0051289
TotalMilliseconds : 5.1289

PS C:\cygwin\var\log> measure-command {[Array]::BinarySearch($array,"abcd")}
Days              : 0
Hours             : 0
Minutes           : 0
Seconds           : 0
Milliseconds      : 0
Ticks             : 6933
TotalDays         : 8.02430555555556E-09
TotalHours        : 1.92583333333333E-07
TotalMinutes      : 1.1555E-05
TotalSeconds      : 0.0006933
TotalMilliseconds : 0.6933

[code]
[array]$array=0..10000
[Array]::BinarySearch($array,5000)
[Array]::BinarySearch($array,5000,5000,5000)

[array]$rand_array=foreach ($i in (1..10000)) {get-random -min 0 -max 10000}
[Array]::BinarySearch($rand_array,5000)
[array]$sort_rand_array=$rand_array | Sort
[array]$s_rand_array=$sort_rand_array
[Array]::BinarySearch($s_rand_array,5000)

[results]
# This works well:
PS>[array]$array=0..10000
PS>[Array]::BinarySearch($array,5000)
5000
PS>[Array]::BinarySearch($array,5000,5000,5000)
5000
#This does not work:
PS>[array]$rand_array=foreach ($i in (1..10000)) {get-random -min 0 -max 10000}
PS>[Array]::BinarySearch($rand_array,5000)
-8826
#This doesn't work either?:
PS>[array]$sort_rand_array=$rand_array | Sort
PS>[array]$s_rand_array=$sort_rand_array
PS>[Array]::BinarySearch($s_rand_array,5000)
-5008

No comments: