Windows PowerShellでProject Euler（21） ArrayList

Problem 14

.netのArrayListを使ってみます。

$a = New-Object System.Collections.ArrayList(10)

これは領域確保するだけ、すなわちstd::vectorでいうreserveしただけのようです。ここからAddで追加していきます。

$a.Add(1)

しかし、Addメソッドは挿入された位置を返すので、これを避けるためには次のようにします。

[void]$a.Add(2)

また、こんなこともできます。

$a.AddRange(0..3)

これで

$a

とすると、前にAddしたのとあわせて、

1
2
0
1
2
3

と表示されます。
この問題では配列の代わりにArrayListをほぼ同じように使えます。
配列を使うのとほとんど時間は変わりませんでした。

function fold($f, $init) {
    begin   { $x = $init }
    process { $x = & $f $x $_ }
    end     { $x }
}

function Collatz($n) {
    if($n -ge $M -or $a[$n] -lt 0) {
        if($n % 2 -eq 0) { $p = $n / 2 } else { $p = $n * 3 + 1 }
        $l = 1 + (Collatz $p)
        if($n -le $M) {
            $a[$n] = $l
        }
        $l
    }
    else {
        $a[$n]
    }
}

function max($x1, $x2) {
    $m1, $n1 = $x1
    $m2, $n2 = $x2
    if($m1 -gt $m2) { $x1 } else { $x2 }
}

$watch = New-Object System.Diagnostics.Stopwatch
$watch.Start();
$M = 100
$a = New-Object System.Collections.ArrayList($M + 1)
$a.AddRange(-1..(-$M - 1))
$a[1] = 1
($M/2+1)..$M | foreach { ,((Collatz $_), $_) } | fold { max $args[0] $args[1] } (0, 0)
$watch.Stop();
$watch.Elapsed.TotalMilliSeconds / 1000