靴下が山積みになっています。靴下をペアにするには、最も速くて効率的なアルゴリズムをどのように使用すればよいでしょうか?

[問題の説明]

昨日、コインランドリーで靴下の山を整理していたのですが、自分が使っていた方法がとても非効率的だということに気づきました。私は最も簡単な方法を使いました。靴下を 1 枚取り、もう一方の靴下を最初から最後まで探します。この方法では、n/2*n/4=n2/8 足以上の靴下の平均を繰り返す必要があります。

コンピューター科学者として、私は何をすべきか考えていました。私はすぐに、サイズと色でソートして、O(NlogN) の複雑さの方法を得ることを思いつきました。

ハッシュ化やその他の「場違いな」方法は、ここでは選択肢ではありません。なぜなら、ソックスをコピーすることはできないからです (できれば良いのですが)。

基本的な質問は次のとおりです。

n 組の靴下、つまり 2n 組の靴下 (靴下はランダムに配置され、ペアになっていません) が山積みになっているとします。各靴下には、それとペアになる靴下が 1 つあると仮定すると、問題は、各靴下とペアになる別の靴下を見つけるための最速かつ最も効率的なアルゴリズムを使用し、最大でも対数の追加スペースを使用するにはどうすればよいか、ということです。

回答では以下の点を考慮に入れていただければ幸いです。（回答では以下の点を考慮に入れていただければ幸いです。）

1. このアルゴリズムは、大量の靴下にも機能するはずです。
2. 実際には、靴下はそれほど多くありません。私と配偶者を合わせても、靴下は 30 足以上は持っていません (私たちの靴下は非常に見分けやすいので、これを悪用することはできますか?)
3. この問題は要素の明確性の問題と同等でしょうか?

【***答え】

上記のソートは考えられますが、少し無駄があります。なぜなら、順序は必要なく、物事が「同じ」特性を持つことだけが必要なからです。

したがって、ハッシュ アルゴリズムは十分かつ高速です。

1. 別の視点から見ると、靴下のすべての色によって山（靴下の束）が形成されます。したがって、入力バスケット内のすべての靴下を反復処理し、色に応じて異なるバスケットに入れます。

2. 上記の新しく形成された各バスケットを横断し、形状などの他の特性に基づいて靴下を 2 番目の収集バスケットに入れます。

3. 上記の方法を繰り返し適用して、すべての靴下が簡単に扱える非常に小さなバスケットに収まるようにします。

SQL Serverの実装では、大規模なコレクションを追加またはマージするときに、この再帰ハッシュ アプローチが使用されます。入力を複数のセットに分割し、各セットは互いに独立しています。この方法は、あらゆる量のデータとマルチコア CPU に対して線形複雑度を実現できます。

各バスケット内の要素数が簡単に処理できるほど小さくなる値を見つけることができれば、再帰的な分割を回避できます。残念ながら、靴下にはそのような性質はないと思います。

各靴下に整数の「PairID」が付いている場合は、ハッシュ アルゴリズム PairID%10 を使用して、すべての靴下を 10 個のバスケットに入れるのは簡単です。

最も効果的な分割方法は、片側が色を表し、もう片側が形状を表す長方形のボックスを使用することだと私は思います。 (翻訳者注: 2 次元配列を使用します。1 つの次元は色を表し、もう 1 つの次元は形状を表します)。なぜ長方形の箱なのでしょうか?この方法では、O(1) のコストだけでボックス内の要素にランダムにアクセスできるからです。 （3次元の直方体も可能ですが、実用的ではありません）。

【回答更新】

並列処理はどうですか?複数人で靴下を合わせたらもっと早くなりますか？

1. 最も単純な並列戦略は、複数の作業者が協力して靴下のバスケットを処理し、それらをペアにすることです。 100 人の人が 10 個の靴下山を処理すると仮定すると、これによって処理速度がほんの少しだけ上がります。複数の人の間での同期コスト (手動衝突や人間によるコミュニケーションなど) により、効率と速度が低下します (ユニバーサル スケーラビリティの法則を参照)。これはデッドロックを引き起こしますか?いいえ。各作業者は一度に 1 つのバスケットにしかアクセスできないためです。デッドロックを防ぐために必要なロックは 1 つだけです。ライブロックが発生するかどうかは、働きアリがバスケットにアクセスするためにどのように協力するかによって決まります。おそらく、ネットワーク カードが行うのと同様のバイナリ指数バックオフ アルゴリズム (ランダム バックオフ) を使用して、物理レベルでどのカードがネットワーク ケーブルに排他的にアクセスできるかを決定します。このアプローチがネットワーク カードで機能する場合は、ワーカーでも機能します。

2. 各作業者が独自のバスケット セットを持っている場合、そのサイズは無限大に近くなります。作業員は非常に大きなバスケットから靴下を取り出すことができ、すべての靴下をペアにするときに同期するために互いに通信する必要がありません (この時点では全員が独自のバスケットを持っているため)。 ***次に、各ワーカーのバスケットをすべて結合します。すべてのワーカーが集約ツリーを形成できる場合、この問題は複雑度 O(logW*P) で解決できると思います (W はワーカー数、P はワーカーあたりのヒープの平均数を表します)。

要素の一意性はどうでしょうか?前述のように、要素の一意性は O(n) 内で解決できます。配布ステップが 1 つだけ必要な場合 (人間の計算能力には限界があるため、以前は複数回の配布を推奨していました。配布に md5 を使用する場合は、1 回で十分です。md5 は色、長さ、パターンを考慮できるため、すべての属性を含む *** ハッシュです)、sock 問題も O(n) 内で処理できます。

明らかに、最速のアルゴリズムは O(n) を超えることはできないため、最低の下限に達しました。

出力は正確には等しくないかもしれませんが (1 つのケースでは単なるブール値、もう 1 つのケースでは靴下 1 足)、漸近的な複雑さは確かに等しくなります。

オリジナルリンク: stackoverflow翻訳: Bole Online - Jerry

翻訳リンク: http://blog.jobbole.com/66738/