Przeglądałem książkę o algorytmach i strukturach danych i postanowiłem zaimplementować przeszukiwanie tablicy w PowerShellu. Założenie jest takie, że może występować w tablicy więcej niż jeden szukany element oraz funkcja przeszukująca powinna zwrócić numery indeksów szukanego elementu. Najprostszy algorytm przeszukiwania sekwencyjnego jest prosty:
function Search-Sequential([array]$arr, $item, [switch]$firstfound)
{
$found=@()
for($i=0; $i -lt $arr.Length; $i++)
{
if($arr[$i].Equals($item) )
{
$found+=$i
if($firstfound)
{
return $found
}
}
}
return $found
}
Użycie funkcji jest intuicyjne:
$arr = 1,2,3,4,4,4,4,4,5,5,5,6,6,7,8,99,120
Search-Sequential -arr $arr -item 5 #8,9,10
Drugim ciekawym algorytmem przeszukiwania jest przeszukiwanie binarne:
function Search-Binare([array]$arr, $item, [switch]$firstfound)
{
$low =0
$high = $arr.Length -1
$found=@()
While($low -le $high)
{
$middleIdx = [math]::Floor(($low + $high)/2)
$middleValue = $arr[$middleIdx]
if($middleValue -lt $item)
{
$low = $middleIdx+1
}
elseif($middleValue -gt $item)
{
$high = $middleIdx -1
}
else{
$found+=$middleIdx
if(!$firstfound)
{
$leftNeighborMiddleIdx = $middleIdx-1
if($low -le $leftNeighborMiddleIdx)
{
$leftArr = $arr[$low..$leftNeighborMiddleIdx]
$foundOnLeftWithOffset =
Search-Binare -arr $leftArr -item $item -firstfound:$firstfound
$foundOnLeft = $foundOnLeftWithOffset |
%{ $low + $_ }
$found+=$foundOnLeft
}
$rightNeighborMiddleIdx = $middleIdx+1
if($rightNeighborMiddleIdx -le $high)
{
$rightArr = $arr[$rightNeighborMiddleIdx..$high]
$foundOnRightWithOffset =
Search-Binare -arr $rightArr -item $item -firstfound:$firstfound
$foundOnRigh = $foundOnRightWithOffset |
%{$rightNeighborMiddleIdx + $_}
$found+=$foundOnRigh
}
}
return $found
}
}
}
Niestety musiałem dodać wywołanie rekurencyjne, aby przeszukał sąsiednie elementy. Przeszukiwanie binarne dla tej samej tabeli zwraca te same elementy, ale w innej kolejności:
Search-Binare -arr $arr -item 5 #8,10,9
Postanowiłem napisać jeszcze jeden alg. za pomocą tablicy haszującej. Na samym początku potrzebowalibyśmy funkcji do przekształcenia zwyczajnej tablicy na hashtable:
function ConvertTo-Hashtable(
[array]$arr,
[scriptblock]$hashFunction =
$({param($x) return $x.GetHashCode()}))
{
[array]$hashTable = @(,$null) * 100
for($i=0; $i -lt $arr.Length; $i++)
{
$item = $arr[$i]
$hashCode = $hashFunction.InvokeReturnAsIs($item)
$diff = $hashCode - $hashTable.Length
if($diff -ge 0)
{
$hashTable += @(,$null) * ($diff +1)
}
if(-not($hashTable[$hashCode]))
{
$hashTable[$hashCode] =@()
}
$hashTable[$hashCode] += $i
}
return $hashTable
}
Warto zauważyć tutaj jaka jest funkcja haszująca. Korzystamy z ogólnodostępnej funkcji GetHashCode.
Funkcja haszująca jest zapisana w script bloku. Konwersja i wyszukiwanie wygląda następująco:
$arr = 1,2,3,4,4,4,4,4,5,5,5,6,6,7,8,99,120
$hashtable = ConvertTo-Hashtable -arr $arr
Search-Hashed -arr $hashtable -item 5 #8,9,10
Natomiast funkcja przeszukująca tablice haszującą ma 2 linijki implementacji:
function Search-Hashed
([array]$arr, $item,
[scriptblock]$hashFunction=
$({param($x) return $x.GetHashCode()}))
{
$hashCode = $hashFunction.InvokeReturnAsIs($item)
return $arr[$hashCode]
}
Zamiast domyślnej funkcji haszującej można stworzyć swoją własną. Mój przykład dla znaków to:
$hashFunction = {param($x) [int][char]$x}
A wywołanie wygląda następująco:
$arr = 'A','V','b','b','C'
$hashtable = ConvertTo-Hashtable -arr $arr -hashFunction $hashFunction
Search-Hashed -arr $hashtable -item 'b' -hashFunction $hashFunction #2,3
Równie dobrze mogę zastosować własną funkcję haszującą string:
$hashFunctionString = {param($x) [int[]][char[]]$x-join ''}
$hashFunctionString.InvokeReturnAsIs("Hello Arek ") #72101108111326511410110732
Oczywiście nie mogę stworzyć tak wielkiej tablicy, ale może coś się wymyśli :)
