問題タブ [recursion]

以下は、マシン上にあるファイルの数をカウントするかなり単純な関数です。「C：\」で呼び出され、実行には約5秒かかります。しばらく実行していないか、最初にRAMクリアプログラムを実行していない限り、60秒以上かかります。毎回新しいスキャンを実行しているので（つまり、このスキャンだけなので、プログラムの新しいインスタンスを開始しているので）キャッシュされている可能性があるとは思いませんでしたが、おそらくメモリ割り当てに関連していますか？その高速実行を毎回実行する方法、またはそれが実行できない理由についてのアイデアはありますか？他のプログラム（SpaceMongerなど）は、RAMをクリアしたり、実行の合間に長時間待機したりしても、10秒でファイルの総数を取得できます。したがって、必ずしもVBである必要はありませんが、これを行う方法は間違いなくあります。

私はおそらくこれを自分で書くことができますが、それを達成しようとしている特定の方法は私をうんざりさせています。私は、.NET 3.5 で導入された他のものと同様の汎用拡張メソッドを作成しようとしています。これは、入れ子になった IEnumerables の IEnumerable (など) を取り、それを 1 つの IEnumerable にフラット化します。誰にもアイデアはありますか？

具体的には、平坦化アルゴリズムに取り組むことができるように、拡張メソッド自体の構文に問題があります。

最近では、かなりの数の主流言語が関数リテラルをサポートしているようです。無名関数とも呼ばれますが、名前があっても構いません。重要なことは、関数リテラルは、他の場所でまだ定義されていない関数を生成する式であるため、たとえば C では&printfカウントされないということです。

追加する編集：本物の関数リテラル式がある場合は、それを関数に渡すか、すぐに引数に適用<exp>できるはずです。.f(<exp>)<exp>(5)

recursiveである関数リテラルを記述できる言語はどれか知りたいです。ウィキペディアの「匿名再帰」の記事には、プログラミングの例はありません。

再帰的階乗関数を例として使用しましょう。

ここに私が知っているものがあります：

• JavaScript / ECMAScript でそれを行うことができますcallee:

  /li>

• を使用する言語では簡単ですletrec。たとえば、Haskell (これはそれを呼び出しますlet):

  let fac x = if x<2 then 1 else fac (x-1) * x in fac

  LispとSchemeにも同等のものがあります。のバインディングはfac式に対してローカルであるため、式全体が実際には無名関数であることに注意してください。

他にもありますか？

私は単純な問題を解決するために長年のプログラミングで再帰をかなり使用してきましたが、メモリ/速度の問題のために反復が必要になる場合があることを十分に認識しています。

そのため、非常に遠い昔、反復への一般的な再帰アプローチを変換する「パターン」またはテキストブックの方法が存在するかどうかを試してみましたが、何も見つかりませんでした。または、少なくとも私が覚えていることは何も役に立ちません。

• 一般的なルールはありますか？
• 「パターン」はありますか？

私はしばらくの間BSPツリーをいじくり回していて、スレッドもいじっています。BSPツリーに三角形を追加すると、データを並列処理する目的で新しいスレッドを作成する機会が生じます。

上記の2つの挿入操作は、2つのスレッドで実行できます。また、同じデータを変更しないため、安価な同期を使用できます。

この新しいメソッドは、スレッドを作成して操作を並行して完了しようとしますが、スレッドを作成できない場合でも失敗することはありません（単に元のアルゴリズムに戻ります）。

これは適切なプログラミング手法ですか、それともスレッドを不適切に使用していますか？私はこの技術に関する文献を見つけることができませんでした。私は、CPUを最大限に（2コア）使用する傾向があり、理論的には、使用可能な任意の数のプロセッサーに拡張できるのが好きです。CPUとメモリにひどく無駄になるのは好きではありません。

通常、変数または関数が使用されているファイルを見つけようとするときに、これを数回行う必要がありました。

これを行うために、過去に grep で xargs を使用したことを覚えていますが、もっと簡単な方法があるかどうか疑問に思っています。

Item_ID、Item_ParentID の通常のツリー構造を持つ SQL サーバーのテーブルがあります。特定の Item_ID (任意のレベル) のすべての CHILDREN を反復して取得したいとします。

再帰はこの問題の直観的な候補のようで、これを行う SQL Server 関数を作成できます。

テーブルに多くのレコードがある場合、これはパフォーマンスに影響しますか? 再帰を避けて単純にテーブルをクエリするにはどうすればよいですか? 提案をお願いします。

順序付けられたツリー階層を格納するフラット テーブルがあるとします。

ここに がある図があります[id] Name。ルート ノード 0 は架空のものです。

それを正しい順序で正しくインデントされたツリーとして HTML (またはテキスト) に出力するには、どのような最小限のアプローチを使用しますか?

さらに、基本的なデータ構造 (配列とハッシュマップ) しかなく、親/子の参照を持つ派手なオブジェクトはなく、ORM もフレームワークもなく、両手だけしかないと仮定します。テーブルは結果セットとして表され、ランダムにアクセスできます。

疑似コードまたは平易な英語で問題ありません。これは純粋に概念上の問題です。

おまけの質問: このようなツリー構造を RDBMS に格納する根本的に優れた方法はありますか?

編集と追加

あるコメント投稿者 ( Mark Besseyさん) の質問に答えるには: ルート ノードは必要ありません。とにかく表示されることはないからです。ParentId = 0 は、「これらがトップ レベルであること」を表すための規則です。Order 列は、同じ親を持つノードがどのようにソートされるかを定義します。

私が話した「結果セット」は、ハッシュマップの配列として描くことができます (その用語にとどまります)。私の例では、すでにそこにあるはずでした。いくつかの答えは、さらに一歩進んで最初に構築しますが、それは問題ありません。

ツリーの深さは任意です。各ノードは N 個の子を持つことができます。ただし、「何百万ものエントリ」ツリーを念頭に置いているわけではありません。

私が選んだノード名 ('Node 1.1.1') を信頼できるものと間違えないでください。ノードは、'Frank' または 'Bob' と同じように呼ぶことができます。命名構造は暗示されていません。これは単に読みやすくするためです。

独自のソリューションを投稿したので、皆さんはそれをバラバラにすることができます。

私は最近、再帰と Big-O 記法を含むコンピューター サイエンスの宿題に取り組んでいます。私はこれをかなりよく理解していると思います (ただし、完全ではないことは確かです!)。奇妙なことに、それを見ると、宿題の中で最も単純なもののように見えます。

次の再発の解決策として、big-Oh 表記法を使用して最高の成長率を提供してください。

T(1) = 2

T(n) = 2T(n - 1) + 1 for n>1

選択肢は次のとおりです。

• O(n log n)
• O(n^2)
• O(2^n)
• O(n^n)

大きな O が上限として機能し、プログラムまたはプロセスにかかる最大の計算量または最大実行時間を表すことを理解しています。この特定の再帰は O(n) であるべきだと思います。なぜなら、再帰は n の値ごとに 1 回しか発生しないからです。n が利用できないので、他の 3 つのオプションである O(nlogn) よりも良いか、悪いかのどちらかです。

だから、私の質問は: なぜこれは O(n) ではないのですか?

このメソッドを任意の数の引数に対して機能させたいのですが、コード生成(多くの醜いコード)でそれを行うことができますが、再帰で行うことができますか? もしそうならどのように？私は再帰を理解していますが、これを書く方法がわかりません。