問題タブ [divide-and-conquer]

私はマージソート関数を書いていますが、今はテストケース配列を使用しています (入力はありません - これは今のところ静的です)。配列を引数として渡す方法がわかりません。ここに私のコードがあります：

この mergeSort 関数は機能しないことに注意してください。それらをマージする方法がまだわかっていないためです (それが私の課題です)。それを処理する前に 2 つのベクトルを並べ替えたいのですが、引数として配列を渡す必要があるため、これをコンパイルできません。私はポインターを理解していないので、それが解決策である場合、私の言い訳は無知です。私は現在、C++ を第一言語としてプログラミングを学んでおり、言語の機能の基本的な理解しかできていません。助けてくれてありがとう。

値からノードセットを作成するにはどうすればよいですか。

私はn個の番号1、2、3.......nを持っています。

ノードセットを作成したい

分割統治の手法は常に問題を同じタイプのサブ問題に分割するのでしょうか? 同じタイプとは、再帰を伴う関数を使用して実装できることを意味します。分割統治は常に再帰によって実装できますか?

ありがとう！

繰り返しのない数字を含むサイズ n の 2 つのデータベースがあります。したがって、合計で 2n 個の要素があります。一度に 1 つのデータベースへのクエリを介してアクセスできます。クエリは、ak を指定すると、そのデータベースで k 番目に小さいエントリを返すようなものです。O(log n) クエリのすべての 2n 要素の中で n 番目に小さいエントリを見つける必要があります。

アイデアは分割統治を使用することですが、これについて考える助けが必要です。ありがとう！

いくつかのチュートリアルをグーグル検索し、いくつかのSOの回答を閲覧しましたが、問題のレシピを見つけることができませんでした.

ほぼリアルタイムの株価チャートを表示することになっている Web サイトを書いています。データは常に更新される MySQL データベースに保存されます。グラフを描画するために必要なすべてのデータを取得する find_by_sql クエリ コードを作成しました。パフォーマンス以外はすべて問題ありません。さまざまなクエリがデータベースからすべてのデータを取得するのに 1 秒から 1 分かかります。この時間には、必要な (My)SQL サーバー側の計算が含まれます。これは単に容認できません。

データセット全体ではなく、一度に 1 つのポイントでデータが MySQL サーバーからクエリされる場合、個々のポイントを取得するのに約 1 ～ 100 ミリ秒しかかかりません。

データのフェッチ プロセスは、ブラウザ主導で行われる可能性があると思います。ユーザーがチャートを描画するためにボタンを押した後、コントローラーはデータベースに対して 1 つのリクエストを行い、たとえば進行状況バー (1% の準備ができているなど) をレンダリングします。ブラウザーが応答を受け取ると、すぐに (ajax) 要求を行い、サーバーは次のデータを取得して "2%" をレンダリングします。

以下同様に、すべてのデータの準備が整い、サーバーが要求されたグラフを表示するまで続けます。これは rails+js で実装できますか? Web で同様の問題を解決するためのチュートリアルはありますか? もしそれが実現可能であるなら、誰かがすでにこれをやったことがあるはずです。

私は ajax に関するいくつかの記事を読みました。一般的な原則は理解していると思いますが、重要な ajax プログラミングを自分で行ったことはありません。

御時間ありがとうございます！

更新：私はこの質問への回答を追加しました。これには、与えられたほとんどすべての提案が組み込まれています。以下のコードに示されている元のテンプレートは、実際の入力ドキュメント（スクリプトプログラミングに関する英語のテキスト）を完成させるために45605msを必要としました。コミュニティウィキの回答の改訂されたテンプレートにより、実行時間が605ミリ秒に短縮されました。

次のXSLTテンプレートを使用して、文字列内のいくつかの特殊文字をエスケープされたバリアントに置き換えています。分割統治法を使用して再帰的に呼び出し、最終的には特定の文字列内のすべての文字を調べます。次に、文字をそのまま印刷するかどうか、または何らかの形式のエスケープが必要かどうかを決定します。

このテンプレートは、XSLTスクリプトが必要とするランタイムの大部分を占めています。上記のescape-textテンプレートを

XSLTスクリプトの実行時間が、ドキュメントの1つで45秒から1秒未満になります。

したがって、私の質問：escape-textテンプレートを高速化するにはどうすればよいですか？私はxsltprocを使用しており、純粋なXSLT1.0ソリューションを好みます。XSLT2.0ソリューションも歓迎されます。ただし、外部ライブラリはこのプロジェクトには役立たない可能性があります。それでも、外部ライブラリを使用するソリューションには興味があります。

重複の可能性:
数値の配列で不足している数値を見つける最も簡単な方法

入力: ソートされていない配列 A[1,..,n] には、範囲 0、..、n の整数のうち 1 つを除くすべてが含まれます

問題は、不足している整数を O(n) 時間で決定することです。A の各要素は 2 進数で表され、利用可能な唯一の操作は関数 bit(i, j) です。これは、A[i] の j 番目のビットの値を返し、一定の時間がかかります。

何か案は？ある種の分割統治アルゴリズムが適切だと思いますが、正確に何をすべきかわかりません。前もって感謝します！

分割統治アルゴリズムを使用して、配列内のオブジェクトの少なくとも半分が (関数で) true を返すかどうかを確認するにはどうすればよいでしょうか? オブジェクトには列挙可能な値がないため、オブジェクト A は決してオブジェクト B より大きくはありません。

明確にするために、その関数を使用してすべてのオブジェクトを互いに比較します。したがって、 funct(Obj a, Obj b) は、いくつかの基準に基づいて true または false を返します。それらはひとまとめにすることができます。比較したオブジェクトの少なくとも半分が true を返したかどうかを知りたいだけです。

この問題は、私が取り組んで以来ずっと私を悩ませてきました。私は、特定の人々が彼らのペアに基づいて一緒に住んでいるかどうかを調べる方法を見つけようとしています。例、私はリストを与えられます：

このリストのすべての要素を比較して、少なくとも半分が同居しているかどうかを確認するためのD＆Cアルゴリズムが必要です。それらが一緒に住んでいるかどうかを調べるために、与えられた単純な関数があります：それらが一緒に住んでいるLivesTogether(x, y)場合はtrueを返し、そうでない場合はfalseを返します。

何か案は？

これは宿題の質問です。二分探索は既に導入されています。

昇順でそれぞれN要素とM要素の2 つの配列が与えられた場合、必ずしも一意であるとは限りません。両方の配列の和集合でk番目に小さい要素
を見つけるための時間効率の良いアルゴリズムは何ですか?

彼らは、それがO(logN + logM)どこNにありM、配列の長さであると言います。

a配列に とという名前を付けましょうb。明らかに、i > kのすべてa[i]と場所を無視できます。まずは と を比較して みましょう。>としましょう。したがって、 i > k/2のすべての を破棄することもできます。b[i]
a[k/2]b[k/2]b[k/2]a[k/2]b[i]

これa[i]で、 i < k の allb[i]と、 i < k/2 の all で答えが見つかりました。

次のステップは何ですか？