問題描述
國家天文臺有個聚類任務(wù)：共 11 份數(shù)據(jù)，每份數(shù)據(jù)是從一張照片中提取出來的，包含 500 多萬條記錄，每條記錄是一個天體的坐標(biāo)及屬性。11 張“照片”中有些天體坐標(biāo)是重復(fù)的，但這些重復(fù)的坐標(biāo)不完全相同，他們會有一些差別但距離不會太遠(yuǎn)。任務(wù)就是把其中一張“照片”作為基礎(chǔ)，從其他照片中找出重復(fù)的天體，把重復(fù)天體的坐標(biāo)及屬性均值作為該天體的最終坐標(biāo)和屬性，即把距離很近的天體聚成一類再做聚合運算，這樣就可以得到一張坐標(biāo)清晰且信息更加準(zhǔn)確的天體“照片”。
問題分析
這個任務(wù)不算復(fù)雜，只要循環(huán)基礎(chǔ)照片中的每一個天體坐標(biāo)，將其與其他照片中的每個天體坐標(biāo)計算距離，不超過某個閾值就認(rèn)為是同一個天體，視作一類，最后將每一類中所有天體坐標(biāo)求均值就得到了該天體的坐標(biāo)。
但是當(dāng)用計算機計算時就發(fā)現(xiàn)這個任務(wù)的計算量是驚人的，基礎(chǔ)照片需要循環(huán) 500 多萬次，其中的每個天體坐標(biāo)又要與其他照片中的 5000 多萬個坐標(biāo)計算距離，計算復(fù)雜度是 500 多萬 *5000 多萬，這將是個天文數(shù)字。
事實也確實如此，在實驗階段，把每張照片的數(shù)據(jù)量減小 10 倍，即每張照片的天體坐標(biāo)量為 50 萬，用 Python 寫出代碼實現(xiàn)上述方法計算出 11 張照片的聚類結(jié)果需要的時間是 6.5 天。按計算復(fù)雜度來算，500 多萬的數(shù)據(jù)量，計算量是 50 萬數(shù)據(jù)量的 100 倍，即需要耗時 650 天，這肯定是一個無法接受的數(shù)字。
同樣的 50 萬數(shù)據(jù)量，被裝入了某分布式數(shù)據(jù)庫后用 SQL 實現(xiàn)，動用了 100 顆 CPU 后，跑了 3.8 小時完成了計算?？雌饋肀?Python 快了很多倍，但 Python 的 6.5 天是單線程，細(xì)算下來 SQL 的單核性能還不如 Python（3.8 小時 *100>6.5 天）。巨大的資源消耗已經(jīng)難以容忍，而且計算 500 多萬規(guī)模時也要 380 小時。
解決方案
我們來考慮哪里可以優(yōu)化以減少計算量。
基礎(chǔ)照片中的天體坐標(biāo)是必須循環(huán)的，這樣才能保證每個天體都被用來聚類了，其他照片中的天體坐標(biāo)不用每次都遍歷，只要找到基礎(chǔ)天體坐標(biāo)附近的坐標(biāo)就可以了。這類查找任務(wù)很適合二分法，它可以大量減少計算量。
具體過程是這樣的：先對每張照片中的天體坐標(biāo)排序，用二分法找到某個閾值范圍內(nèi)的天體坐標(biāo)，這樣就排除了大多數(shù)天體，這是粗篩過程；用基礎(chǔ)天體與粗篩結(jié)果中的天體計算距離，找出符合條件的結(jié)果，這是細(xì)篩過程。
來看看粗篩加細(xì)篩方法的計算量，10 張照片每張排序一次，計算量是 500 萬 *log(500 萬)*10；二分法粗篩，計算量是 500 萬 *log(500 萬)*10；細(xì)篩過程，計算量不確定，但根據(jù)經(jīng)驗，粗篩后的結(jié)果通常不超過 1 萬個，粗篩的計算量中 log(500 萬) 還要再加 1 萬；這樣算下來，總的計算量大概是 500 萬 *log(500 萬)*10+500 萬 *(log(500 萬)+1 萬 )*10，相較于原來的方法，計算量只有原來的五百分之一。
技術(shù)選型
方法有了，還要選擇程序工具，之前實現(xiàn)時使用 Python，不可否認(rèn) Python 很強大，有天文學(xué)計算的現(xiàn)成框架，比如計算距離的方法，只要調(diào)用現(xiàn)成的類庫就可以輕松算出來。
但 Python 也有著非常嚴(yán)重的弊端：
關(guān)系數(shù)據(jù)庫的 SQL 也無法高效完成。這個聚類運算本質(zhì)上是個非等值連接，數(shù)據(jù)庫對于等值連接還能采用 HASH JOIN 等優(yōu)化方案來減少計算量，但對于非等值連接就只能采用遍歷方案了；SQL 也無法在語句中實現(xiàn)上面設(shè)計的復(fù)雜過程，不能識別距離的單調(diào)性而主動排序并采用二分法；再加上本來做這類數(shù)學(xué)類計算的能力不足（距離計算涉及三角函數(shù)）；所以發(fā)生了前面實驗階段中 SQL 的單核性能還跑不過 Python 的現(xiàn)象。
Java等高級語言雖然可以實現(xiàn)二分法，也可以很好的并行，但代碼寫起來冗長，開發(fā)效率過低，會嚴(yán)重影響程序的可維護性。
那么，還能用什么工具來完成這個任務(wù)呢？
集算器 SPL 是個很好的選擇，它內(nèi)置了很多高性能算法（如二分法），也支持多線程并行，代碼寫起來也簡單明了，還提供了友好的可視化調(diào)試機制，能有效提高開發(fā)效率，以及降低維護成本。
實際效果
相較于 Python 來說，SPL 為本任務(wù)提速 2000 倍，二分法能夠提速 500 倍，多線程并行又提速 4 倍（筆者筆記本電腦的 CPU 只有 4 核），總計提速 2000 倍，使用 SPL 完成 500 多萬目標(biāo)規(guī)模的聚類任務(wù)只需要數(shù)個小時。
SPL的代碼不僅性能優(yōu)異，而且也并不復(fù)雜，關(guān)鍵計算代碼只要 23 行。
A | B | C | D | E | |
1 | =RThd | /距離閾值 | |||
2 | =NJob=4 | /并行線程數(shù) | |||
3 | =file(“BasePhoto.csv”).import@tc() | ||||
4 | =directory@p(OtherPhotos) | /其他照片路徑 | |||
5 | for A4 | =file(A4).import@tc() | /其他照片 | ||
6 | =B5.sort@m(OnOrbitDec) | /排序 | |||
7 | =B6.min(DEC) | ||||
8 | =delta_ra=F(B7,RThd) | /根據(jù)DEC算RA閾值 | |||
9 | =FK(B5,NJob) | /數(shù)據(jù)索引分段 | |||
10 | fork B9 | =B5(B10) | /照片片段 | ||
11 | for A3 | =C11.OnOrbitDec | /DEC | ||
12 | =D11-delta_rad | /DEC下限 | |||
13 | =D11+delta_rad | /DEC上限 | |||
14 | =C11.RA | /RA | |||
15 | =D14-delta_ra | /RA下限 | |||
16 | =D14+delta_ra | /RA上限 | |||
17 | =C10.select@b(between@b(OnOrbitDec,D12:D13)) | /二分查找DEC | |||
18 | =D17.select(RA>=D10&&RA<=D11) | /查找RA | |||
19 | =D36.select(Dis(~,C11)<=A7) | /細(xì)篩 | |||
20 | if D19!=[] | /合并結(jié)果 | |||
21 | =FC(C11,D37) | ||||
22 | =@|B10 | /匯總結(jié)果 | |||
23 | =file(OFile).export@tc(B22) | /寫出結(jié)果 | |||
B10格的 fork 是多線程并行函數(shù)，允許分段執(zhí)行上述算法。
B6格的 sort@m() 函數(shù)是并行排序方法，數(shù)據(jù)量大時可以提高效率，數(shù)據(jù)有序是二分法使用的前提條件。
C17格的 select@b(…) 函數(shù)是二分查找方法，也是本任務(wù)提速的關(guān)鍵。
后記
性能優(yōu)化的問題依賴于高性能的算法，只有把計算量降下來才能有效提高運行效率，而高性能算法需要在工作中慢慢積累，感興趣的同學(xué)可以來這里學(xué)習(xí)常用的性能優(yōu)化算法：性能優(yōu)化課程http://www.raqsoft.com.cn/wx/course-performance-optimizing.html
高性能算法需要高效的編程工具來實現(xiàn)，之前已經(jīng)說過，Python、SQL、java 等語言都有其弊端，要么無法并行，要么實現(xiàn)困難、維護困難。SPL 有足夠的算法底層支持且允許高并發(fā)，代碼能做到很簡潔，還提供了友好的可視化調(diào)試機制，能有效提高開發(fā)效率，以及降低維護成本。
SPL下載地址：http://c.raqsoft.com.cn/article/1595816810031
SPL開源地址：https://github.com/SPLWare/esProc
