【問(wèn)題描述】

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

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

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

因此，這個(gè)基本問(wèn)題是：

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

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

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

【***答案】

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

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

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

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

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

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

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

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

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

【答案更新】

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

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

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

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

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

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

原文鏈接： stackoverflow   翻譯： 伯樂(lè)在線 - Jerry

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