Algorytmy przeszukiwania w PowerShell

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 :)