入職一周吭练，還算比較清閑竞帽。沒(méi)有一些明確時(shí)間點(diǎn)的事情椿息，所以目前的大部分時(shí)候悠反，探索成分居多嗤军，絞盡腦汁做的某些架構(gòu)設(shè)計(jì)注盈，不談結(jié)果，就過(guò)程而言叙赚，收獲頗豐老客。
總的來(lái)說(shuō)，蠻喜歡目前的狀態(tài)震叮，思考>編碼胧砰。
今天下午，旁邊的同事在做一個(gè)關(guān)于庫(kù)上的檢查苇瓣，簡(jiǎn)單說(shuō)就是判斷數(shù)據(jù)庫(kù)的某些字段是否唯一尉间。
最開(kāi)始是一條sql語(yǔ)句，大概是這樣的：
select * from aaa group by aaa.bbb, aaa.ccc having count(*) > 1;
全表大概1000w的數(shù)據(jù)击罪，第一次執(zhí)行哲嘲，用了16分鐘。
我們的mysql是架在一臺(tái)12核媳禁，128Gb內(nèi)存的機(jī)器上眠副，應(yīng)該說(shuō)資源是足夠的，但是這樣的執(zhí)行時(shí)間竣稽，相比于oracle的2分鐘左右的處理速度囱怕，還是慢了太多。
單純select *大概在1分鐘左右毫别，所以大部分的開(kāi)銷在group by上娃弓，從這點(diǎn)上看，mysql的一些計(jì)算能力確實(shí)欠缺太多岛宦。
后來(lái)考慮優(yōu)化忘闻，將select *的結(jié)果全部裝入內(nèi)存，然后進(jìn)行查找恋博。
思路上齐佳，沒(méi)有任何問(wèn)題私恬，但他的實(shí)施是這樣的：
判斷重復(fù)時(shí)，使用了2個(gè)循環(huán)炼吴，如下：
vector<string> data;
for (int i = 0; i < data.size(); i++)
{
for (int j = i + 1; j < data.size(); j++)
{
if (data[i] == data[j])
{
//do some
}
}
}
這個(gè)代碼執(zhí)行了大概30分鐘本鸣，仍然沒(méi)有結(jié)果。
正好當(dāng)時(shí)沒(méi)事硅蹦，就幫他做了一些優(yōu)化荣德。很顯然，這樣的一個(gè)唯一性檢查使用窮舉是有問(wèn)題的童芹，復(fù)雜度在O(N^2)涮瞻，對(duì)于1000w這樣的數(shù)量級(jí)，O(N^2)基本上是不可實(shí)現(xiàn)的假褪。所以第一步的優(yōu)化署咽，就是將這個(gè)算法的復(fù)雜度降下來(lái)。
增加一個(gè)排序操作生音，這樣宁否，程序的處理流程將變?yōu)椋?br>
1 排序
2 兩兩比較，確定非唯一值
總體的復(fù)雜度為O(N logN)
在排序中缀遍，使用了stl的sort函數(shù)進(jìn)行排序慕匠，程序整體執(zhí)行一遍的時(shí)間為7分鐘。刨掉出庫(kù)select的1分鐘域醇，排序的時(shí)間在6分鐘左右台谊。這么說(shuō)來(lái)，還是有些慢譬挚。這個(gè)時(shí)候青伤，更好的優(yōu)化方式是將算法更改為hash，這樣時(shí)間復(fù)雜度將降為O(N)殴瘦，那么將會(huì)有質(zhì)的提升狠角，但是考慮到stl的map是紅黑樹(shù)實(shí)現(xiàn)，復(fù)雜度為O(N logN)蚪腋，并不是很好的選擇丰歌，而自己重新寫(xiě)一個(gè)hash函數(shù)好像又比較麻煩。所以權(quán)衡了一下屉凯，還是繼續(xù)從排序入手立帖。
最開(kāi)始，想要將排序操作轉(zhuǎn)移到mysql上執(zhí)行悠砚，也就是在出庫(kù)的同時(shí)進(jìn)行排序晓勇，需要把出庫(kù)語(yǔ)句改為：
select * from aaa order by aaa.bbb, aaa.ccc;
這樣之后，內(nèi)存中只需要一次遍歷就好，時(shí)間開(kāi)銷基本可以忽略绑咱，這條sql的執(zhí)行時(shí)間為4分鐘绰筛，雖然相比于前面有了一些提升，但還是不夠理想描融，還需要進(jìn)一步的優(yōu)化铝噩。
在上文的程序中，我們發(fā)現(xiàn)全部的數(shù)據(jù)存儲(chǔ)在一個(gè)vector里窿克，每一條數(shù)據(jù)為一個(gè)string骏庸，因此核心的開(kāi)銷為string的operator < 比較操作。string是一個(gè)相對(duì)來(lái)說(shuō)比較龐大的類年叮，會(huì)造成許多的額外開(kāi)銷具被。
我們只需要比較2個(gè)字段的唯一性，完全可以將這兩個(gè)字段拼接起來(lái)只损，存在一個(gè)char*中一姿，之后的比較基于memcmp。
當(dāng)然改执，可能有這樣的問(wèn)題啸蜜，第一條記錄的第一個(gè)字段為“123”坑雅，第二個(gè)字段為“456”辈挂；而第二條記錄的第一個(gè)字段為“12”，第二個(gè)字段為“3456”裹粤，這樣本來(lái)不等的兩個(gè)字段终蒂，拼接后相同。解決方式也很簡(jiǎn)單遥诉，在“123”的結(jié)束位置加入一個(gè)特殊字符拇泣，再拼接，這樣就可以了矮锈。
在更改為char*之后霉翔，數(shù)據(jù)的排序時(shí)間從原來(lái)的3分鐘降到了40秒。
目前來(lái)看苞笨，總體的執(zhí)行時(shí)間為1分鐘40秒债朵，其中出庫(kù)1分鐘，排序40秒瀑凝。系統(tǒng)的整體瓶頸轉(zhuǎn)移到了出庫(kù)這里序芦，這里的優(yōu)化方式就相當(dāng)明顯了，我們只是用到了2個(gè)字段粤咪，完全沒(méi)有必要select *谚中，只需要將select語(yǔ)句改為：
select aaa.bbb, aaa.ccc from aaa;
這樣更改后，出庫(kù)的時(shí)間為13秒，整體的執(zhí)行時(shí)間為50秒宪塔。
這個(gè)時(shí)間磁奖，已經(jīng)完全符合要求了，但是為了追求更高的速度蝌麸，繼續(xù)將計(jì)算并行化点寥，也就是說(shuō)，充分利用cpu的多核計(jì)算能力来吩，將任務(wù)盡可能的拆分為多個(gè)線程來(lái)完成敢辩。對(duì)于本例來(lái)說(shuō)，我們并不需要整體有序的數(shù)據(jù)弟疆，因此戚长，考慮hadoop的分桶思想，我們將取出的char*每位相加怠苔，得到的結(jié)果對(duì)10取余同廉，將結(jié)果分散到10個(gè)線程去做，最后的執(zhí)行結(jié)果為4秒鐘柑司。
經(jīng)過(guò)上面的一步步優(yōu)化迫肖，總共的執(zhí)行時(shí)間為17秒。
(原文時(shí)間2014-1-15)
