有一堆襪子，如何用最快速高效的算法來給襪子配對？
【問題描述】
昨天我在整理從洗衣店洗干凈的一堆襪子，發現我用的方法非常不高效。我用了一個最簡單的方法：拿到一只襪子，然后從頭到尾去找另外一只襪子。用這種方法需要重復平均超過 n/2*n/4=n2/8 雙襪子。
作為一個計算機科學家，我在想我應該怎么做？我立馬就想到了根據尺寸顏色排序來得到一個復雜度為O(NlogN)的方法。
哈希或其他“非原地”的方法在這里不可取，因為我不可能復制襪子(要是可以的話就好了)。
因此，這個基本問題是：
給一堆襪子，總數 n 雙，即包含 2n 只襪子(襪子是亂放的，即不是成對放的)，假設每只襪子都有一個確定的且能和它配對的襪子，問：如何用最快最有效的算法找出每只襪子與之配對的另一個襪子，并且最多使用對數級別的額外空間？
如果答案能夠考慮到下面的幾個方面，我會非常高興：(我希望答案能夠考慮到下面的幾個方面:)
- 該算法要同樣適用于巨大數量的襪子。
- 現實中襪子數量不會很多，我和我配偶的襪子加起來不超過30雙(我們倆的襪子非常容易區分，這可以被利用嗎？)
- 該問題是否等同于元素唯一性問題（Element distinctness problem）？
【***答案】
上面提到的排序雖然可以考慮，但是有點浪費。因為我們不需要有序，我們僅僅需要的是具有“相同”屬性的東西；
因此哈希算法就已經足夠了，并且還很快。
1. 從另一個角度來看堆(一堆襪子)是由襪子的所有顏色形成的。所以遍歷輸入籃子中的所有襪子并，根據顏色再把他們放到不同的籃子。
2. 遍歷上述新形成的每個籃子，再根據其他的一些特性比如形狀將襪子放到第二個集合籃子中。
3. 遞歸地運用上述方法，直到將所有襪子都放到一個非常小的籃子中，***你可以很容易的來處理。
SQL Server的實現就采用的是這種遞歸哈希劃分方法，當它要進行添加或者合并巨大集合的時候。它將輸入劃分成了多個集合，而且每個集合都是相互獨立的。這個方法對任意數據量和多核CPU都可以得到線性的復雜度。
如果你可以找到一個值，使得每個籃子內的元素數量小到可以很輕松處理的程度，那么你就可以不用遞歸的劃分。不幸的是，我認為襪子沒有這樣的一個屬性。
如果每個襪子都有一個整數形式的”PairID”，這樣就可以很容易依據哈希算法PairID%10，將所有襪子放到10個籃子中。
我認為實際上最有效的劃分是：用一個長方形的盒子，長方形的一條邊代表顏色，另一條邊代表形狀。(譯者注：運用一個二位數組，一維代表顏色，另一維代表形狀)。為什么是一個長方形的盒子？因為這樣我們可以只用O(1)的代價，就可以隨機訪問盒子中的元素。(三維的長方體也可以，但是不合實際)。
【答案更新】
考慮并行處理呢？如果有多個人來共同配對襪子，是否會快點呢？
1.有一個最簡單的并行策略，就是多個工人共同處理一籃子的襪子，將襪子配對。這只會加快一點點，假設有100個人處理10堆襪子。多人之間的同步成本(比如說手工碰撞和人類溝通)這樣會降低效率和速度(見Universal Scalability Law)。這樣會導致死鎖嗎？不會，因為每一個工人在一個時間只會訪問一個籃子。只需要一個鎖就可以防止死鎖。是否發生活鎖(Livelocks)則依賴于工人怎么合作去訪問籃子。他們可能使用類似網卡那樣的二進制指數退避算法（random backoff ），在物理級別上決定哪些可以獨占的訪問網線。如果這個方法在網卡上有成效，那也同樣適用于那些工人。
2. 如果每個工人都有自己的一個籃子集合那這個規模就會接近無限大了。工人們可以從一個非常大的籃子中拿走襪子，并且在配對所有襪子時候不需要相互交流同步(因為此時每個人都有自己獨有的籃子)。***再將每個工人所有的籃子合并在一起。我認為如果所有工人能夠形成一個聚合樹，那么這個問題可以在復雜度O(logW*P) (W代表工人的數量，P是平均每個工人的堆數量)內完成。
元素唯一性會如何呢？前文也提到了，元素唯一性可以在O(n)內解決。如果你只需要一個分派步驟(我之前推薦分發多次，是因為人計算能力不強的原因。如果你使用md5來進行分發，一次就足夠了。因為md5可以把顏色、長度、圖案都考慮進去，是一個包含所有屬性的***哈希)，襪子問題同樣也可以在O(n)內處理完。
很明顯，所有算法最快也不可能超過O(n)，所以我們達到了***下界。
盡管輸出可能不完全相等(在一種情況下，只是一個布爾值。另一種情況，是一雙襪子)，但是漸進復雜性確實相等的。
原文鏈接： stackoverflow 翻譯： 伯樂在線 - Jerry
