問題タブ [memoization]

私は三角数を見つける関数を書いています、そしてそれを書く自然な方法は再帰的にです：

しかし、最初の100,000の三角数を計算しようとすると、しばらくするとスタックオーバーフローが発生して失敗します。これはメモ化するのに理想的な関数ですが、渡した関数をメモ化するソリューションが必要です。

これに関する他の投稿を見たことがありますが、Haskell でこれを行うクリーンな方法はありますか?

第2部として、関数をモナドにせずに行うこともできますか?

上記のコードサンプルは、メモ化を使用して、いくつかの入力に基づいて再帰式を計算しますn。同じ式を使用する純粋な再帰関数を記述したため、これがメモ化を使用していることはわかっていますが、これは、の値がはるかに大きい場合にはるかに高速ですn。私はこれまでベクターを使用したことがありませんが、いくつかの調査を行い、ベクターの概念を理解しています。メモ化では、計算された各値が保存されることになっているため、同じ計算を繰り返し実行する代わりに、すでに計算された値を簡単に取得できることを理解しています。

私の質問は、このメモ化はどのように行われ、どのように機能するのかということです。nの値がすでに存在するかどうかを確認する時点で、コードを確認できないようです。また、の目的がわかりませんif(as[n]<=0)。この式は正と負の値を生成する可能性があるため、このチェックが何を探しているのかわかりません。

ありがとう、私はこれがどのように機能するかを理解していると思います。実際、私が思っていたよりも少し単純です。

シーケンス内の値が0になることはないと思います。したがって、nは1から開始する必要があると思うので、これでうまくいくはずです。

しかし、ゼロが私のシーケンスで実行可能な数であった場合、それを解決できる別の方法は何ですか？たとえば、5つが表示されない場合はどうなりますか？ベクトルを5で埋める必要がありますか？

編集：うわー、コードをチェックしてこれを入力しているときに、他にもたくさんの応答がありました。皆さんの助けに感謝します、私は今それを理解していると思います。

Predicate<Foo> を受け入れ、一致する項目のリストを返す C# メソッドがあります...

フィルタは、多くの場合、一般的なセットの 1 つになります...

...しかし、匿名の代理人である可能性があります。

このメソッドで結果を ASP.NET キャッシュにキャッシュするようにしたいので、同じデリゲートを繰り返し呼び出すと、キャッシュされた結果が返されます。このために、デリゲートからキャッシュ キーを作成する必要があります。Delegate.GetHashCode() は、この目的のために適切な結果を生成しますか? 私が見るべきデリゲートの他のメンバーはいますか? これをまったく別の方法で行いますか？

私はLisp初心者です。Collat​​z列の項数を計算するための再帰関数をメモしようとしています ( Project Eulerの問題 14 用)。私のコードはまだです：

memoize 関数は、 On Lispブックで提供されているものと同じです。

このコードは、メモ化されていないバージョンと比較して実際にはスピードアップしません。これは、関数のメモ化されていないバージョンを呼び出す再帰呼び出しが原因であると考えられますが、これは一種の目的を無効にします。その場合、ここでメモ化を行う正しい方法は何ですか? 元の関数へのすべての呼び出しでメモ化されたバージョン自体を呼び出して、特別な m-collat​​z-steps シンボルの必要性をなくす方法はありますか?

編集：コードを修正しました

これは私のコードにあったものです。編集の前に、私が誤って入れたもの:

そのエラーを見て別のアイデアが浮かび、この最後の defvar 自体を使用して、再帰呼び出しを次のように変更してみました

これはメモ化 (約 60 秒から 1.5 秒への高速化) を実行しているように見えますが、元の関数を変更する必要があります。元の機能を変更する必要のない、よりクリーンなソリューションはありますか?

Haskell で配列を使用したキャッシング (メモ化) の実装について質問があります。次のパターンが機能します。

しかし、これはそうではありません（プログラムの速度は、呼び出しごとに配列が再作成されていることを示唆しています）：

where句の外側（「グローバルスコープ」内）でfAを定義することも、どちらのパターンでも機能します。

上記の 2 つのパターンの違いについて、誰かが技術的な説明をしてくれることを期待していました。

私は最新の GHC を使用していることに注意してください。これが単なるコンパイラの特性なのか、それとも言語自体の一部なのかはわかりません。

編集： ！は配列アクセスに使用されるため、 fA ! 5 は、C++ 構文の fA[5] を意味します。Haskell についての私の理解では、(fA !) n は (fA ! n) と同じであるということです...また、"fn = fA ! n" (括弧なし) と書く方がより一般的でした。とにかく、どのように括弧を付けても同じ動作になります。

問題を解決するために再帰またはメモ化を使用する選択肢がある場合、どちらを使用する必要がありますか? 言い換えれば、それらが正しい出力を提供し、使用しているコードで合理的に表現できるという点で両方とも実行可能なソリューションである場合、いつ一方を他方よりも使用するのでしょうか?

.ply ファイルとして保存されている 3d モデルをハーフ エッジ データ構造メッシュにロードする .PLY パーサーを構築しようとしています。

大きな質問で申し訳ありません。私は非常に冗長で、すべての詳細をレイアウトしたことを確認したかったのです。このため、最終的な目標をすぐにもう一度言います。これは、ユーザーが、続く巨大なテキスト ブロックを読む前に、私が何を望んでいるのかを理解できるようにするためです。

1) .PLY ファイルの頂点と面のリストからハーフエッジをメモ化するための適切なハッシュは何でしょうか?

また

2) .PLY ファイルのデータからハーフエッジ構造を埋めるためのより良い方法はありますか?

.PLY ファイルには頂点がリストされ、その後にメッシュの面が続きます。明らかな解決策は、最初に頂点テーブルを埋めてから、面リストを使用してエッジ テーブルを生成することです。問題は、すべてのエッジにパートナー エッジがあるため、クアッド メッシュの場合、ロードする最初のクワッドには 8 つのハーフ エッジが必要になることです。これは最初は問題ではありません。顔の 4 つのハーフエッジを作成し、各エッジを逆にして相手のハーフエッジを作成するだけです。ここでの問題は、4 つの異なる面に関連付けられた 4 つのぶら下がりハーフ エッジが作成されることです。

したがって、攻撃には 2 つの方法があります。最初に面のすべてのエッジを生成し、次にパートナーのエッジをペアにしようとします。私はこのアプローチが本当に好きではありません。多くの検索と並べ替えが必要になるため、プログラム的には効率が悪いようです。

2 番目: 最初に述べたように続行します。指定された最初の面から開始し、ポリゴンの作成に必要なエッジを生成します。エッジが作成されると、その双子も作成されます。ただし、エッジ リストをメモ化するので、すべてのエッジがテーブルにハッシュされます。次に、他の面のエッジを生成するときに、エッジが既に生成されている場合 (以前にロードされた面のパ​​ートナー エッジであるため)、テーブルからポインタを取得するだけです。

これは私が立ち往生しているところです。エッジ リストをメモ化するためのインテリジェントなハッシュ関数が必要です。効率を上げるには、衝突を最小限に抑える必要があります。私が今考えているスキームは、それらを作成した 2 つの頂点に基づいてエッジに名前を付けることです。IE エッジ 01 と 10 はツインです。最悪のシナリオでは、すべての頂点が結合される可能性のあるハッシュ テーブルが作成され、これは最終的にサイズ 2^n (n = 頂点の数) になり、これはまったく受け入れられません。私の目標は、衝突を最小限に抑えながら、ハッシュを実際のエッジの数 (= 面ごとのエッジの数の合計) に近づけることです。

*注意: ハーフエッジは「反時計回りのみ」の描画スキームを適用するため、名前の競合は発生しません。エッジを描画する 2 つの頂点に基づいてエッジに名前を付けることで、すべての名前が単一のハーフエッジに固有であることを保証します。

C# では、2 つの引数を持つ関数をメモ化するにはどうすればよいですか?

メモ化の前にカレーをしなければなりませんか?

Wes Dyer は、私が通常使用するメモ化コードを作成しましたが、現在は 2 つの引数が必要です

次の目的で、JavaScript 関数で静的変数を模倣しようとしています。

「折りたたみ」オブジェクトを保存して、呼び出しごとに「見つける」必要がないようにするにはどうすればよいですか? 名前付き関数を使用すると、「someFunction.myvar = collapse」のようなことができることはわかっていますが、このような匿名関数はどうですか?

ありがとう！