問題タブ [algorithm]

以下で説明するタスクを達成するために、最適な時間効率の良いアルゴリズムを決定しようとしています。

私はレコードのセットを持っています。このレコードのセットには、このセットのレコードのペアが互いにどのように接続するかを示す接続データがあります。これは基本的に無向グラフを表し、レコードが頂点、接続データがエッジになります。

セット内のすべてのレコードには接続情報があります (つまり、孤立したレコードは存在しません。セット内の各レコードは、セット内の 1 つ以上の他のレコードに接続されます)。

セットから任意の 2 つのレコードを選択し、選択したレコード間の単純なパスをすべて表示できるようにしたいと考えています。「単純なパス」とは、パスに繰り返しレコードがないパス (つまり、有限パスのみ) を意味します。

注: 選択された 2 つのレコードは常に異なります (つまり、開始頂点と終了頂点が同じになることはありません。サイクルはありません)。

例えば：

開始レコードとして B を選択し、終了レコードとして E を選択した場合、レコード B をレコード E に接続するレコード接続を通るすべての単純なパスを見つけたいと思うでしょう。

これは一例です。実際には、数十万のレコードを含むセットがある場合があります。

候補者のスクリーニング プロセスで効果的だと思われる単純なアルゴリズムまたはデータ構造関連の「ホワイト ボード」の問題は何ですか?

問題解決スキルを検証するために使用する単純なものがいくつかあります。これらは簡単に表現できますが、いくつかのヒューリスティックを適用する機会があります。

私がジュニア開発者に使用する基本の 1 つは、次のとおりです。

一連の単語 (文) を含む文字列を受け取り、それらの単語を X 桁右に回転させる C# メソッドを作成します。文の最後の位置にある単語が回転されると、結果の文字列の先頭に表示されるはずです。

候補者がこの質問に答えるとき、問題を解決するために利用できる .NET データ構造とメソッド (string.Join、string.Split、List など) を確認します。また、最適化の特殊なケースを特定するためにそれらを探します。単語をローテーションする必要がある回数は、実際には X ではなく、単語の X % の数です。

候補者との面接に使用するホワイト ボードの問題と、回答に求めるものは何ですか (実際の回答を投稿する必要はありません)。

私はしばらくの間、文字列の配列を結合するためのすてきでクリーンなソリューションがどのように見えるか疑問に思っていました。例: ["Alpha", "Beta", "Gamma"] があり、コンマで区切られた文字列を 1 つに結合したい – "Alpha, Beta, Gamma".

これで、ほとんどのプログラミング言語が何らかの結合メソッドを提供することがわかりました。これらがどのように実装されるのか疑問に思っています。入門コースを受講したとき、私はしばしば一人で行こうとしましたが、満足のいくアルゴリズムを見つけることができませんでした. 問題は、配列をループして文字列を連結することはできず、(最後の文字列の前または後に) コンマを 1 つ追加しすぎるためです。ループ内の条件をチェックしたくありません。ループの前後に最初または最後の文字列を追加したくありません (これが最善の方法だと思いますか?)。

誰かが私にエレガントなソリューションを見せてもらえますか? それとも、もっとエレガントなものがない理由を正確に教えてください。

小数点以下 8 桁までの可能性のある数値の配列があり、すべての整数になるように乗算できる最小の共通数値を見つける必要があります。これが必要なのは、元のすべての数値をすべて同じスケールに乗算し、整数のみを処理する密閉されたシステムで処理できるようにするためです。その後、結果を取得し、それらを共通の乗数で割って相対的な結果を得ることができます。 .

現在、数値をいくつかチェックして 100 倍または 1,000,000 倍していますが、*sealed システムによって行われる処理は、大きな数値を処理する場合に非常にコストがかかる可能性があるため、目的のためにすべてを 100 万倍にすることはあまり意味がありません。素晴らしいオプションです。概算として、封印されたアルゴリズムは、10 倍するたびに 10 倍のコストがかかると言えます。

私が必要とするものを達成するために、可能な限り最良の結果をもたらす最も効率的なアルゴリズムは何ですか?また、必要なものの数学的な名前や式はありますか?

*封印されたシステムは、実際には封印されていません。私はそのソースコードを所有/維持していますが、その100,000行の独自の魔法であり、バグとパフォーマンスが徹底的にテストされており、フロートを処理するように変更することは多くの理由でオプションではありません. それは、X x Y セルのグリッドを作成し、X x Y の四角形をグリッドにドロップし、「独自の魔法」が発生して結果を吐き出すシステムです。十分な近似です。

これまでのところ、いくつかの良い答えが静かにあり、「正しい」答えをどのように選択すればよいか疑問に思いました. 最初は、各ソリューションを作成してパフォーマンスをテストすることが唯一の公正な方法だと考えていましたが、純粋な速度だけが関連する要因ではなく、より正確なソリューションも非常に重要であることに後で気付きました。とにかくパフォーマンステストを書きましたが、現在、「直感」式を使用して、速度と精度に基づいて正しい答えを選択しています。

私のパフォーマンス テストでは、ランダムに生成された 100 の数値の 1000 の異なるセットを処理します。各アルゴリズムは、同じ乱数セットを使用してテストされます。アルゴリズムは .Net 3.5 で記述されています (ただし、これまでのところ 2.0 と互換性があります)。テストをできるだけ公正にするために、かなりの努力をしました。

• Greg – 大きな数を掛けてから GCD で割る – 63 ミリ秒
• Andy – 文字列解析 – 199 ミリ秒
• Eric – Decimal.GetBits – 160 ミリ秒
• Eric – 二分探索 – 32 ミリ秒
• Ima – 申し訳ありませんが、ソリューションを .Net で簡単に実装する方法がわかりませんでした (あまり時間をかけたくありませんでした)。
• Bill – あなたの答えは Greg の答えにかなり近かったので、実装しませんでした。わずかに高速になると確信していますが、精度が低下する可能性があります。

したがって、Greg の「多数を掛けてから GCD で割る」ソリューションは、2 番目に高速なアルゴリズムであり、最も正確な結果が得られたので、今のところ正しいと呼んでいます。

私は本当に Decimal.GetBits ソリューションを最速にしたかったのですが、非常に遅かったです。BitConverter.GetBytes とここに含まれるいくつかの知識を使用して、ストレート Double の同様の使用可能なソリューションがあるはずです: http://blogs.msdn.com/bclteam/archive/2007/05/29/bcl-refresher-floating-point- types-the-good-the-bad-and-the-ugly-inbar-gazit-matthew-greig.aspx ですが、その記事を読むたびに目が眩み、最終的に実装を試みる時間がなくなりました。解決。

誰かがより良いものを考えることができれば、私は常に他の解決策を受け入れます.

任意の値を含む一連のポリゴンを取得し、各ピクセルがその位置のポリゴンの値を含む対応するビットマップを作成するにはどうすればよいですか?

質問を文脈に入れるために、私のポリゴンには、ポリゴン内の 1 平方キロメートルあたりの平均人数に関する情報が含まれています。200 メートルのビンで人口を表すピクセルを含むラスター/ビットマップを作成する必要があります。

私は過去に、ビットマップに描画して値を入力し、ビットマップを操作可能な配列に変換することで、ポリゴンを使用してマスクを作成するという同様のことを行いました。これを行うためのより良い方法があると確信しています！

リクエストに応じて、質問をもう少し明確にしています。

1. 複数のポリゴンがあり、各ポリゴンはベクトルのセットです
2. 各ポリゴンには単一の一意の値があります
3. ポリゴンが重ならない

ありがとう

ニック

同期アルゴリズムの参考文献はありますか?

複数のユーザー間で次の種類のデータを同期するアルゴリズムに興味があります。

• カレンダー
• ドキュメント
• リストとアウトライン

rsyncでのディレクトリの 内容の同期を探しているだけではありません。個々のファイル内のデータをマージすることに興味があります。

入力: フレーズ 1、フレーズ 2

出力: 意味的類似度値 (0 と 1 の間)、またはこれら 2 つのフレーズが同じことについて話している確率

私は、GPS によって記録された多くのトラックを持っています。これは、より正式には、多数のライン ストリングとして説明できます。

ここで、記録されたトラックのいくつかは同じルートの記録である可能性がありますが、GPS システムの不正確さのため、記録が別の機会に行われ、異なる速度で移動して記録された可能性があるという事実は、完全に一致しますが、人間が地図上で見ると、実際に記録されたのと同じルートであると判断するのに十分なほど近くに見えます.

2 つの折れ線の類似度を計算するアルゴリズムを見つけたいです。これを行うための自家製の方法をいくつか考え出しましたが、これが問題を解決するための優れたアルゴリズムを既に持っている問題であるかどうかを知りたいです。

類似の平均が地図上の同じ経路を表すとすれば、類似度をどのように計算しますか?

編集:私が何について話しているのかわからない場合は、次のリンクを参照して、線の文字列とは何かを定義してください: http://msdn.microsoft.com/en-us/library/bb895372.aspx - I'文字列については質問しません。

最近、Java アプリで作業しているときに、コンマ区切りの値のリストを組み立てて別の Web サービスに渡す必要がありましたが、事前に要素がいくつあるかわからなかったのです。頭のてっぺんから思いついたのは、次のようなものでした。

いたるところに文字列が作成されているため、これは特に効率的ではありませんが、最適化よりも明確にするつもりでした。

Ruby では、代わりに次のようなことができます。これははるかにエレガントに感じます。

しかし、Java には結合コマンドがないため、これに相当するものを見つけることができませんでした。

では、Java でこれを行う最善の方法は何でしょうか?

渡された量が一連の数値から加算的に構築できるかどうかを決定するための非再帰的アルゴリズムとは何ですか。
私の場合、一連の請求書（$ 5、$ 10、$ 20の請求書など）の組み合わせを合計することで、特定の通貨額（$ 40など）を満たすことができるかどうかを判断しています。これは単純な例ですが、アルゴリズムはどの通貨セットでも機能する必要があります（一部の通貨はファンキーな請求額を使用し、一部の請求は特定の時間に利用できない場合があります）。
したがって、$ 50は（$20と$30）のセットで満たすことができますが、（$20と$40）のセットで満たすことはできません。非再帰的要件はSQL Server 2000、再帰のサポートが制限されているターゲットコードベースによるものです。
さらに、これは、利用可能な請求書のセットが変更される可能性がある多通貨環境をサポートするためのものです（たとえば、外国為替窓口係を考えてみてください）。