私はJでlookandsay（OEIS A005150）の実装で遊んでいますwhile.。タイプ制御構造を使用して、両方とも非常に単純な2つのバージョンを作成しました。1つは繰り返し、もう1つはループします。私は強迫的であるため、バージョンで比較タイミングを実行し始めました。
見て、言うのは、s、1つ、2つなどのシーケンス1 11 211211111221です。
リストの初期の要素（最大約20）の場合、ループバージョンが優先されますが、その量はごくわずかです。30前後のタイミングでは、再帰バージョンが勝ちます。スタックスペースがそれをサポートするのに十分である場合、再帰バージョンが優先される可能性があります。その理由を調べましたが、それは中間結果の処理に関係していると思います。シーケンスの30番目の数字は5808桁です。（32番目の数字、9898桁、34番目、16774。）
再帰で問題を実行しているときは、再帰呼び出しで中間結果を保持できます。最後にスタックを解除すると、結果の処理が最小限になるように結果が作成されます。
リストバージョンでは、結果を保持するための変数が必要です。ループを繰り返すたびに、結果に2つの要素を追加する必要があります。
問題は、私が見ているように、既存の配列を完全に再割り当てせずに変更する方法をJで見つけることができないことです。だから私は言っている
try. o =. o,e,(0&{y) catch. o =. e,(0&{y) end.
開始時にoに値がない可能性があるoに要素を配置します。それは著しく遅いかもしれません
o =. i.0
.
.
.
o =. (,o),e,(0&{y)
ポイントは、ほつれがないと結果が間違った形になるということです。なんとなくi.0から形を継承しています。
ただし、} amendのような関数でさえ、リストを変更せず、変更が加えられたリストを返します。リストを保存する場合は、リストを割り当てる必要があります。割り当てられたリストのサイズが大きくなるにつれて（番号を最初から最後まで歩いて次の番号を作成するにつれて）、割り当てにはさらに時間がかかるように見えます。この割り当ては、要素32、9898桁を作成し、再帰バージョンでは時間がかからないのに対し、要素20（408桁）はループバージョンでは時間がかからないことを私が確認できる唯一のことです。
再帰バージョンは、次のようにリターンを構築します。
e,(0&{y),(,lookandsay e }. y)
上記の行は、関数からの戻り行と再帰の両方であるため、呼び出しが文字列の最後に到達し、すべてがアンスタックされると、戻りベクトル全体が一度に構築されます。
APLでは、次のようなことを言うことができると思いました。
a[1+rho a] <- new element
しかし、NARS2000でこれを試してみると、インデックスエラーが発生することがわかりました。私は他のAPLにアクセスできません。APLPlusのこのイディオムを覚えているかもしれませんが、APL\360またはAPL\1130でこのように機能したとは思えません。私はそれを完全に覚えていないかもしれません。
Jでそれを行う方法を見つけることができません。それを行う方法がない可能性がありますが、次の考えは、結果を保持できる配列を事前に割り当て、個々のエントリを変更することです。それを行う方法もわかりません。つまり、JはAPLイディオムをサポートしていないようです。
a<- iota 5
a[3] <- -1
これは、言語の純粋さのために許可されていない副作用の1つですか？
インタプリタは、またはそのバリアントの一部を、内部的a=. a,fooにファストパスする必要があるものとして認識していますか？a[>:#a]=.foo
これは再帰バージョンであり、そのためだけのものです。私はさまざまなバージョンを試しましたが、プログラムが長いほど遅くなり、一般的に複雑になるほど遅くなると思います。一般に、プログラムはチェーン化できるため、n番目の数値が必要な場合は、lookandsay ^：n]yを実行できます。いくつかの最適化を試しましたが、問題は、出力を送信する環境がわからないことです。プログラムの次のイテレーションに送信していることがわかった場合は、大きな数ではなく、数字の配列として送信します。
また、コードの暗黙のバージョンを作成する方法を理解できれば、コードを短くする必要があるものをコードに追加すると、実行時間が長くなるという私の発見に基づいて、実行速度が速くなると思います。
lookandsay=: 3 : 0
if. 0 = # ,y do. return. end. NB. return on empty argument
if. 1 ~: #@$ y do. NB. convert rank 0 argument to list of digits
y =. (10&#.^:_1) x: y
f =. 1
assert. 1 = #@$ y NB. the converted argument must be rank 1
else.
NB. yw =. y
f =. 0
end.
NB. e should be a count of the digits that match the leading digit.
e=.+/*./\y=0&{y
if. f do.
o=. e,(0&{y),(,lookandsay e }. y)
assert. e = 0&{ o
10&#. x: o
return.
else.
e,(0&{y),(,lookandsay e }. y)
return.
end.
)
生成された数字の特徴に興味がありました。1から始めると、数字が3より大きくなることはありません。3より大きい数字から始めると、シングルトンとして存続します。また、何かから始めることで、生成された数字に数字を入れることもできます。 888888888のように、1つの9が含まれ、番号の最後に1つの8が含まれる番号が生成されます。ただし、シングルトンを除いて、3を超える数字はありません。
編集：私はもう少し測定をしました。私はもともと、ベクトルまたはスカラーのいずれかを受け入れるようにプログラムを作成していました。内部的にはベクトルを使用するという考えです。コードのあるレイヤーから別のレイヤーにベクトルを渡すことを考えていましたが、それでも左の引数を使用してコードを制御する可能性があります。トップレベルのベクトルを渡すと、コードは非常に高速に実行されるため、非常に長い数値をベクトルから数字に変換することで、ほとんどのCPUが消費されていると思います。再帰ルーチンは、再帰するときに常にベクトルを渡します。これが、ループとほぼ同じ速度である理由である可能性があります。
それは私の質問を変えません。
これに対する答えがありますが、3時間投稿できません。それでは投稿しますので、たくさんの調査をして答えないでください。