摘要: 所謂的熱點圖,是圖1)構建一張灰度圖,圖2)在每個熱點的位置上繪製並疊加形成灰色的熱點圖,圖3)根據顏色表生成熱點圖。不難看出,最核心的是圖2的過程。詳情參考《可視化之熱點圖》。


大數據

作者:funkgiser

所謂的熱點圖,是圖1)構建一張灰度圖,圖2)在每個熱點的位置上繪製並疊加形成灰色的熱點圖,圖3)根據顏色表生成熱點圖。不難看出,最核心的是圖2的過程。詳情參考《可視化之熱點圖》。

大數據

圖1

大數據

圖2&圖3

1強調兩處細節

這種思路效率高,缺點就是不夠靈活,每個點都是同一個樣式,沒有考慮該點的半徑和權重。創建大小不一的模版(章),每個熱點根據自己的半徑值選擇對應的章就可以,實現思路如下:

大數據

半徑&模版

權重的不同,是通過蓋章的“力度”,權重越大,不透明度越大,這樣疊加時也越能體現權重大的效果。是否發現,這個方式會產生覆蓋情況,並不嚴謹。

大數據

權重&透明度(力度)

2大數據渲染

我們看看在不同數據量下的性能分析。7759個熱點,每個點有經緯度和權重三個float值,生成一張2000*1400左右的熱點圖。採用pa7/heatmap.js,在Chrome下測試1w(1倍),5w(5倍),10w(15倍),60w(75倍),100w(150倍),600w(750)六個級別,千萬級別會崩潰。

備註:只測試了一次,誤差估計不小,僅供參考。

大數據

數據轉換消耗(毫秒)

大數據

純渲染時間(毫秒)

在這種方式下渲染時間依次為:68,100,194,894,2918,63817(ms)。數據量在100w以內的還好,渲染時間將近3s。但再往上就不給力了。千萬級別下讀取會崩潰,內存達到1.2G以上。渲染就算可用,從時間消耗上也不實用。

在渲染性能方面,之前我們通過模版,蓋章的思路已經優化了,沿著這個思路提升空間不大。而且,因為渲染上存在疊加依賴,很難並行。

CPU並行

自己實現渲染算法,以並行的方式實現數值計算部分。思路如下:對熱點圖這個目標圖片,遍歷每一個像素,以像素半徑做一個緩衝區分析,獲取對應的熱點數據(數據支持範圍查詢)。如果沒有熱點,則該像素為空;如果存在N個熱點,則計算該點的熱點值。乍看上去,這不是又倒退到逐點計算的思路上。

坦白說,我很不喜歡這個思路,就好比老師出了一道1+2+3……+100的題目,本來是想讓你發現規律和數據模型,。可是你真的在一個個累加。但全班同學合作,把這100個數分解成10組,每人分別計算一部分,同樣也能很快得出結果,這就是另一個角度的智慧。

因為每個點的計算是獨立的,可以通過並行來優化“渲染”時間。但這種思路是以放棄渲染技術為代價的,也要藉助於空間索引,並行計算,在JS上很難實現。

另外,這個思路讓我認為(不知道對不對),點差值和熱點圖並無本質區別。

GPU並行

下圖是OpenGL的思路:每一個熱點構造成一個正方形,對角線將其分為兩個三角形,有四個頂點和6個頂點索引。採用批次渲染的方式,每個批次下渲染1w個熱點(對應4w個頂點),將數據分解為多個批次,實現大數據的渲染,GPU中實現混合效果。具體的shader代碼可以參考pyalot。

大數據

我在WebGL下實現了這個思路,還是剛才那個7759個熱點的數據,我放到一個渲染批次,對這一個批次渲染多次, 1s內完成千萬級別的渲染。

大數據

3問題

數據解析是瓶頸,比如經緯度點最終要轉換到像素單。如果性能還不夠,就“偷工減料”,建立矢量金字塔,本質就是把N個點合併成一個,減少渲染過程的計算量。

二維對應的策略是,渲染性能不夠,就把渲染問題轉為for循環下的簡單計算,然後通過CPU並行優化;對於三維,需要點轉三角形,創建buffer,然後通過GPU實現渲染過程。

從渲染的角度來看,無論二維還是三維,在十萬級別下的性能都不錯,百萬級別也能接受,差別不大,但十萬以上,兩者的渲染差距則體現出來,前者像打狗棒,強調的是心法和招式,後者則是降龍十八掌,靠的是內力。兩點區別,二維是因為渲染性能不行,只好採用最簡單的數值計算,以這樣的代價實現核心計算的並行;三維本身就是並行策略,就是通過shader,通過頂點和片元實現GPU的並行。第二,GPU的並行能力顯然不是CPU可以媲美的,換句話說,GPU能夠承擔更多的並發計算量,盡可能少的對原始數據做預處理,理論上,只要內存夠用或讀取數據合理,顯存上通過批次渲染,可以渲染任意大的數據量,而且時間和批次應該是線性的。

最後,再強調一下數據。簡單計算了一下,假如是一個二進制流的方式,一個熱點佔12個字節,這樣1kw個點要佔120M,即使壓縮後也得20M,這還沒有考慮數據轉換上的消耗。對於Web端,基於原始數據,需要有一種機制,能夠快速的完成數據傳輸和處理。

有一個不一定對的思路,建一個GeoHash,大範圍的預先生成熱點圖,更新頻率可以不高;局部範圍則通過GeoHash獲取對應的熱點,實現本地渲染。GeoHsh貌似是一種很不錯的大數據設計方式,我也不太了解,有時間再研究研究。

還有一個收穫,當複雜度達到一定程度,原先行得通的算法和方案不一定滿足要求了。更精彩的是,因為性能低,以前認為比較差的思路,因為思路簡單,容易實現並行改造,竟然可行了。

End.

轉貼自: 36大數據


留下你的回應

以訪客張貼回應

0

在此對話中的人們

熱門標籤雲

每月文章