[解決済み] 山積みされた靴下を効率よく組み合わせるには？

質問

昨日、洗濯した靴下をペアリングしていたのですが、そのやり方があまり効率的でないことに気づきました。私は単純な探索を行っていました。つまり、1つの靴下を選び、そのペアを見つけるためにその山をquot;iterating"していたのです。これには、n/2 * n/4 = n個の靴下を繰り返し処理する必要があります。 ² /平均で8枚。

コンピュータサイエンティストとして、何かできないかと考えていました。もちろん、O(NlogN)ソリューションを達成するために、(サイズ/色/...に従って)ソートすることが頭に浮かびました。

ハッシュ化など、その場限りの解決策は、靴下を複製することができないので、選択肢には入っていません（できたらいいのですが）。

ということで、基本的には質問です。

の山があるとします。 n の靴下があり、その中に 2n 要素（各靴下にはちょうど1つの一致するペアがあると仮定します）を、対数倍までの余分なスペースで効率的にペアリングする最良の方法は何でしょうか？(必要ならその程度の情報は覚えていられると思います)。

次のような点に着目して回答していただけるとありがたいです。

• 一般的な 理論的 膨大な数の靴下に対応するソリューションです。
• 実際の靴下の数はそれほど多くなく、私と配偶者で30足以上あるとは思えません。(そして、私の靴下と彼女の靴下を区別するのはかなり簡単です。これも使えるでしょうか？)
• と同等なのでしょうか？ 要素の識別性問題 ?

解決方法は？

ソートソリューションが提案されているが ソートするのは少し無理がある : 秩序は必要ない 等しいグループだけが必要です .

そこで ハッシュ化 で十分です（しかも高速）。

1. 靴下の各色について 山を作る . 入力バスケットの中のすべての靴下を繰り返し処理する を作成し、色のついた杭に分配します。 .
2. 各パイルを繰り返し処理し 他の指標で分配する (パターンなど) を 2 番目のパイルのセットに入れる
3. このスキームを再帰的に適用する にすべてのソックスを分散させるまで 目視ですぐに処理できるような非常に小さな山

このような再帰的なハッシュ分割を実際に行っているのは SQLサーバー 巨大なデータセットに対してハッシュ結合やハッシュ集計を行う必要がある場合。これは、構築された入力ストリームを独立した多くのパーティションに分散させます。この方式は、任意のデータ量と複数のCPUにリニアに対応する。

という分散キー（ハッシュキー）が見つかれば、再帰的パーティショニングは必要ない。 十分なバケットを提供する 各バケツが十分に小さく、非常に高速に処理できること。残念ながら、靴下にそのような性質があるとは思えません。

もし各靴下に "PairID" という整数があれば、次のように10個のバケツに簡単に振り分けることができます。 PairID % 10 (下一桁)です。

現実的なパーティショニングとして考えられるのは、作成した 杭の長方形 一次元は色で、もう一次元はパターンです。なぜ長方形なのか？杭へのランダムアクセスがO(1)必要だからです。(3次元 キューボイド も有効ですが、あまり実用的ではありません)。

更新しました。

についてはどうでしょうか。 並列性 ? 複数の人間がより速く靴下を合わせることができるのか？

1. 最も単純な並列化戦略は、複数の作業者が入力バスケットから靴下を取り出し、杭の上に置くことである。100人が10個の靴下の山を取り合うとしたらどうでしょう。 同期化コスト (手と手のぶつかり合いや人間同士のコミュニケーションとして現れる）。 効率とスピードアップを破壊する (を参照）。 ユニバーサルスケーラビリティの法則 !). になりやすいのでしょうか？ デッドロック ? いいえ、各ワーカーは一度に一つの山にしかアクセスする必要がないからです。ロックは1つだけなので、デッドロックは起こりません。 ライブロック は、人間がどのように杭へのアクセスを調整するかによって可能かもしれません。ただ ランダムバックオフ ネットワークカードが物理的なレベルで、どのカードがネットワーク線に排他的にアクセスできるかを決定するように。もし、それが NIC 人間にも使えるはずです。
2. があれば、ほぼ無限に拡張できます。 各ワーカーは、独自の杭のセットを持つ . ワーカーは入力バスケットから大きな塊のソックスを取ることができ (滅多に行わないのでほとんど競合しません)、ソックスを分配する際に同期する必要は全くありません (スレッドローカルのパイルを持っているからです)。最後に、すべてのワーカーは自分のパイルセットを結合する必要があります。を形成していれば、O(log (worker count * piles per worker)) でできると思います。 集約ツリー .

はどうでしょうか？ 要素の区別の問題 ? 記事にあるように、要素の明瞭性問題は O(N) . これはソックスの問題でも同じです（同じく O(N) に分配するのであれば、1ステップで十分です（私が複数ステップを提案したのは、人間は計算が苦手だからです。 md5(color, length, pattern, ...) は、すなわち パーフェクトハッシュ の全属性))。

を超える速度は出せないことは明らかです。 O(N) に到達したわけです。 最適下限 .

出力は全く同じではありませんが（一方は単なるブール値、もう一方は靴下のペア）、漸近的な複雑さは同じです。