問(wèn)題描述

國(guó)家天文臺(tái)有個(gè)聚類(lèi)任務(wù)：共 11 份數(shù)據(jù)，每份數(shù)據(jù)是從一張照片中提取出來(lái)的，包含 500 多萬(wàn)條記錄，每條記錄是一個(gè)天體的坐標(biāo)及屬性。11 張“照片”中有些天體坐標(biāo)是重復(fù)的，但這些重復(fù)的坐標(biāo)不完全相同，他們會(huì)有一些差別但距離不會(huì)太遠(yuǎn)。任務(wù)就是把其中一張“照片”作為基礎(chǔ)，從其他照片中找出重復(fù)的天體，把重復(fù)天體的坐標(biāo)及屬性均值作為該天體的最終坐標(biāo)和屬性，即把距離很近的天體聚成一類(lèi)再做聚合運(yùn)算，這樣就可以得到一張坐標(biāo)清晰且信息更加準(zhǔn)確的天體“照片”。

問(wèn)題分析

這個(gè)任務(wù)不算復(fù)雜，只要循環(huán)基礎(chǔ)照片中的每一個(gè)天體坐標(biāo)，將其與其他照片中的每個(gè)天體坐標(biāo)計(jì)算距離，不超過(guò)某個(gè)閾值就認(rèn)為是同一個(gè)天體，視作一類(lèi)，最后將每一類(lèi)中所有天體坐標(biāo)求均值就得到了該天體的坐標(biāo)。

但是當(dāng)用計(jì)算機(jī)計(jì)算時(shí)就發(fā)現(xiàn)這個(gè)任務(wù)的計(jì)算量是驚人的，基礎(chǔ)照片需要循環(huán) 500 多萬(wàn)次，其中的每個(gè)天體坐標(biāo)又要與其他照片中的 5000 多萬(wàn)個(gè)坐標(biāo)計(jì)算距離，計(jì)算復(fù)雜度是 500 多萬(wàn) *5000 多萬(wàn)，這將是個(gè)天文數(shù)字。

事實(shí)也確實(shí)如此，在實(shí)驗(yàn)階段，把每張照片的數(shù)據(jù)量減小 10 倍，即每張照片的天體坐標(biāo)量為 50 萬(wàn)，用 Python 寫(xiě)出代碼實(shí)現(xiàn)上述方法計(jì)算出 11 張照片的聚類(lèi)結(jié)果需要的時(shí)間是 6.5 天。按計(jì)算復(fù)雜度來(lái)算，500 多萬(wàn)的數(shù)據(jù)量，計(jì)算量是 50 萬(wàn)數(shù)據(jù)量的 100 倍，即需要耗時(shí) 650 天，這肯定是一個(gè)無(wú)法接受的數(shù)字。

同樣的 50 萬(wàn)數(shù)據(jù)量，被裝入了某分布式數(shù)據(jù)庫(kù)后用 SQL 實(shí)現(xiàn)，動(dòng)用了 100 顆 CPU 后，跑了 3.8 小時(shí)完成了計(jì)算?？雌饋?lái)比 Python 快了很多倍，但 Python 的 6.5 天是單線程，細(xì)算下來(lái) SQL 的單核性能還不如 Python（3.8 小時(shí) *100>6.5 天）。巨大的資源消耗已經(jīng)難以容忍，而且計(jì)算 500 多萬(wàn)規(guī)模時(shí)也要 380 小時(shí)。

解決方案

我們來(lái)考慮哪里可以優(yōu)化以減少計(jì)算量。

基礎(chǔ)照片中的天體坐標(biāo)是必須循環(huán)的，這樣才能保證每個(gè)天體都被用來(lái)聚類(lèi)了，其他照片中的天體坐標(biāo)不用每次都遍歷，只要找到基礎(chǔ)天體坐標(biāo)附近的坐標(biāo)就可以了。這類(lèi)查找任務(wù)很適合二分法，它可以大量減少計(jì)算量。

具體過(guò)程是這樣的：先對(duì)每張照片中的天體坐標(biāo)排序，用二分法找到某個(gè)閾值范圍內(nèi)的天體坐標(biāo)，這樣就排除了大多數(shù)天體，這是粗篩過(guò)程；用基礎(chǔ)天體與粗篩結(jié)果中的天體計(jì)算距離，找出符合條件的結(jié)果，這是細(xì)篩過(guò)程。

來(lái)看看粗篩加細(xì)篩方法的計(jì)算量，10 張照片每張排序一次，計(jì)算量是 500 萬(wàn) *log(500 萬(wàn))*10；二分法粗篩，計(jì)算量是 500 萬(wàn) *log(500 萬(wàn))*10；細(xì)篩過(guò)程，計(jì)算量不確定，但根據(jù)經(jīng)驗(yàn)，粗篩后的結(jié)果通常不超過(guò) 1 萬(wàn)個(gè)，粗篩的計(jì)算量中 log(500 萬(wàn)) 還要再加 1 萬(wàn)；這樣算下來(lái)，總的計(jì)算量大概是 500 萬(wàn) *log(500 萬(wàn))*10+500 萬(wàn) *(log(500 萬(wàn))+1 萬(wàn) )*10，相較于原來(lái)的方法，計(jì)算量只有原來(lái)的五百分之一。

技術(shù)選型

方法有了，還要選擇程序工具，之前實(shí)現(xiàn)時(shí)使用 Python，不可否認(rèn) Python 很強(qiáng)大，有天文學(xué)計(jì)算的現(xiàn)成框架，比如計(jì)算距離的方法，只要調(diào)用現(xiàn)成的類(lèi)庫(kù)就可以輕松算出來(lái)。

但 Python 也有著非常嚴(yán)重的弊端：

關(guān)系數(shù)據(jù)庫(kù)的 SQL 也無(wú)法高效完成。這個(gè)聚類(lèi)運(yùn)算本質(zhì)上是個(gè)非等值連接，數(shù)據(jù)庫(kù)對(duì)于等值連接還能采用 HASH JOIN 等優(yōu)化方案來(lái)減少計(jì)算量，但對(duì)于非等值連接就只能采用遍歷方案了；SQL 也無(wú)法在語(yǔ)句中實(shí)現(xiàn)上面設(shè)計(jì)的復(fù)雜過(guò)程，不能識(shí)別距離的單調(diào)性而主動(dòng)排序并采用二分法；再加上本來(lái)做這類(lèi)數(shù)學(xué)類(lèi)計(jì)算的能力不足（距離計(jì)算涉及三角函數(shù)）；所以發(fā)生了前面實(shí)驗(yàn)階段中 SQL 的單核性能還跑不過(guò) Python 的現(xiàn)象。

Java等高級(jí)語(yǔ)言雖然可以實(shí)現(xiàn)二分法，也可以很好的并行，但代碼寫(xiě)起來(lái)冗長(zhǎng)，開(kāi)發(fā)效率過(guò)低，會(huì)嚴(yán)重影響程序的可維護(hù)性。

那么，還能用什么工具來(lái)完成這個(gè)任務(wù)呢？

集算器 SPL 是個(gè)很好的選擇，它內(nèi)置了很多高性能算法（如二分法），也支持多線程并行，代碼寫(xiě)起來(lái)也簡(jiǎn)單明了，還提供了友好的可視化調(diào)試機(jī)制，能有效提高開(kāi)發(fā)效率，以及降低維護(hù)成本。

實(shí)際效果

相較于 Python 來(lái)說(shuō)，SPL 為本任務(wù)提速 2000 倍，二分法能夠提速 500 倍，多線程并行又提速 4 倍（筆者筆記本電腦的 CPU 只有 4 核），總計(jì)提速 2000 倍，使用 SPL 完成 500 多萬(wàn)目標(biāo)規(guī)模的聚類(lèi)任務(wù)只需要數(shù)個(gè)小時(shí)。

SPL的代碼不僅性能優(yōu)異，而且也并不復(fù)雜，關(guān)鍵計(jì)算代碼只要 23 行。

B10格的 fork 是多線程并行函數(shù)，允許分段執(zhí)行上述算法。

B6格的 sort@m() 函數(shù)是并行排序方法，數(shù)據(jù)量大時(shí)可以提高效率，數(shù)據(jù)有序是二分法使用的前提條件。

C17格的 select@b(…) 函數(shù)是二分查找方法，也是本任務(wù)提速的關(guān)鍵。

后記

性能優(yōu)化的問(wèn)題依賴于高性能的算法，只有把計(jì)算量降下來(lái)才能有效提高運(yùn)行效率，而高性能算法需要在工作中慢慢積累，感興趣的同學(xué)可以來(lái)這里學(xué)習(xí)常用的性能優(yōu)化算法：性能優(yōu)化課程http://www.raqsoft.com.cn/wx/course-performance-optimizing.html

高性能算法需要高效的編程工具來(lái)實(shí)現(xiàn)，之前已經(jīng)說(shuō)過(guò)，Python、SQL、java 等語(yǔ)言都有其弊端，要么無(wú)法并行，要么實(shí)現(xiàn)困難、維護(hù)困難。SPL 有足夠的算法底層支持且允許高并發(fā)，代碼能做到很簡(jiǎn)潔，還提供了友好的可視化調(diào)試機(jī)制，能有效提高開(kāi)發(fā)效率，以及降低維護(hù)成本。

SPL下載地址：http://c.raqsoft.com.cn/article/1595816810031

SPL開(kāi)源地址：https://github.com/SPLWare/esProc