Pseudorekurencja w SqlServer

Już dawno nie miałem styczności z SqlServerem więc muszę sobie przypomnieć. Dla treningu zrobiłem zapytanie rekurencyjne (pseudorekurencje). Już taki skrypt wykonałem dla Oracla i muszę powiedzieć, że kod wygląda identycznie :)
Dla problemu liczby fibonacciego tworzymy CTE:

WITH Fibonacci_cte  AS
(
     SELECT 0 as PrevFibN, 1 as FibN, 1 as Nr
     UNION ALL

     SELECT FibN, PrevFibN + FibN, Nr+1
     FROM Fibonacci_cte
     WHERE FibN < 1000000000
)
select * from Fibonacci_cte

Wynik zapytania wygląda tak:

Dla problemu wieży Hanoi mamy model:

with Hanoi_cte   AS 
(
select 
1 as n,
1 as counts

union all

select n +1 as n, POWER(2, n+1) -1 as counts
from Hanoi_cte 
where n < 30
)
select * from Hanoi_cte  

Wyniki zapytania są poniżej:

W tych przykładach dostaje często wyjątek związany z przekroczeniem dozwolonej wielkości dla typu kolumny (int).
Arithmetic overflow error for type int, value = 2147483648.000000.
Możemy zmienić typ kolumny w zapytaniu. Do sprawdzenia typu pomocne nam będzie funkcja SQL_VARIANT_PROPERTY. Przykład wykorzystania takiej funkcji jest poniżej:

select SQL_VARIANT_PROPERTY(POWER(CAST (2 as bigint), 2) , 'BaseType')​

Kiedy dodamy kastowanie do bigint to możemy już uzyskiwać większe liczby.

with Hanoi_cte   AS 
(
select 
CAST (1 AS bigint) as n,
CAST (1 AS bigint) as counts

union all

select 
n + 1   as n 
,POWER(CAST (2 as bigint), n+1) -1 as counts
from Hanoi_cte 
where counts < CAST(0x3FFFFFFFFFFFFFFF AS bigint)
)
select * from Hanoi_cte  

Ale i tak dla tego problemu możemy iterować do 63 rekordu - czy wiesz może dlaczego :)

Tak samo dodałem kastowanie do bigint dla problemu fibonacciego:

WITH Fibonacci_cte  AS
(
     SELECT 
CAST (0 as bigint) as PrevFibN, 
CAST(1 as bigint) as FibN, 
1 as Nr

     UNION ALL

     SELECT 
FibN, 
PrevFibN +FibN, 
Nr+1 
     FROM Fibonacci_cte
     WHERE Nr < 92 
)
select * from Fibonacci_cte

A wyniki tego zapytania są poniżej:

8 filmików o high frequency trading

Jestem po lekturach o HFT i jestem zdania, że bardzo trudno jest rozpocząć swoją przygodę z budowaniem infrastruktury do 'walki' na giełdzie. Co jednak nie zmienia mojego głodu na poszerzenie tej wiedzy i zdobycia doświadczenia w tym zakresie :)

Poniżej przedstawiam Ci najciekawsze filmiki o HFT.
























I filmik, który mówi o HFT od strony kuchni:

Pseudorekurencja w Oracle

Spróbowałem moich sił w oracle w wywołaniach rekurencyjnych. Skorzystałem z klauzury WITH. Tak na prawdę nie są to wywołanie rekurencyjne. Poniżej przedstawiam przykład wyświetlania wartości silni:

with 
Factorial (n,fact) as (
select 
0 as n,
1 as fact
from dual

union all

select 
n +1, (n+1)*fact
from Factorial
where n < 20
)
select * from Factorial 
;

A tutaj przykład wyliczenia liczby ruchów z postaci jawnej dla problemu wieży Hanoi:

with 
hanoi  (n,counts) as (
select 
1 as n,
1 as counts
from dual

union all

select 
n +1, POWER(2,n+1) -1
from hanoi 
where n < 20
)
select * from hanoi  
;

Wśród standardowych przykładów rekurencji zawsze musi wystąpić ciąg Fibonacciego. Zapytanie wyświetlające liczbę oraz wartość fibonacciego dla tej liczb, wygląda następująco:

with 
fibonacci (n,fib, fibadd) as (
select 
0 as n,
0 as fib,
1 as fibadd
from dual

union all

select 
n +1, fibadd, (fib + fibadd)
from fibonacci
where n < 100
)

select n,fib from fibonacci 
;

Jak pewnie zauważyłeś, to nie tworzysz modelu rekurencyjnego z warunkami stopu, ale model iteracyjny z warunkami początkowymi.

Problem ucztujących filozofów w PowerShell

Już wcześniej chciałem przedstawić moje rozwiązanie problemu pięciu ucztujących filozofów, ale jak zwykle ciężko znaleźć chwilkę czasu. Tak na prawdę moje rozwiązanie nie jest ostatecznym rozwiązaniem tego problemu, ale implementacją różnych możliwości uruchomienia symulacji ucztujących filozofów. Aby uruchomić symulację wystarczy uruchomić skrypt:

Run-DPP -showAll

Na ekranie uzyskamy liczby:
Status: 0 0 0 1 0
Meals: 5 2 4 3 3

Górny wiersz określa semafory o wolnych widelcach, a dolny wiersz określa ile razy dany filozof jadł. Z górnego wiersza można odczytać, że widelec przedostatni jest wolny.

Zacząłem rozwiązywać ogólny problem ucztujących n-filozofów. Poniżej przykład statusu dla 10 filozofów:

Symulacja działania filozofów jest na podstawie Jobów. Przy każdym wywołaniu skryptu następuję usunięcie job'ów:

    get-job | Stop-Job
    get-job | Remove-Job 

Na potrzeby rozwiązania problemu, użyto dodatkowego joba, który zarządza wszystkimi filozofami - kelner obsługujący filozofów. Implementacja kelnera jest w pliku Run-Waiter.ps1.

for( $i=0; $i -lt $philosopherNumber ; $i++) 
{
        Start-job -FilePath $scriptPath  -ArgumentList  $i,$scriptLocation -Name "Philo_$i"
} 

Każdy filozof prosi kelnera o widelec (request +1).
Kelner sprawdza listę próśb (request >0) i jak widelce są dostępne, podchodzi do filozofa i pozwala na wzięcie widelca (response +1).
Filozof sprawdza odpowiedz (response >0), bierze widelec i dziękuje za obsługę (request -1).
Kelner odchodzi od filozofa (response -1)
W taki sposób, filozof jest odpowiedzialny za zapis requestów, a kelner odpowiedzialnego za zapis responsów.




Dla kelnera wprowadziłem opcje randomizacji wyboru od którego filozofa za zacząć pytać czy czegoś nie potrzebuje. Częściowo rozwiązanie to rozwiązało problem nadawania priorytetu filozofom parzystym przed innymi filozofami, gdy mamy parzystą liczbę wszystkich filozofów.

W pliku DiningPhilosophersProblemHelper.ps1 są wszystkie funkcje współdzielone między kelnerem, a filozofami. PS nie ma pamięci współdzielonej pomiędzy wszystkie job'y czy procesy. Komunikację między job'ami jest zaimplementowana poprzez zmienne środowiskowe, które są dostępne z poziomu użytkownika:

[Environment]::GetEnvironmentVariable($name, [System.EnvironmentVariableTarget]::User)

Tablica określająca wolne zasoby widelców jest zapisana w zmiennej środowiskowej jako string:

function Set-ArrVariable([string]$name, [array]$arr)
{
    Set-ArrVariableStr $name ($arr  -join ';')
}

Zapis danych do zmiennej środowiskowej na poziomie użytkownika jest naszą sekcją krytyczną. Często można było uzyskać wielokrotne zwiększenie lub zmniejszenie wartości w tablicy:

Synchronizacja zapisu zmiennej środowiskowej jest za pomocą globalnych muteksów dostępnych przez wszystkie job'y. Przykład tworzenia globalnego muteksa jest poniżej:

$UsedForksMutex = new-object  System.Threading.Mutex ($false, 'Global\UsedFork')

Wprowadziłem opcje umierania filozofów, gdy za długo czekają na sztućce (lub na obsługę kelnera).

[bool]$mayStarve = $false

Czas potrzebny dla filozofa na myślenie oraz jedzenie jest ustawiony jako zmienna losowa. Domyślnie jest to wartość jednostkowa.

W planach mam jeszcze dodatnie
- ograniczenia do parzystej liczby filozofów, którzy mogą ubiegać się o sztućce
- pozwolenie filozofom wzięcia widelców, tylko jeżeli 2 z nich są dostępne ( jak na razie filozof bierze jeden widelec, a później próbuje wziąć drugi)
- filozofowie z parzystymi numerami najpierw wybierają widelce po prawej stronie, a filozofowie z numerami nieparzystymi wybierają najpierw widelce po lewej stronie
- rozwiązanie probabilistyczne (losowe wybieranie strony pierwszego widelca, a później znów losowanie prawdopodobieństwa wzięcia drugiego widelca, w przypadku nie wzięcia tego drugiego widelca opuszcza się widelec pierwszy)
- ustalenie priorytetów wyboru widelców (przy podnoszeniu najpierw wybiera się sztućce o numerach niższych, a przy oddawaniu najpierw oddaje się sztućce o numerach wyższych)
- rozwiązanie czystych i brudnych widelców
- ustawienie pierwszeństwa w jedzeniu dla filozofa o najmniejszej ilości skonsumowanych posiłków

Co prawda implementacja problemu 5 filozofów nie jest jeszcze gotowa, ale mogę wysunąć wnioski, że dużo przyjemniej rozwiązuje się ten problem w innych językach programowania - przynajmniej nie trzeba pracować na zmiennych globalnych czy na job'ach. Dużo przyjemniejsza była by implementacją tego problemu w C# niż w PS. PS jak na razie nie ma prostych sposobów synchronizacji job'ów. Taka prosta sprawa jak wyświetlanie komunikatów też nie była prosta. Write-Host nie wyświetla komunikatów w konsoli dopóki nie pobierze się job'a. Można było zawiesić komputer za pomocą symulację dla 20 filozofów i przetrzymując wszystkie komunikaty w pamięci. Nawet jak wyjdziemy z debuggera to job'y i tak będą wykonywać się.

Cały kod źródłowy można pobrać z github.

Algorytmy geometryczne w PowerShell

Wystartowałem z kolejnym projektem w PS, tym razem z algorytmami geometrycznymi. Chciałbym zrobić framework oraz zaimplementować parę alg. geometrycznich. Dopiero co zacząłem implementację i dużo jeszcze jest przede mną.
Na samym początku można stworzyć punkt dla int jak i dla float:

new-p 1 2
new-pf 1.4 2.1

Aby funkcje zadziałały to należy uruchomić funkcje Init-GeoAlg znajdująca się w pliku PointsCommon.ps1.
Możesz wygenerować 100 punktów od punktu (0,0) do (100,100) wywołując:

Generate-PF -iterateNum 100

Lub za pomocą wyrażenia lambda (oficialnie nie ma w PS :) ) można podać scriptblock zwracający wartość równej sumy poprzedniej wartości i iteratora:

Generate-PF -iterateNum 100 -funcX {param($prevVal, $i) $i + $prevVal}

Jak na razie to nie wiele alg. zaimplementowałem (spr. czy punkt znajduje się na odcinku, sortowanie punktów po koncie nachylenia względem osi OX, znajdywanie parę punktów o najmnijszej odległości od siebie itd.).

Z pomocą pestera, zacząłęm pisać testy w stylu BDD, ale jak na razie nie wiem jak można weryfikować mocka na alias w pipelinie w wywołaniu rekurencyjnym. Tej funkcjonalności brakuje mi w pester.


Projekt można znaleźć na moim github. Pomysł na projekt o alg. geometrycznych powstał po prezentacji o tym temacie:

Rozwiązanie wieży Hanoi za pomocą listy cyklicznej

Już parę razy pisałem o problemie wieży Hanoi oraz rozwiązaniu jej.

Tym razem chciałbym przedstawić Ci rozwiązanie iteracyjne wieży Hanoi za pomocą listy cyklicznej w PowerShellu.
Algorytm jest bardzo prosty:
1. Połącz słupki w sposób cykliczny
2. Jeżeli liczba wszystkich krążków jest parzysta to ruch słupków jest zgodny z ruchem zegara. W przeciwnym przypadku jest to ruch przeciwny do ruchu zegara.
3. Znajdź najmniejszy krążek i przenieś go na następny słupek
4. Jeżeli wszystkie krążki jest są na słupku docelowym to zakończ program
5. Dla każdego krążka, który nie jest najmniejszym krążkiem spróbuj przenieś krążek na następne miejsce.
6. Przej do kroku nr 3


Do implementacji tego algorytmu będzie nam potrzebny typ stosu. Skorzystamy z akceleratora. =

$accelerators = [psobject].Assembly.gettype("System.Management.Automation.TypeAccelerators")
$stackType = [type]'System.Collections.Generic.Stack`1'
$accelerators::Add('stack', $stackType)

Stworzymy węzeł, który w problemie wieży Hanoi będzie jako słup:

function Create-Node
{
    param($value, $previous, $next, $key=$([guid]::NewGuid()))

    return new-object PSObject | 
               Add-Member -MemberType NoteProperty -Name "Key" -Value  $key -PassThru |                
               Add-Member -MemberType NoteProperty -Name "Value" -Value $value  -PassThru |
               Add-Member -MemberType NoteProperty  -Name "Next" -Value $next  -PassThru |
               Add-Member -MemberType NoteProperty  -Name "Previous" -Value $previous -PassThru
}

I teraz będziemy mogli stworzyć listę cykliczną z tablicy:

function Create-CircularList
{
    param([array]$arr, [switch]$nonCircular, [array]$keys)

    $CircularList =@()
    for($i=0; $i -lt $arr.Length; $i++)
    {
        $node = Create-Node -value $arr[$i] -key $keys[$i] 
        if($i -gt 0)
        {
            $prevNode =   $CircularList[$i-1]
            $node.Previous = $prevNode
            $prevNode.Next = $node
        }
        $CircularList += $node
    }

    if(!$nonCircular)
    {
        $firstNode = $CircularList[0]
        $lastNode = $CircularList[$arr.Lengt-1]

        $firstNode.Previous = $lastNode 
        $lastNode.Next = $firstNode
    }
    return $CircularList
}

Jeszcze będziemy potrzebować funkcji która by zwracała index listy, która posiada najmniejszy krążek:

function Find-ItemInValue
{
    param([array]$arr, [int]$item)

    for($i=0; $i -lt $arr.Length; $i++)
    {
        $value = $arr[$i].Value
        if($value -is [int] -and [int]$value -eq [int]$item)
        {
            return $i
        }
        elseif($value)
        {
            $index = [array]::IndexOf($value,$item)
            if($index -ge 0)
            {
                return $i
            }
        }
    }
    return -1
}

I teraz wystarczy zaimplementować algorytm rozwiązujący wieżę Hanoi:

function Solve-Hanoi
{
[CmdletBinding()]
param(
[Alias("circularList")]$list,
[switch]$optDir
)

$startPeg = $list[0]
$maxItems =  $list.Value.Count
$listMeasure = $list.Value | measure -Minimum -Maximum
$minSpotValue = $listMeasure.Minimum
$maxSpotValue = $listMeasure.Maximum
$endPeg = $list[$list.Length-1]
 
$moveDir = "Next"
if($optDir)
{
    [bool]$even = $maxItems % 2 -eq 0
    if(!$even)
    {
        $moveDir = "Previous"
    }
}

$step=0
 while($endPeg.Value.Count -lt $maxItems)
 {
    for($searchSpot = $minSpotValue; $searchSpot -le $maxSpotValue; $searchSpot++)
    {
        $indexOfMin = Find-ItemInValue -arr $list -item $searchSpot
        if($indexOfMin  -eq -1)
        {
            continue
        }
        $currentPeg = $list[$indexOfMin]
 
        $nextPeg = $currentPeg.$moveDir
        $currentSpot = $currentPeg.Value.Peek()
        if($currentSpot -eq $searchSpot)
        {
            while($nextPeg -ne $currentPeg)
            {
                if($nextPeg.Value.Count -eq 0 -OR $nextPeg.Value.Peek() -gt $currentSpot)
                {
                    $nextPeg.Value.Push($currentPeg.Value.Pop())
                        
                    $step++
                    Write-Verbose "Step: $step"
                    Write-Verbose " $($list | select Key,Value |out-string)"
                    break
                }
                $nextPeg = $nextPeg.$moveDir
            }
        }
    }
}
return $list
}

Wywołanie tego algorytmu jest następujące:

[stack[int]]$pegA = 5,4,3,2,1 #last in, first out
[stack[int]]$pegB = @()
[stack[int]]$pegC = @()

$CircularList= Create-CircularList -arr $pegA,$pegB,$pegC -keys 'A','B','C'
Solve-Hanoi -circularList $CircularList -Verbose -optDir

Możemy wywołać wieżę Hanoi z dowolnego układu:

$arr = 1..4
[array]::Reverse($arr)
[stack[int]]$pegA =$arr
[stack[int]]$pegB = @(6)
[stack[int]]$pegC = @(5)

$CircularList= Create-CircularList -arr $pegA,$pegB,$pegC -keys 'A','B','C'
Solve-Hanoi -circularList $CircularList -Verbose -optDir

No, prawię z dowolnego. Dla takiego układu początkowego musiałem wyłączyć parametr optymalizujący kierunek przesunięcia krążków.

$arr = 1..2
[array]::Reverse($arr)
[stack[int]]$pegA =$arr
[stack[int]]$pegB = 7,6
[stack[int]]$pegC = @(5)

$CircularList= Create-CircularList -arr $pegA,$pegB,$pegC -keys 'A','B','C'
Solve-Hanoi -circularList $CircularList -Verbose 

Lista cykliczna w PS

Postanowiłem zrobić listę cykliczną w PowerShellu.
Na samym początku zrobiłem węzeł reprezentujący wartość oraz wskazuje na następny i poprzedni węzeł:

function Create-Node
{
    param($value, $previous, $next)

    return new-object PSObject | 
               Add-Member -MemberType NoteProperty -Name "Value" -Value $value  -PassThru |
               Add-Member -MemberType NoteProperty  -Name "Next" -Value $next  -PassThru |
               Add-Member -MemberType NoteProperty  -Name "Previous" -Value $previous -PassThru
}

Jeszcze do tego jest potrzebna funkcja do wypełnienia tych węzłów:

function Create-CircularList
{
    param([array]$arr, [switch]$nonCircular)

    $CircularList =@()

    for($i=0; $i -lt $arr.Length; $i++)
    {
        $node = Create-Node -value $arr[$i] 
        if($i -gt 0)
        {
            $prevNode =   $CircularList[$i-1]
            $node.Previous = $prevNode
            $prevNode.Next = $node
        }
        $CircularList += $node
    }

    if(!$nonCircular)
    {
        $firstNode = $CircularList[0]
        $lastNode = $CircularList[$arr.Lengt-1]

        $firstNode.Previous = $lastNode 
        $lastNode.Next = $firstNode
    }
    return $CircularList
}

Wywołanie jest bardzo proste:

$list= Create-CircularList -arr "A","B","C"
$item = $list[0]
$item.Next.Next.Next

Zmienna $item reprezentuje pierwszy element, a jak wywołały 3 razy następny element to również uzyskamy pierwszy element z listy.
Jeżeli będziesz chciał stworzyć połączenia, bez cyklu to wystarczy wywołać funkcję z parametrem nonCircular:

$list= Create-CircularList -arr "A","B","C" -nonCircular
$item = $list[0]
$item.Next.Next.Next

Problem Józefa Flawiusza w PowerShell cz.2

Już wcześniej pisałem o problemie Józefa Flawiusz. W tamtych czasach nie miałem rozwiązania przedstawiającego wszystkie iteracje tylko rozwiązanie zwracało ostatni element. Napisałem od nowa algorytm do wyświetlenia wszystkich elementów.
Poniżej jest funkcja iteracyjna do wyświetlenia kolejności elementów:

function Iterate-JosephusFlavius(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]        
        [int]$soldiers = 41
      )
{
    [bool[]]$bools = @($false)*$soldiers
    $indexOfKilledSoldiers=@()
    $soldiersToKill = $soldiers
    $rest = 0
    $setps=0
    while($soldiersToKill  -gt 0)
    {
        for($i=$rest; $i -lt $bools.Length;$i++)
        {
            if($bools[$i] -eq $false)
            {
                $setps++
                if($setps -eq $killEvery)
                {
                    $bools[$i] = $true
                    $indexOfKilledSoldiers += $i
                    $soldiersToKill--
                    $setps=0
                }
            }
        }
        $rest = $i -$bools.Length
    }
    return $indexOfKilledSoldiers
}

A tutaj jest funkcja rekurencyjna. Z tą funkcją miałem więcej problemów. Niestety argumenty funkcji są inne dla iteracji jak i dla rekurencji. Jak będę miał chwilkę czasu to poprawię tą różnicę.

function Recursive-JosephusFlavius(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [int[]]$soldiers,
        [int[]]$killedSoldiers=@(),
        [int]$prevRest = 0
      )
{
    if($soldiers.Length -eq 0 )
    {
        return $killedSoldiers
    }
    $aliveSoldiers=@()
    
    if($soldiers.Length - $killEvery -lt 0)
    {
        $soldierToKill = (($killEvery + $prevRest) -1) % $soldiers.Length 
        for($i=0; $i -lt $soldiers.Length; $i++)
        {
            if($soldierToKill -eq $i)
            {
                $killedSoldiers += $soldiers[$i]
            }else
            {
                $aliveSoldiers += $soldiers[$i] 
            }
        }  
    }
    else
    {
        for($i=0; $i -lt $soldiers.Length; $i++)
        {
            if(($i+1)  % $killEvery -ne 0)
            {
                $aliveSoldiers +=   $soldiers[($i-$prevRest)]  
            }else
            {
                $killedSoldiers +=  $soldiers[($i-$prevRest)]
            }
        }
        $soldierToKill = $soldiers.Length % $killEvery
    }
   return  Recursive-JosephusFlavius -soldiers $aliveSoldiers -killEvery $killEvery -killedSoldiers $killedSoldiers  -prevRest $soldierToKill 
}

Wywołanie tych funkcji oraz sprawdzenie działania wygląda następująco:

$soldiers = 0..40 #41 soldiers
$killEvery = 3

$res1= Recursive-JosephusFlavius -soldiers $soldiers -killEvery $killEvery
$res2 = Iterate-JosephusFlavius  -soldiers ($soldiers.Length) -killEvery $killEvery

for($i=0; $i -lt [math]::Max($res1.Length,$res2.Length); $i++)
{
    if($res1[$i] -ne  $res2[$i])
    {
        throw "not the same"
    }
    else
    {
        Write-Host $res1[$i]
    }
}

MergeSort i Assert w PowerShell

Chciałem napisać prostą asercje i poćwiczyć sortowanie, więc napisałem script, z którym podzielę się z tobą :)
Na samym początku będziemy potrzebować funkcje, która będzie łączyła lewą i prawą stronę tablicy. Te części są posortowane.

function Merge
{
    param([array]$A,
    [array]$temp=@(),
    [int]$low=0,
    [int]$high=$($A.Length-1),

    [int]$middle = 
$([math]::Floor($low + ($high - $low)/2))
    )
    
    $i = $low
    $j = $middle +1
    
    Assert-Command {IsSorted ($A[$i..$middle]) }
    Assert-Command {IsSorted ($A[$j..$high]) }

    $temp = $A
    $swapA = @(0)* $A.Length
    for($k = $low; $k -le $high; $k++)
    {
        if( $i -gt $middle)
        {
            $swapA[$k] = $temp[$j]
            $j++        
        }
        elseif ($j -gt $high)
        {
            $swapA[$k] = $temp[$i]
            $i++
        }
        elseif( $temp[$j] -gt $temp[$i] )
        {
            $swapA[$k] = $temp[$i]
            $i++
        }
        else
        {
            $swapA[$k] = $temp[$j]
            $j++
        }
    }
    $sortedA =$swapA[$low..$high]

    Assert-Command {IsSorted $sortedA}
    return $sortedA
}

Napiszemy prostą funkcję do sprawdzenia czy elementy są posortowane:

function IsSorted([array]$arr)
{

    for($i=0; $i -lt $arr.Length-1; $i++)
    {
        if($arr[$i] -gt $arr[$i+1])
        {
            return $false
        }
    }
    return $true
}

Do funkcji scalania potrzebna jest funkcja asercji:

function Assert-Command
{
    param(
    [Parameter(Position=0,Mandatory=$true)]
    [ScriptBlock]$condition,

    [Parameter(Position=1)]
    [string]$message
    )
    $invoke = $MyInvocation

    try{
        $ErrorActionPreference = "STOP"
        $result = &$condition
    }catch{
        $result=$false
        $exceptionType = $_.Exception.GetType().FullName
    }


    if(-not($result))
    {
        $errMess = "Assert failed in line: $($invoke.Line) `n"
        $errMess += "Message: $message `n"
        $errMess += "Exception type: $exceptionType `n"
        $errMess += "Used parameters: $($invoke.BoundParameters.condition) `n"
        throw $errMess
    }
}

I na końcu potrzebujemy funkcji sortując:

function MergeSort-Object
{
    param([array]$A,
    [array]$temp=@(),
    [int]$low=0,
    [int]$high=$($A.Length-1),

    [int]$middle = $([math]::Floor($low + ($high - $low)/2))
    )
    
    if($low -ge $high)
    {
        return $A[$low]
    }

    [array]$sortedPart1 = MergeSort-Object -A $A -low $low -high $middle
    $A = Fill-Array -table $A -with $sortedPart1 -offSet $low

    [array]$sortedPart2  = MergeSort-Object -A $A -low ($middle+1) -high $high
    $A = Fill-Array -table $A -with $sortedPart2 -offSet ($middle+1)

    [array]$sorted = Merge -A $A -low $low -middle $middle -high $high
    return $sorted 
}

Niestety będziemy musieli użyć pomocniczej funkcji do wypełnienia tablicy już posortowanej części. Są to uroki przekazywania parametrów funkcji przez wartość, a nie przez referencje.

function Fill-Array
{
    param([array]$table,
    [int]$offSet=0,
    [array]$with
    )

    [array]$newTable = $table
    
    for($i =0; $i -lt $with.Length; $i++)
    {
        
        $newTable[$offSet + $i] = $with[$i]
    }
    return $newTable
}

I przykładowe sortowanie tablicy wygląda następująco:

 MergeSort-Object -A 1,3,7,99,5,3,32,5,11,91 

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