積み重ねられた靴下を効率よく組み合わせるにはどうすればいいでしょうか? 質問する

ソートソリューションが提案されていますが、ソートは少々やりすぎです。順序は必要ありません。必要なのは等価グループだけです。

したがって、ハッシュ化で十分です (そして高速です)。

1. 靴下を色ごとに山に分けます。入力バスケット内のすべての靴下を反復処理し、色ごとの山に分配します。
2. 各山を反復処理し、他の基準（パターンなど）に従って2番目の山のセットに分配します。
3. このスキームを再帰的に適用して、すべての靴下を視覚的にすぐに処理できる非常に小さな山に分配します。

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

各バケットが非常に速く処理できるほど小さい、十分な数のバケットを提供する分散キー (ハッシュ キー) が見つかる場合は、再帰パーティショニングは必要ありません。残念ながら、ソックスにはそのような特性はないと思います。

各ソックスに「PairID」と呼ばれる整数があれば、PairID % 10（最後の桁）に応じて 10 個のバケットに簡単に分配できます。

私が思いつく最も現実的な分割方法は、長方形の山を作ることです。1つの次元は色で、もう1つの次元はパターンです。なぜ長方形なのでしょうか？それは、山へのランダムアクセスがO(1)必要だからです。(3D直方体も機能しますが、あまり実用的ではありません。

アップデート：

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

1. 最も単純な並列化戦略は、複数の作業員が投入バスケットから靴下を取り出して山に積むというものです。これは、100人が10個の山をめぐって争っているところを想像してみてください。同期コスト（手と人のコミュニケーションとして現れる）は、効率とスピードアップを損ないます（普遍的なスケーラビリティの法則！）。これはデッドロックになりやすいですか？いいえ、各作業員は一度に 1 つの山にアクセスするだけでよいからです。1 つの「ロック」だけではデッドロックは発生しません。人間が山へのアクセスを調整する方法によっては、ライブロックが発生する場合があります。ランダムバックオフネットワークカードは物理的なレベルでどのカードがネットワーク回線に排他的にアクセスできるかを決定します。NIC、それは人間にも効果があるはずです。
2. 各ワーカーが独自の山のセットを持っている場合、ほぼ無制限に拡張できます。ワーカーは入力バスケットから大量の靴下を取り出すことができ (めったに行われないため、競合はほとんどありません)、靴下を配布するときに同期する必要はまったくありません (スレッドローカルの山があるため)。最後に、すべてのワーカーが山のセットを結合する必要があります。ワーカーが集約ツリーを形成する場合、これは O(log (ワーカー数 * ワーカーあたりの山)) で実行できると思います。

どうですか要素の明確性の問題? 記事に述べられているように、要素の一意性問題は で解決できますO(N)。これは、靴下の問題 (また、必要な配布ステップが 1 つだけの場合 (人間は計算が苦手なので、複数のステップを提案しました。 、つまりすべての属性の完全なハッシュO(N)で配布する場合は 1 つのステップで十分です)) についても同様です。md5(color, length, pattern, ...)

明らかに、 より速く進むことはできないので、最適な下限 にO(N)到達しました。

出力はまったく同じではありませんが (1 つのケースでは単なるブール値、もう 1 つのケースでは靴下のペア)、漸近的な複雑さは同じです。