PowerShell -Part 5

**デフォルトの名無しさん** · 2021/03/18(木) 00:29:52.04

前スレ
PowerShell -Part 4
https://mevius.5ch.net/test/read.cgi/tech/1577862511/

次スレは>>980が立ててね！！

**デフォルトの名無しさん** · 2022/02/21(月) 14:38:31.70

(実装は暗黙のCPSかもしれないけど) schemeだとdelay/forceそのまんまじゃね

イテレータとかストリームとか色んな言い方があるけど、何にせよ処理すべきデータがまだ存在していないような時にのみ有効
もし処理対象のデータが既に存在しているのなら、単に無駄な計算を増やすだけだよ

**デフォルトの名無しさん** · 2022/02/21(月) 14:43:51.48

再帰処理したいつってる本人が理解できないと意味ないからな
再帰が軽い言語で処理すりゃいいんじゃねーの

**デフォルトの名無しさん** · 2022/02/21(月) 15:22:36.66

コールスタック制限してない言語の方が珍しいと思うがね、スクリプト言語なら500-1000くらいが標準的か

とりあえず言語によって課される安全装置としてのコールスタック制限を回避したいのなら、>>984が求めている資料はこれだと思うhttps://www.python.org/doc/essays/graphs/(pwshじゃなくてすまん)
生リスト(配列)を使ってもいいけど、現実的な時間で可能なのか怪しい程の難問なので、これの出番かも

https://docs.microsoft.com/en-us/dotnet/api/system.collections.stack?view=net-6.0
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.stack-1?view=net-6.0

**デフォルトの名無しさん** · 2022/02/21(月) 15:34:29.48

ごめんdfsだわこれ
全要素網羅したい、という要求だからどっちでもいいと思うけど
queueはこれ使うと配列よりかなり速いはず
https://docs.microsoft.com/ja-jp/dotnet/api/system.collections.generic.queue-1?view=net-6.0

**デフォルトの名無しさん** · 2022/02/21(月) 16:03:11.06

すみません、めちゃくちゃ難しいっす

なんとなくリンク先のスクリプトが
動かせればと思ったのですが…

やはり悪手なんですかね

**デフォルトの名無しさん** · 2022/02/21(月) 16:22:43.74

データのサンプル、期待する出力を書いてくれれば具体的なコード提案できるかも（たぶん）

**デフォルトの名無しさん** · 2022/02/21(月) 18:40:11.40

色々回答してありがとうございました

結局再帰を使わずループで代用する
こととしました

トランポリンはもう少し
勉強してみたいと思います

**デフォルトの名無しさん** · 2022/02/21(月) 20:07:10.97

powershell内でC#埋め込めばいいんじゃないの
あいにくpowershellのクロージャはダイナミックスコープで使えたもんじゃないのでC#のサンプルだけ

Add-Type -TypeDefinition @"
using System;
public static class test {
　static int fib(int n) { //普通の再帰
　　if (n < 2) {
　　　return n;
　　} else {
　　　return fib(n - 1) + fib(n - 2);
　　}
　}
　static void fibcps(int n, Action<int> cont) { // CPS(継続渡しスタイル)
　　if (n < 2) {
　　　cont(n);
　　} else {
　　　fibcps(n - 1, n1 =>
　　　　fibcps(n - 2, n2 =>
　　　　 cont(n1 + n2)));
　　}
　}
　public static void recurse() {
　　for (var n = 0; n <= 20; ++n) {
　　　Console.WriteLine("fib {0}: {1}",n,fib(n)); //普通の再帰
　　　fibcps(n, r => Console.WriteLine("fibcps {0}: {1}",n,r)); // CPS(継続渡しスタイル)
　　}
　}
}
"@
[test]::recurse()

**デフォルトの名無しさん** · 2022/02/21(月) 21:16:04.35

一応powershell版。ただしpowershell関数は末尾再帰の最適化をしてくれないためCPSで書いてもただの効率悪い再帰にしかならない。
上のC#も32bit環境だと末尾再帰の最適化が働かないため64bit環境でのみ有効なコード。
function fib($n) {
　if ($n -lt 2) {
　　$n
　} else {
　　(fib ($n - 1)) + (fib ($n - 2))
　}
}
function fibcps($n, $cont) {
　if ($n -lt 2) {
　　& $cont $n
　} else {
　　fibcps ($n - 1) {param($fib1); $cont = $cont
　　　fibcps ($n - 2) {param($fib2);
　　　　& $cont ($fib1 + $fib2) }.GetNewClosure()}.GetNewClosure()
　}
}
1..10 | %{ $r=fib $_; "fib($_):$r" }
1..10 | %{ fibcps $_ {param([int]$r) "fibcps($_):$r"}.GetNewClosure() }

**デフォルトの名無しさん** · 2022/02/21(月) 21:38:24.93

変なやり方を広めようとするやつの典型例

**デフォルトの名無しさん** · 2022/02/22(火) 00:12:46.08

あえて混乱させようとしてるようにしか思えない

仮に末尾最適化でシリアルなコードを得たとして、まさかそれが木の探索に有利だとでも？

呼び出しをstart-(thread)jobで行ってスレッド/プロセスをばら撒けば済む話じゃないの
コールスタック溢れるような計算であればあるほど、スケーラブルで高速

**デフォルトの名無しさん** · 2022/02/22(火) 02:35:33.30

スタックを使わない再帰呼び出しならスタックは溢れないなw
個々の再帰呼び出しをStart-ThreadJob/Wait/Receiveで機械的に置き換えればとりあえず動く雛形にはなる
代わりにプロセス/スレッドが溢れるけど、スレッドなら単に順番待ちに入るだけで悪さはしない

個々のワーカーが自身の子をwaitしている限りはオーバーヘッドでしかないので、メインプロセスを設けStart時に-StreamingHostで直接報告を挙げさせるべき
長く走ってる枝を殺す等、最適化の可能性は大

メモ化や大域脱出程度で済むような問題には薦めない

**1001** · Over 1000

このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 341日 2時間 5分 41秒