【問題描述】

昨天我在整理從洗衣店洗干凈的一堆襪子，發(fā)現(xiàn)我用的方法非常不高效。我用了一個最簡單的方法：拿到一只襪子，然后從頭到尾去找另外一只襪子。用這種方法需要重復(fù)平均超過 n/2*n/4=n2/8 雙襪子。

作為一個計算機(jī)科學(xué)家，我在想我應(yīng)該怎么做？我立馬就想到了根據(jù)尺寸顏色排序來得到一個復(fù)雜度為O(NlogN)的方法。

哈希或其他“非原地”的方法在這里不可取，因?yàn)槲也豢赡軓?fù)制襪子(要是可以的話就好了)。

因此，這個基本問題是：

給一堆襪子，總數(shù) n 雙，即包含 2n 只襪子(襪子是亂放的，即不是成對放的)，假設(shè)每只襪子都有一個確定的且能和它配對的襪子，問：如何用最快最有效的算法找出每只襪子與之配對的另一個襪子，并且最多使用對數(shù)級別的額外空間？

如果答案能夠考慮到下面的幾個方面，我會非常高興：(我希望答案能夠考慮到下面的幾個方面:)

1. 該算法要同樣適用于巨大數(shù)量的襪子。
2. 現(xiàn)實(shí)中襪子數(shù)量不會很多，我和我配偶的襪子加起來不超過30雙(我們倆的襪子非常容易區(qū)分，這可以被利用嗎？)
3. 該問題是否等同于元素唯一性問題（Element distinctness problem）？

【***答案】

上面提到的排序雖然可以考慮，但是有點(diǎn)浪費(fèi)。因?yàn)槲覀儾恍枰行颍覀儍H僅需要的是具有“相同”屬性的東西；

因此哈希算法就已經(jīng)足夠了，并且還很快。

1. 從另一個角度來看堆(一堆襪子)是由襪子的所有顏色形成的。所以遍歷輸入籃子中的所有襪子并，根據(jù)顏色再把他們放到不同的籃子。

2. 遍歷上述新形成的每個籃子，再根據(jù)其他的一些特性比如形狀將襪子放到第二個集合籃子中。

3. 遞歸地運(yùn)用上述方法，直到將所有襪子都放到一個非常小的籃子中，***你可以很容易的來處理。

SQL Server的實(shí)現(xiàn)就采用的是這種遞歸哈希劃分方法，當(dāng)它要進(jìn)行添加或者合并巨大集合的時候。它將輸入劃分成了多個集合，而且每個集合都是相互獨(dú)立的。這個方法對任意數(shù)據(jù)量和多核CPU都可以得到線性的復(fù)雜度。

如果你可以找到一個值，使得每個籃子內(nèi)的元素數(shù)量小到可以很輕松處理的程度，那么你就可以不用遞歸的劃分。不幸的是，我認(rèn)為襪子沒有這樣的一個屬性。

如果每個襪子都有一個整數(shù)形式的”PairID”，這樣就可以很容易依據(jù)哈希算法PairID%10，將所有襪子放到10個籃子中。

我認(rèn)為實(shí)際上最有效的劃分是：用一個長方形的盒子，長方形的一條邊代表顏色，另一條邊代表形狀。(譯者注：運(yùn)用一個二位數(shù)組，一維代表顏色，另一維代表形狀)。為什么是一個長方形的盒子？因?yàn)檫@樣我們可以只用O(1)的代價，就可以隨機(jī)訪問盒子中的元素。(三維的長方體也可以，但是不合實(shí)際)。

【答案更新】

考慮并行處理呢？如果有多個人來共同配對襪子，是否會快點(diǎn)呢？

1.有一個最簡單的并行策略，就是多個工人共同處理一籃子的襪子，將襪子配對。這只會加快一點(diǎn)點(diǎn)，假設(shè)有100個人處理10堆襪子。多人之間的同步成本(比如說手工碰撞和人類溝通)這樣會降低效率和速度(見Universal Scalability Law)。這樣會導(dǎo)致死鎖嗎？不會，因?yàn)槊恳粋€工人在一個時間只會訪問一個籃子。只需要一個鎖就可以防止死鎖。是否發(fā)生活鎖(Livelocks)則依賴于工人怎么合作去訪問籃子。他們可能使用類似網(wǎng)卡那樣的二進(jìn)制指數(shù)退避算法（random backoff ），在物理級別上決定哪些可以獨(dú)占的訪問網(wǎng)線。如果這個方法在網(wǎng)卡上有成效，那也同樣適用于那些工人。

2. 如果每個工人都有自己的一個籃子集合那這個規(guī)模就會接近無限大了。工人們可以從一個非常大的籃子中拿走襪子，并且在配對所有襪子時候不需要相互交流同步(因?yàn)榇藭r每個人都有自己獨(dú)有的籃子)。***再將每個工人所有的籃子合并在一起。我認(rèn)為如果所有工人能夠形成一個聚合樹，那么這個問題可以在復(fù)雜度O(logW*P) (W代表工人的數(shù)量，P是平均每個工人的堆數(shù)量)內(nèi)完成。

元素唯一性會如何呢？前文也提到了，元素唯一性可以在O(n)內(nèi)解決。如果你只需要一個分派步驟(我之前推薦分發(fā)多次，是因?yàn)槿擞嬎隳芰Σ粡?qiáng)的原因。如果你使用md5來進(jìn)行分發(fā)，一次就足夠了。因?yàn)閙d5可以把顏色、長度、圖案都考慮進(jìn)去，是一個包含所有屬性的***哈希)，襪子問題同樣也可以在O(n)內(nèi)處理完。

很明顯，所有算法最快也不可能超過O(n)，所以我們達(dá)到了***下界。

盡管輸出可能不完全相等(在一種情況下，只是一個布爾值。另一種情況，是一雙襪子)，但是漸進(jìn)復(fù)雜性確實(shí)相等的。

原文鏈接： stackoverflow   翻譯： 伯樂在線 - Jerry

譯文鏈接： http://blog.jobbole.com/66738/