質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
PowerShell

Windows PowerShellはコマンドラインインターフェースであり、システム管理を含むWindowsタスク自動化のためのスクリプト言語です。

Q&A

0回答

327閲覧

iの値を順番に出力するスクリプトの計算量を削減したい

falcon_function

総合スコア6

PowerShell

Windows PowerShellはコマンドラインインターフェースであり、システム管理を含むWindowsタスク自動化のためのスクリプト言語です。

0グッド

0クリップ

投稿2023/01/23 10:39

前提

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

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

Zuishin

2023/01/23 10:50

> i=1からi=nまでiの値を出力するスクリプトの処理速度を上げたい O(n) です。ほんとうに 1 から n まで表示するだけなら O(1) もしくは O(log n) にする方法も無くはありませんが、実用的な処理では O(log n) にはなりません。 > ・実装には至っていないが、2のn乗同士の足しざん同士ならすべての数を表せるということまでは分かっているが、どういう規則になるのかわからないため、2のn乗のみ出力する関数しか制作していない。 この場合は使えません。
otn

2023/01/23 11:12

O(log n) で出来ると思った理由は何でしょうか?
matukeso

2023/01/23 15:31

Write-Host一回が自体O(logN)のオペレーションだから、それをforで回したらO(NlogN)ではないの?
Zuishin

2023/01/24 00:12

何を N と想定しているのかよくわかりませんが、ないでしょう。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

まだ回答がついていません

会員登録して回答してみよう

アカウントをお持ちの方は

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問