Pokazywanie postów oznaczonych etykietą math. Pokaż wszystkie posty
Pokazywanie postów oznaczonych etykietą math. Pokaż wszystkie posty

poniedziałek, 5 maja 2014

Ceiling i Floor w PS

Postanowiłem poćwiczyć implementację sufitu i podłogi w PS. Jak jesteś zainteresowany jak działa Ceiling i Floor to sprawdź klasę Math.
Implementacja sufitu jest następująca:
function Get-Ceiling($x)
{
    [int]$ceil = [int]$x
    if($ceil  -ne $x)
    {
        $diff = $ceil - $x
        if($diff -ge 0)
        {
            return $ceil
        }else{
            return $ceil+1
        }
    }
    return $ceil
}
A podłogi jest taka:
function Get-Floor($x)
{
    [int]$floor = [int]$x
    if($floor  -ne $x)
    {
        $diff = $floor - $x
        if($diff -ge 0)
        {
            return $floor-1
        }else{
            return $floor
        }
    }
    return $floor
}
Implementacja algorytmu podłogi i i sufitu jest zupełnie inna niż dla c podobnych języków programowania (C,C++,java, c#) jak i dla VB

Postanowiłem zaimplementować inne funkcje, za pomocą już zdefiniowanych funkcji:

function Get-Sign([int]$x)
{
    if($x -gt 0)
    {
        return 1
    }
    elseif($x -lt 0)
    {
        return -1
    }
    return $x
}

function Get-Abs([decimal]$x)
{
    return  $x * (Get-Sign($x))
}

function Get-Round($x)
{
    if([int]$x -ge 0)
    {
        return Get-Floor($x + 0.5D)   # D for Decimal
    }
    return Get-Ceiling($x - 0.5D)
}

function Get-Sawtooth($x)
{
    return $x - (Get-Floor($x))
}
Funkcja Sawtooth zwraca ułamek ( może powinna się nazywać funkcją zębatej piły)

function Get-Truncate($x)
{
    return (Get-Sign($x)) * (Get-Floor(Get-Abs($x)))
}
Dla funkcji Get-Truncate złe będzie zwracana liczba jeżeli funkcja zwracająca sygnału będzie bez nawiasów:
Get-Sign($x) * (Get-Floor(Get-Abs($x)))


Dodatkowo mamy implementację tych części funkcji dla licz używanych jako wartość pieniądza (z dokładności liczby do 2 miejsc po przecinku):
function Get-RoundMoney($x)
{
    return (Get-Round($x*100))/100    
}

function Get-SawtoothMoney($x)
{
    return [decimal]($x*100) - (Get-Floor($x*100))
}

function Get-TruncateMoney($x)
{
    return (Get-Sign($x)) * ((Get-Floor(Get-Abs([decimal]$x*100)))/100)
}

Dla funkcji Get-TruncateMoney też będziemy mieli problem z ze zmienną $x.
Bez [decimal] nie zadziała Get-TruncateMoney.
Przy wywołaniu Get-TruncateMoney -19.0190 uzyskamy błąd z tekstem:-19.0190-19.0190-19.0190-19.0190-19.0190-19.0190... itd.

Tak się zastanawiam czy nie lepiej było by zaimplementować te funkcje w .NET i skorzystać z wygenerowanej biblioteki.

piątek, 14 marca 2014

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]
    }
}

piątek, 28 lutego 2014

Rozwiązanie problemu Józefa Flawiusza w PowerShell

Józef Flawiusz walczył w powstaniu żydowskim przeciwko rzymianom. Pewnego razu, żołnierze żydowscy zostali otoczeni przez wojsko rzymskie i 40 powstańców wolało popełnić samobójstwo niż oddać się w niewolę. Żeby nie było łatwo w przewidzeniu kto będzie ostatni w tym czynie, postanowiono, że powstańcy staną w okręgu i co 3 osoba będzie dokonywać samobójstwa. Pomysł samobójstwa nie podobał się Józefowi i chciał stanąć w takim miejscu, aby jako ostatni mógł oddać się do niewoli i przeżyć. Wyznaczenie tego ostatniego miejsca nazywa się problemem Józefa Flawiusza.

Symulację graficzną algorytmu można zobaczyć na tej stronie.

Dla uproszczenia numeracja miejsc jest od 0. Poniżej jest rozwiązanie iteracyjne:
function Solve-JosephusProblem
{
    param(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]        
        [int]$soldiers = 40
      )
      $i=1
      $rest=0
      while($i -le $soldiers)
      {
        $rest = ($rest + $killEvery ) % $i 
        $i++
      }
      return $rest
}
Sprawdzenie miejsca dla 10 żołnierzy:
Solve-JosephusProblem -soldiers 10 -killEvery 3
#3


Gdyby samobójca był wybierany co 1 osobę to ostatnia osoba dokona samobójstwa.

Solve-JosephusProblem -soldiers 41 -killEvery 1



Poniżej jest rozwiązanie rekurencyjne:
function Solve-JosephusProblemRec
{
    param(
        [ValidateRange(1,1000)]
        [int]$killEvery = 3,
        [ValidateRange(1,1000)]
        [int]$soldiers = 40
      )

    if($soldiers -eq 1)
    { 
        return 0 
    }
    else
    {
        [int]$recSolve = Solve-JosephusProblemRec -killEvery $killEvery -soldiers ($soldiers-1)
        return (($recSolve +$killEvery  ) % $soldiers )  
    }
}

Nie ukrywam, że dużo pomogła mi strona na wiki opisująca ogólny problem.

Sprawdzamy na którym miejscu powinien Józef Flawiusz się ustawić:
$soldiers =41
$killEvery =3
Solve-JosephusProblem -soldiers $soldiers -killEvery $killEvery  #30
Solve-JosephusProblemRec -soldiers $soldiers -killEvery $killEvery #30

czwartek, 27 lutego 2014

Wartość oczekiwana w PS

Ostatnio bawiłem się statystyką i postanowiłem napisać super prostą funkcję do zliczania wartości oczekiwanej w PowerShell.


function Get-ExpectedValue
{
    param(
        [Parameter(Mandatory=$true)]
        [ValidateNotNullOrEmpty()]
        [array]$values=@(),
        
        [Parameter(Mandatory=$false)]
        [ValidateNotNullOrEmpty()]
        [array]$probability=$( @(1/$values.Length) * $values.Length)
    )
        [int]$min =[math]::Min($values.Length, $probability.Length)
        $sum=0
        $probabilitySum=0
        for($i=0; $i -lt $min; $i++)
        {
            $product = [double]$values[$i] * $probability[$i]
            $sum+=  $product
            $probabilitySum+=$probability[$i]
        }

        return ($sum / $probabilitySum)
}
Wprowadźmy wartość oczekiwaną w praktykę. Wartość oczekiwana sprawdza się w grach.

Kostka sześcienna ma wartość oczekiwaną 3.5
Get-ExpectedValue  -values 1,2,3,4,5,6  #3,5

Gdyby prawdopodobieństwo wystąpienia ilości oczek nie było takie same to wartość oczekiwana była by inna:
Get-ExpectedValue  -values 1,2,3,4,5,6 -probability ((1/6), (1/5),(1/3),(1/3))  #2,80645161290323


Dajmy na to, że gramy w kości. Jeżeli uzyskasz liczbę oczek mniejszą lub równą 2 to dasz mi kwadrat różnicy 6 i ilości oczek. Natomiast jak uzyskasz liczbę oczek 3,4,5,6 to ja tobie daję dwu-krotność liczby oczek.
Get-ExpectedValue  -values ( (-1* (6-1) *(6-1) ), (-1*(6-2)*(6-2)),  6,8,10,12 ) #-0,833333333333333



Bardzo lubię grać w Osadników z catanu i w grze występują dwie kostki. Wiesz może dlaczego złodziejem ruszasz się, gdy masz sumę równa 7?? Rozwiązanie jest przedstawione poniżej:
$dice  = 1,2,3,4,5,6
$dice2=  $arr | %{ 
    $outter = $_
    $arr | %{
        $inner = $_
        return $outter + $inner
    }
} | sort
Get-ExpectedValue $dice2 #7

$dice2 | group 
Count Name                      Group                                                                                                                                    
----- ----                      -----                                                                                                                                    
    1 2                         {2}                                                                                                                                      
    2 3                         {3, 3}                                                                                                                                   
    3 4                         {4, 4, 4}                                                                                                                                
    4 5                         {5, 5, 5, 5}                                                                                                                             
    5 6                         {6, 6, 6, 6...}                                                                                                                          
    6 7                         {7, 7, 7, 7...}                                                                                                                          
    5 8                         {8, 8, 8, 8...}                                                                                                                          
    4 9                         {9, 9, 9, 9}                                                                                                                             
    3 10                        {10, 10, 10}                                                                                                                             
    2 11                        {11, 11}                                                                                                                                 
    1 12                        {12}  


Jest to wartość oczekiwana, a jednocześnie najczęściej spotykana suma.

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

wtorek, 25 lutego 2014

Symbol Newtona w PowerShell

Chciałem poćwiczyć z symbolem Newtona, więc postanowiłem napisać skrypt w PS, aby porównać te sposoby uzyskiwania współczynnika dwumianowego.
Oczywiście do symbolu Newtona będziemy potrzebowali funkcję zwracającą wartość silni.
function Get-Factorial([int]$n)
{
    if($n -lt 1) {
        return 1
    }
    $facttorialRec = Get-Factorial($n -1)
    return ($n * $facttorialRec )
}
Jak na razie funkcja oblicza silnie rekurencyjnie (ale mam w planach dodać jeszcze silnie obliczoną w sposób iteracyjnie).

Mamy też funkcję obliczającą symbol Newtona za pomocą rekurencji:
function Get-BinomialCoefficientRec([int]$n, [int]$k)
{
    if($k -lt 0 -OR $k -gt $n)
        {return 0}

    if($k -eq 0 -OR $k -eq $n -OR $n -lt 1)
        {return 1} 

    $diff = $n - $k
    if($k -gt $diff)
    {
        $k = $diff
    }
    
    $binomial1 = Get-BinomialCoefficientRec -n ($n-1) -k $k
    $binomial2 = Get-BinomialCoefficientRec -n ($n-1) -k ($k-1)
    return $binomial1 + $binomial2
}


Oraz funkcję korzystającą z tożsamości algebraicznej:
function Get-BinomialCoefficientIteratively([int]$n, [int]$k)
{
    if ($k -lt 0 -or  $k -gt $n)
    {return 0}
 
    if($k -eq  0 -or  $k -eq  $n)
    { return 1}

    $diff = $n - $k
    if ($k -gt $diff)
    {  $k = $diff }
    
    $prod = 1
    for($i=1; $i -le $k; $i++)
    {
        $prod = $prod * (  ($n - $i + 1) / $i  )    
    }

    return $prod
}

Możemy wyliczyć symbol Newtona na ze wzoru Sterlinga. Wzór ten stosuje się dla bardzo dużych liczb, gdyż błędy względne są małe.
function Get-StirlingApproximation([int]$n)
{

    $numDivE = $n / [math]::E
    $const = [math]::Sqrt(2.0 * $n * [math]::PI)
    $result = $const * ([math]::Pow(($numDivE) ,$n))   
    if($result -eq 0)
        {return 1}
    return $result
}


Główna funkcja, która agreguje funkcje zliczające współczynnik dwumianowy jest przedstawiona poniżej:

function Get-BinomialCoefficient
{
    param(
    [ValidateSet('factorial','recursive', 'multiplicative', 'stirling'  )]
    [string]$arg='factorial',

    [Parameter(Mandatory=$true, Position=0)]  
    [int]$n,

    [Parameter(Mandatory=$true, Position=1)]  
    [int]$k
    )

    if($arg -eq 'factorial')
    {
         $upperFractal = Get-Factorial($n) 
         $lowerFractalK = Get-Factorial ($k) 
         $lowerFractalNK=  Get-Factorial($n- $k)
         return $upperFractal  / ($lowerFractalK * $lowerFractalNK)
    }
    elseif($arg -eq 'stirling')
    {
        $aproxN = Get-StirlingApproximation($n)
        $aproxK = Get-StirlingApproximation ($k)
        $aproxNK = Get-StirlingApproximation($n- $k)
        return  $aproxN/ ( $aproxK  *$aproxNK )
    }
    elseif($arg -eq 'recursive')
    {
        return Get-BinomialCoefficientRec -n $n -k $k
    }
    elseif($arg -eq 'multiplicative')
    {
        return Get-BinomialCoefficientIteratively -n $n -k $k
    }

    throw 'Wrong argument in parameter $arg'
}


A funkcja do pomiaru wygląda następująco:
function Measure-BinomialCoefficient([int]$to)
{
    $Nenum = 1..$to
    $Nenum | %{
        $n = $_
        $Kenum = 1..$n 
        $Kenum | %{
           $k = $_
           $factorialMeasure =         
(Invoke-Command  {  Get-BinomialCoefficient -arg factorial -n $n -k $k       })

           $multiplicativeMeasure =    
(Invoke-Command  {  Get-BinomialCoefficient -arg multiplicative -n $n -k $k  })

           $recursiveMeasure =         
(Invoke-Command  {  Get-BinomialCoefficient -arg recursive -n $n -k $k       })

           $stirlingMeasure =          
(Invoke-Command  {  Get-BinomialCoefficient -arg stirling -n $n -k $k        })


            return new-object PSObject | 
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  n  -Value $n |
               
Add-Member -PassThru -MemberType NoteProperty 
-Name  k  -Value $k |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  factorial  -Value $factorialMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  multiplicative  -Value $multiplicativeMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  recursive  -Value $recursiveMeasure |
                
Add-Member -PassThru -MemberType NoteProperty 
-Name  stirling  -Value $stirlingMeasure
        }
    }
}

Wyniki tych wywołań są przedstawione poniżej. Co prawda wzór Stirling nie daje dokładnej wartości, ale jestem pod wrażeniem przybliżenia wartości symbolu Newtona.



Aby uzyskać czasy działania algorytmów to wystarczy zamienić słowa Invoke na Measure oraz dodać TotalMilliseconds - pomiary są w milisekundach.
           $factorialMeasure =         
(Measure-Command  {  Get-BinomialCoefficient -arg factorial -n $n -k $k       }).TotalMilliseconds

           $multiplicativeMeasure =    
(Measure-Command  {  Get-BinomialCoefficient -arg multiplicative -n $n -k $k  }).TotalMilliseconds

           $recursiveMeasure =         
(Measure-Command  {  Get-BinomialCoefficient -arg recursive -n $n -k $k       }).TotalMilliseconds

           $stirlingMeasure =          
(Measure-Command  {  Get-BinomialCoefficient -arg stirling -n $n -k $k        }).TotalMilliseconds

A poniżej wykres przedstawiający czasy działania algorytmów (dla różnych n i k):



Gdybyśmy ograniczyli ilość danych poprzez wprowadzenie parametru k jako połowa parametru n oraz przedstawili dane na wykresie w skali logarytmicznej to mamy taki wykres:

Co dla mnie jest dziwne, to czasy obliczeń symbolu Newtona za pomocą wzoru Sterlinga oraz dla iteracyjnego sposób wyliczenia się zmniejszają :)
Takie rzeczy to tylko w PS.


czwartek, 13 lutego 2014

Wizualizacja algorytmu Wieży Hanoi

Ilość wykonywanych ruchów w algorytmie Wieży Hanoi wzrasta bardzo szybko wraz ze wzrostem ilości krążków. Stworzyłem parę obrazków, które przedstawiają kroki jakie należy zrobić, aby rozwiązać wieże. Wierzchołki grafu są słupkami wieży, a numer na krawędzi grafu symbolizuje kolejność przesuwania krążka.


Przeniesienie dla 1 krążka:

Przeniesienia dla 2 krążków:

Przeniesienia dla 3 krążków:

Przeniesienia dla 4 krążków:

Przeniesienia dla 5 krążków:

Przeniesienia dla 6 krążków:

Przeniesienia dla 7 krążków:

Więcej o Wieży Hanoi można poczytać tutaj.

piątek, 15 marca 2013

PowerShell w matematyce

PowerShell jest fantastycznym narzędziem do poprawienia swojej produktywności. Może przydać się w prostych zadaniach matematycznych.


Między innymi możesz w szybki sposób sprawdzić co zwraca dane wyrażenie matematyczne:
PS>19 * 17 / 13 + 11 - 7
28.8461538461538
Ale należy uważać, gdyż PS nie kieruje się matematyczną kolejnością wykonywana działań, dlatego poniżysz wynik jest inny niż spodziewany:
PS>2 + 2 * 2
6
PowerShell sprawdza jaka operacja jest na pierwszym miejscu oraz jaki jest typ pierwszej zmiennej. Wywołując wyrażenie 1+"2" mamy inny wynik niż wywołując "1"+2.
PS>1+ "2"
3

PS>"1" + 2 
"12"
Śmieszną możliwością PS jest sposób mnożenia stringa:)
PS>"z" * 5 + "...."
zzzzz....
Jak będziesz potrzebował przeliterować od 1 do 10 to wystarczy zapisać 1..10 (poniżej przykład)
PS>write-host (1..10) -NoNewLine -separator " _ "
1 _ 2 _ 3 _ 4 _ 5 _ 6 _ 7 _ 8 _ 9 _ 10
Taki zapis jest znany z innych języków. Pierwszy raz zobaczyłem taki sposób inicjalizacji w Matlabie. Dodawanie zakresów jest też bardzo intuicyjne. Aby przeiterować od -5 do 5 bez zera to wystarczy zapisać:
PS>write-host ( -5..-1 + 1..5 ) -NoNewLine -separator " _ "
-5 _ -4 _ -3 _ -2 _ -1 _ 1 _ 2 _ 3 _ 4 _ 5
Do tego masz możliwości użycia klasy [math], która posiada najważniejsze funkcje matematyczne:
PS> [math] | Get-Member -Static 
I tak możemy w szybki sposób obliczyć procent składany
PS> $initialInvestment * [math]::pow(1+$interestRate, $times) 
PS> 1000 * [math]::pow(1+0.05, 2)
1102,5
Natomiast, aby obliczyć na jaki procent w skali roku zwróciła się inwestycja wystarczy napisać:
PS>[math]::pow($value/$initialInvestment,1/$times) - 1
PS>[math]::pow(1102/1000,1/2) - 1
0,0497618777608568
Co jest bardzo ciekawe w PS to możliwość operacji na jednostkach pamięci.
PS> 1MB
1048576

PS> 9MB
9437184

PS> 1TB
1099511627776
Możesz przedstawić wielkość jednostki pamięci w innej jednostce, na przykład w postaci megabajtów:
PS>1TB / 1MB
1048576
Czasami taki zapis pomaga przy obliczaniu zajmowanej przestrzeni na dysku.
PS>"{0:n3}"-f ((gwmi win32_logicaldisk -Filter "DeviceID='C:'").freespace/1GB)
Uważam, że PowerShell jest narzędziem matematycznym do bardzo prostych zadań. PS nigdy nie będzie (nigdy nie mów NIGDY) narzędziem dla matematyków, ale w pracy administratora fantastycznie się sprawdza jako proste narzędzie matematyczne.

poniedziałek, 25 czerwca 2012

Double są szalone

Typ podwójnej precyzji zawarty w .NET jest bardzo dziwny. Zapisując liczbę mamy tak naprawdę liczbą zaburzoną pewnym błędem reprezentacji.
Poniższe przykłady przedstawiają "dokładność" metody zaokrąglającej oraz prostą operację dodawania.
double res0 = Math.Round(0.500000000000000000000000000D); //0
double res1 = Math.Round(1.500000000000000000000000000D); //2
double res2 = Math.Round(2.500000000000000000000000000D); //2
double res3 = Math.Round(3.500000000000000000000000000D); //4
double res4 = Math.Round(4.500000000000000000000000000D); //4
double res5 = Math.Round(5.500000000000000000000000000D); //6
double res6 = Math.Round(6.500000000000000000000000000D); //6
W komentarzach jest informacja co metoda zwraca.
double d = 0D;
decimal m = 0M;
 
double growD = 0.1D;
decimal growM = 0.1M;
for (int i = 0; i < 10; i++)
{
    d += growD;
    m += growM;
    Console.WriteLine("double :" + d.ToString("R"));
    Console.WriteLine("decimal:" + m.ToString("G"));
    Console.WriteLine();
}
 
A wynik prostego dodawania przedstawiony jest poniżej:



Jak widać na doublach można się mocno przejechać.

czwartek, 3 maja 2012

Algorytmy sortowania

Aby poćwiczyć algorytmikę napisałem parę algorytmów sortowania i sprawdziłem czasy ich działania. Porównałem 12 algorytmów sortowania (m.in. Bubble Sort, Cocktail, Counting Sort, Insert Sort, Merge Sort, ShellSort, Stooge Sort). Kod z algorytmami sortowania można pobrać z github.com/arekbee/SortEngines. Podczas pisania nie kierowałem się złożonością obliczeniową tych algorytmów, ale byłem ciekaw w jakim czasie mogę posortować tablicę z liczbami.

Jak wiadomo, czas sortowania zależny jest od danych. Dane do posortowania składały się z liczb naturalnych. Każdy z algorytmów został sprawdzony pod 6-ma rożnymi tablicami danych. Pierwszy typ danych składał się z liczb losowych (random). Dla każdego algorytmu były te same dane. Drugi typ składał się z tablicy, w której pierwsza liczba była maksymalną liczbą, a pozostałe elementy były już posortowane w sposób rosnący (increasing). Następnym typem danych był modyfikacją poprzedniej tablicy poprzez wprowadzenie powtórzeń wartości tej tablicy (increasing-repeated). Ilość powtórzeń wynosiła wartość pierwiastka z ilości elementów w tablicy (jeżeli elementów w tablicy było 10 000 to ilość powtórzeń jednego elementu wynosiła 100). Skoro już była tablica "prawie" posortowana w sposób rosnąco to następnym typem danych była tablica posortowana z sposób malejąco, ale pierwszy element wynosił 0 (decreasing). Analogicznie, do następnego typu danych wprowadzono modyfikację poprzez powtarzanie tych samych elementów (decreasing-repeated). Ostatnim typem danych była tablica składająca się z jedynki i samych zer (onezero). Algorytm o nazwie BuildInNet to standardowy algorytm sortowania listy przygotowany przez MS i jest on zaimplementowany jako agorytm Quicksort.

Poniżej jest przedstawiony wykres w skali logarytmicznej z czasem działania algorytmów dla losowo wygenerowanych danych. Oś odcięta stanowi grupę ilości danych ( odpowiednio 10, 100, 1 000, 10 000 i 100 000 elementów w tablicy), a oś rzędnych przedstawia czas działania algorytmu w milisekundach.



A poniżej są tablice z wynikami sortowania. Wartości czasu sortowania są przedstawione w milisekundach.


Jak widać w poniższej tablicy, wprowadzenie powtarzalnych elementów nie zmienia znacząco czasu działania algorytmów.





Jak widać na powyższych tabelkach, 3 algorytmy działają stosunkowo długo oraz nie mają znaczenia czy dane są posortowane w postaci rosnąco czy malejąco. Te algorytmy to: Odd-Even sort, Selection i Stooge sort. Takie algorytmy jak Quicksort, BuildInNet Counting i ShellSort działają równie szybko dla tablicy prawie posortowanej rosnąco jak i malejąco. Dla tablicy z jedną modyfikacją (onezero) oraz z prawie posortowaną tablicą (increasing), selection sort ma gorszy wynik czasu sortowania niż dla algorytmów bubble sort, comb sort czy sortowanie gnoma, mimo że dla innych danych te algorytmy są szybsze.
Algorytm Stooge sort ma najgorszą złożoność obliczeniową. Dla 10 000 elementów czas działania był o 3 rzędy wielkości większy niż dla słabych algorytmów. Sortowanie zostało zatrzymane dla 100 0000 elementów,gdyż czas sortowania wynosił 489 557 429 ms, a to jest ... strasznie długo. W przybliżeniu stanowi to 5 dni i 15 godzin. Gdy sprawdzałem dane, to okazało się, że dane zostały posortowane do 48 147 elementu. Dla tablicy liczącej do 1000 elementu nie ma znaczenia jaki algorytm zastosujesz z sortowaniu (za wyjątkiem nieszczęsnego stoogesorta).
Do dalszych testów wybrałem 6 najlepszych algorytmów. W śród nich są: Counting, Quicksort, Shellsort, Mergesort, Insertsort i dla porównania BuildInNet (algorytm Quicksort w BCL). Poniższy wykres przedstawia czas sortowania w skali logarytmicznej dla poszczególnej ilość danych (1000, 10 000, 100 000 i 1 000 000 elementów).





Z tego można wybrać 4 najlepsze algorytmy. Poniżej wykres dla tablicy z danymi losowymi (random) w skali liniowej (OY przedstawia czas działania algorytmu w milisekundach).




W trakcie przerwy w pisaniu algorytmów miałem możliwość zainteresowania się tańcami ludowymi:)








Bardzo mi się podobają filmiki przedstawiające algorytmy sortowania za pomocą tańców. Jestem bardzo ciekaw jak można by było przedstawić jakiś algorytm za pomocą ruedy z salsy :) Może problem ucztujących filozofów.

poniedziałek, 27 lutego 2012

Sieć bayesowska w .NET

Sieć bayesowska jest zaawansowaną probabilistyczną metodą odkrywania wiedzy i wnioskowania. Przedstawia ona zależności pomiędzy zdarzeniami bazując na wzorze Bayesa oraz rachunku prawdopodobieństwa. Umożliwia reprezentację probabilistycznych zależności przyczynowych między dowolnymi atrybutami (zdarzeniami). W praktyce sieć bayesowska jest reprezentowana przez skierowany graf acykliczny. Największą korzyścią sieci bayesowskiej jest czytelna i intuicyjna graficzna reprezentacja wiedzy o bezpośrednio zachodzących zależnościach.

Poniżej przedstawiony jest przykład modelu graficznego sieci. Mokra trawa(atrybut WetGrass) jest bezpośrednio uzależniona od dwóch czynników: czy został załączony zraszacz (Sprinkler) oraz od tego czy padał deszcz (Rain). Te dwa czynniki są uzależnione od pochmurności ( atrybut Cloudy). Zgodnie z relacją przechodnią, mokra trawa jest pośrednio zależna od pochmurności. Każdy z atrybutów ma dwie opcje: może zajść lub nie może zajść (T i F). Dla każdej kombinacji przedstawione jest prawdopodobieństwo wystąpienia takiego zdarzenia.


Dajmy na to, że chcemy obliczyć z jakim prawdopodobieństwem padał deszcz (Rain(R)=T) przy zaistnieniu (zaobserwowaniu) mokrej trawy (atrybut WetGrass(W)= T). Czyli mamy do czynienia z prawdopodobieństwem warunkowym P(R|W=T).
Do implementacji takiego modelu z pomocą przychodzi nam projekt o naziwe Infer.NET. Służy on m.in. do wnioskowania dla bayesowskiego modelu graficznego. Implementacja przedstawiona jest poniżej:
#region implementacja modelu
     //pochmurnie
     Variable<bool> cloudy = Variable.Bernoulli(0.5);

     // spryskiwacz 
     Variable<bool> sprinkler = Variable.New<bool>();
     using (Variable.If(cloudy))
            sprinkler.SetTo(Variable.Bernoulli(0.1));

     using (Variable.IfNot(cloudy)) 
            sprinkler.SetTo(Variable.Bernoulli(0.5));

     // deszcz
     Variable<bool> rain = Variable.New<bool>();
     using (Variable.If(cloudy)) 
               rain.SetTo(Variable.Bernoulli(0.8));

     using (Variable.IfNot(cloudy)) 
               rain.SetTo(Variable.Bernoulli(0.2));

    // mokra trawa
    Variable<bool> wetGrass = Variable.New<bool>();
    using (Variable.If(sprinkler))
    {
           using (Variable.If(rain)) 
                  wetGrass.SetTo(Variable.Bernoulli(0.99));

           using (Variable.IfNot(rain)) 
                  wetGrass.SetTo(Variable.Bernoulli(0.9));
    }
    using (Variable.IfNot(sprinkler))
    {
           using (Variable.If(rain)) 
                  wetGrass.SetTo(Variable.Bernoulli(0.9));

           using (Variable.IfNot(rain)) 
                  wetGrass.SetTo(Variable.Bernoulli(0.0));
    }
#endregion

#region wnioskowanie
wetGrass.ObservedValue = true;  //mokra trawa
InferenceEngine ie = new InferenceEngine();
ie.ShowProgress = false;
Console.WriteLine("P(deszcz | trawa jest mokra)=" 
        + ie.Infer(rain));

Console.WriteLine("P(spryskiwacz | trawa jest mokra)=" 
        + ie.Infer(sprinkler));

cloudy.ObservedValue = false; //nie jest pochmurnie
Console.WriteLine("P(deszcz | trawa jest mokra,  nie jest pochmurnie)="
       + ie.Infer(rain));

Console.WriteLine("P(spryskiwacz | trawa jest mokra, nie jest pochmurnie)="
       + ie.Infer(sprinkler));
#endregion


W 60 linijkach mamy zaimplementowany cały model graficzny oraz mechanizm wnioskujący. Dla potrzeb publikacji zamieściłem zdjęcie z okienkiem całej aplikacji oraz prawdopodobieństwa dla paru innych warunków.



Implementacja podanego przykładu można znaleźć pod adresem Bayesian Networks na Codeplex. Więcej o samej sieci bayesowskiej jest na wykładzie pt. Introduction To Bayesian Inference.

wtorek, 23 listopada 2010

matematyka != obliczenia

Widziałem video Conrad Wolfram o aspektach nauczaniu matematyki. Wolfram mówi o tym, aby obliczenia, symulacje, wyniskowanie oraz nauczaniem było zadaniem komputerów, a nie ludzi. Ludzie są od utworzenia zadania oraz ustaleniem problemu. Conrad Wolfram jest jednym z twórców świetnej wyszukiwarki . Więcej o projekcie Wolfram Alpha można znaleźć w drugim filmiku.