前提
Powershellで実行すること
O(n)の計算量から少なくともO(logn)まで処理速度を上げる
実現したいこと
- i=1からi=nまでiの値を出力するスクリプトの処理速度を上げたい
発生している問題・エラーメッセージ
単純にfor文でiの値を出力するコード自体は作成できますが、これを半分以下の計算量で同じ動作をさせるアルゴリズムが分かっておりません。
該当のソースコード
Powershell
1for($i=1;$i -le 1000;$i++){ 2 Write-host $i 3} 4
試したこと
・Measure-commandにおいて、上記ソースコードのタイム計測を行った。
実行結果:
Days : 0
Hours : 0
Minutes : 0
Seconds : 0
Milliseconds : 814
Ticks : 8146149
TotalDays : 9.42841319444444E-06
TotalHours : 0.000226281916666667
TotalMinutes : 0.013576915
TotalSeconds : 0.8146149
TotalMilliseconds : 814.6149
・実装には至っていないが、2のn乗同士の足しざん同士ならすべての数を表せるということまでは分かっているが、どういう規則になるのかわからないため、2のn乗のみ出力する関数しか制作していない。
Powershell
1$MOD=[math]::Pow(10,9) 2$MOD=$MOD+7 3#算術オーバーフロー対策用 4 5function Two_Of_Pow([long]$n){ 6 [long]$ret=1 7 [long]$mythic=2 #指数部分 8 while($n -gt 0){ 9 if($n -band 1){ 10 $ret=$ret *$ret % $mod 11 } 12 $mythic=$mythic * $mythic % $mod 13 $n=$n -shr 1 14 } 15 return $ret 16} 17#上記は繰り返し二乗法のソースコード
補足情報(FW/ツールのバージョンなど)
Powershell5.1
あなたの回答
tips
プレビュー