Author: Kevin Criss, Indiana University 1977-1984.
(I goofed off alot)
Very efficient way to search an array! Requires the array being searched to be pre-sorted in the sequence of your search key. This is a requirement!
PowerShell's compare-object cmdlet could not do the comparisons I was looking for, so I had to write this routine.
How does it work and why do they call it the Binary Search, are we manipulating bits 1 and 0? No, were not doing anything with bits just pieces. A binary search always cuts the array into two pieces at the middle point. Then it checks the item being searched for against the contents at the middle point. If the contents at the middle point is greater than the item being search, the current middle point becomes the new high point and the array is cut in half again and re-tested. If the contents at the middle point is less than the item being searched, the current middle point becomes the new low point and the array is cut in half again and re-tested. This cutting in half and adjusting either the high point or the low point is repeated until the item is found or the low point and the high point converge. This is much faster then sequentially searching an entire array.
All Sophomores at Indiana University were required to know and code this routine in the early 1980s. Shell/Bubble sorting too. We also had to write a Concordance in the PL1 programming language as well. That's counting and indexing each individual word in any given manuscript. Writing a Binary Search algorithm is easy, writing a Concordance is really hard. Junior year we had to write a two-pass assembler for the Motorola 6809 chipset using the FLEX OS. That was really, super hard, especially during summer school at Bloomington. Ah Spring in Paris, no way, I'll take summer in Bloomington any day! :) I even dove off the Breaking Away cliff, but that's another story. :)
A typical IU graduate of the period would be fluent in: Fortran, COBOL, Pascal, PL1, and Assembler. Lisp, Fourth, and Basic were also available at that time and quite popular too. I've written shell sorts and binary searches in every language I know. I think I'm fluent in nine or ten languages seven of which are now arcane or rather more like Latin who most consider to be a dead language. I hear they still speak Latin in Northern Europe though, and I think it's still being broadcast on short wave radio too. So there is still probably a lot of activity in the arcane programming languages as well.
Additional Reference:
http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
Thank you Mr. Bloch for sharing the patch to this classic algorithm via your Google Research Blog. I have incorporated the new formula you reported for calculating the $script:MiddlePoint into my routines.
The array must be sorted into YourObjectSearched sequence. I think this is the only line of code in this script that you'll have to modify. Substitute .YourObjectSearched with .TennisShoes, .Processes, .Telephone, or whatever it is that you are searching for in your array.
Returns
$script:ItemFound = $True and
$script:MiddlePoint indexing the location of the item
or
Returns
$script:ItemFound = $False and
$script:MiddlePoint equal to
the negative value of $YourOrderedArray.length +1
################################################
# Function: PowerShell Binary Search Algorithm #
################################################
#
function BinarySearch
{
Param ($YourOrderedArray, $ItemSearched)
[int] $LowIndex = 0
[int] $HigIndex = $YourOrderedArray.length - 1
while ($LowIndex -le $HigIndex)
{
# [int]$script:MiddlePoint = ($LowIndex + $HigIndex) / 2
[int]$script:MiddlePoint = $LowIndex + (($HigIndex - $LowIndex) / 2)
$InspectedValue = $YourOrderedArray[$script:MiddlePoint].YourObjectSearched
If ($InspectedValue -lt $ItemSearched)
{
$LowIndex = $script:MiddlePoint + 1
}
Elseif ($InspectedValue -gt $ItemSearched)
{
$HigIndex = $script:MiddlePoint - 1
}
Else
{
$script:ItemFound = $True
return
}
}
$script:ItemFound = $False
$script:MiddlePoint = -($LowIndex + 1)
return
}
So how would you call this function?
##################################################
Function: PowerShell Binary Search Algorithm #
##################################################
#
function BinarySearch
{
Param ( $YourOrderedArray, $ItemSearched)
#
# $YourOrderedArray=1,2,3,4,5,6,7,8,9,10 # Example
# $ItemSearched=7 # Example
#
# Returns ($script:ItemFound = $True and the $script:MiddlePoint indexing the location of the item)
# or
# Returns ($script:ItemFound = $False# and $script:MiddlePoint equal to the negative value of $YourOrderedArray.length +1)
#
[int] $LowIndex = 0
[int] $HighIndex = $YourOrderedArray.length - 1
If ($YourOrderedArray.length -eq $Null)
{
# It is conceivable you could import a CSV file into $YourOrderedArray that contains only one
# line of data. In this case you won't have an array of objects, you'll just have an object.
# $HighIndex will be equal to [int]$NULL which is zero plus a minus one. Therefore the *while loop*
# below never gets executed. You don't have an array of objects, you'll just have one object.
# Best-practice is to ensure you have a valid array before calling this Binary Search function.
#
# [int]$script:MiddlePoint = $LowIndex + (($HighIndex - $LowIndex) / 2)
# The niddlepoint now equals [int]-0.5 which computes to an interger zero.
#
If ($ItemSearched -eq $YourOrderedArray.FQDNservername)
{
$script:ItemFound = $True
return
}
Else
{
$script:ItemFound = $False
return
}
}
#
while ($LowIndex -le $HighIndex)
{
# Reference: http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html
# Thank you Mr. Bloch for sharing the patch to this classic algorithm via your Google Research Blog.
# I have incorporated the new formula you reported for calculating the $script:MiddlePoint
# into my routines. Wow, Two to the ThirtyFirst power minus one, that's a big number. :)
# I don't think my UpTime2HTML script would ever process that many servers to experience the reported
# overflow error. Interesting report though! Very nice article.
#
# [int]$script:MiddlePoint = ($LowIndex + $HighIndex) / 2
[int]$script:MiddlePoint = $LowIndex + (($HighIndex - $LowIndex) / 2)
$InspectedValue = $YourOrderedArray[$script:MiddlePoint].FQDNservername
If ($InspectedValue -lt $ItemSearched)
{
$LowIndex = $script:MiddlePoint + 1
}
Elseif ($InspectedValue -gt $ItemSearched)
{
$HighIndex = $script:MiddlePoint - 1
}
Else
{
$script:ItemFound = $True ### Item found
return
}
}
$script:ItemFound = $False ### Item not found.
$script:MiddlePoint = -($LowIndex + 1) ### The negative value of $YourOrderedArray.lenght +1
return
}
##
###################################
# Script Block Count Object #
###################################
#
$CountObjects =
{
$Script:ObjectsCounted++
}
#
#
###################################
# Script Block $WriteCSVfile #
###################################
#
$WriteCSVfile =
{
$Outputline = $_.FQDNServername+","+$_.OrganizationalUnit+","+$_.SystemName+","+$_.Environment
$Outputline Out-file Working.csv -append
}#
#########################################################################
############# Remove any defects from the good input File ###############
#########################################################################
#
# Its not very efficient to process a 100 or more bad severs on every# running of UpTime2HTML. So lets clean out the defective servers
# from our good master input file.
#
"R E M O V E D E F E C T S" Out-host
$A = import-csv Servers.csv sort-object -property Organizationalunit,Systemname,Environment,fqdnservername select-object FQDNservername,OrganizationalUnit,Systemname,Environment -unique
$script:ObjectsCounted = 0
$B = import-csv badservers.csv sort-object -property fqdnservername
$B foreach-object -process {&$CountObjects}
If ($script:ObjectsCounted -gt 0)
{
"Objects Counted = $script:objectsCounted writing new servers.csv file" out-host
"FQDNServername,OrganizationalUnit,SystemName,Environment" out-file working.csv
$A Foreach-object -process {
BinarySearch $B $_.FQDNservername
If ($ItemFound -eq $False) {&$WriteCSVfile}
}
import-csv working.csv export-csv servers.csv -notypeinformation
}
#
No comments:
Post a Comment