記憶體資料集產生的隱性成本
當我們要對資料做一些非常規的複雜運算時,通常要將資料裝入記憶體。現在也有不少程式設計語言提供了記憶體資料集物件及基本的運算方法,可以較方便地實現這類運算。不過,如果對記憶體資料集的工作原理了解不夠,就可能寫出低效的程式碼。
我們看資料集的產生。比如要生成一個100行2列的資料集,第一列x為序號,第二列xx是第一列的平方。
第一種方法,先生成一個空資料集,再一行一行地追加資料進去。
A |
B |
|
1 |
=create(x,xx) |
|
2 |
for 100 |
>A1.insert(0,A2,A2*A2) |
第二種方法,直接產生相應行數的資料集。
A |
B |
1 |
=100.new(~:x,~*~:xx) |
這兩種方法產生的結果集相同,實質的迴圈次數和每次迴圈的計算內容看起來也相同,但執行效率卻不一樣,後者要比前者更快。
資料集在記憶體中會儲存成一個連續的陣列。動態追加的資料集,會導致這個陣列長度不斷地變長,原先為這個陣列分配的空間也要擴大。而記憶體分配不是一件很簡單的事情,已經分配好的空間的後面記憶體很可能已經被佔用而不能再繼續擴大,只能重新分配一塊更大的空間,然後將原空間內的資料複製過來。尋找空間和複製資料都要佔用CPU時間,常常比運算本身的消耗都大。一般情況下,分配記憶體時會多預留一些空間來應付可能的增長,這樣不致於每次追加都導致重新記憶體分配,但也不可能預留太多而浪費記憶體,如果追加次數過多,仍然還會有不少時間消耗到記憶體分配上。而如果事先知道資料集行數一次性創建出來後,則只需要在開始做一次記憶體分配即可。
動態追加的資料集雖然使用起來更靈活,但效能卻趕不上靜態資料集,在關注效能時要習慣性地避免。
其實,用這個例子來對比並不很恰當,因為有100.new(~:x,~*~:xx)這樣的簡單寫法時,很少人會採用動態追加的資料集了,這裡用這個例子主要是為了突出關鍵差異。而實際應用中會有不少情況下很難用一句話寫出資料集生成,程式設計師就可能習慣性地採用動態追加的資料集了。
舉一個更恰當的例子,我們想生成一個20行2列的Fibonacci資料集,第一列key為行號,即1,2,3,…;第二列value為值。Fibonacci數列的規則是:第1、第2行取值為1,從第3行起,取值為前兩行之和。這個運算需要一步步實現,使用動態資料集就是很自然的想法了:
A |
B |
|
1 |
=create(key,value) |
|
2 |
>a=0 |
>b=1 |
3 |
for 20 |
>A1.insert(0,A3,b) |
4 |
>b=a+b,a=b-a |
不過,使用靜態資料集的效能更好,即使計算本身仍然需要一步步實現,但資料集可以一次性產生:
A |
B |
|
1 |
=20.new(0:key,0:value) |
|
2 |
>a=0 |
>b=1 |
3 |
for A1 |
>A3.key=#A3,A3.value=b |
4 |
>b=a+b,a=b-a |
先生成一個都填滿0的資料集(隨便別的什麼數也可以),然後再用迴圈把正確的值填進去。實質計算量仍然一樣,但避免了動態分配。
除了行方向動態追加外,還有列方向的問題,即在資料集上增加新的列。
列追加比行追加要更為複雜。記憶體資料集中的一行是一條記錄,物理上也是一個數組。因為資料結構很少改變,大多數記憶體資料集不會在生成這個陣列時預留空間,否則記憶體浪費就太多了(每一行都有)。這時候每次追加列時都會發生前面說的重新分配空間,而且要針對每一行記錄進行,再將原記錄資料抄過來,這個動作的時間成本經常遠遠超過追加的那個列本身的計算。
記憶體資料集一般都有提供追加列的功能,這會帶來方便性,但在關注效能時卻要慎用。能不用則不用,一定需要時,也是如上所述,最好是一次性把需要追加的列都加上,而不要一遍遍地追加。
比如我們想在第一個例子中的資料集上再追加兩個列y=x+xx和yy=y*y。看起來較自然的兩步寫法:
A |
B |
|
3 |
=A1.derive(x+xx:y) |
=A3.derive(y*y:yy) |
一次性產生列的寫法:
A |
B |
|
3 |
=A1.derive(x+xx:y,0:yy) |
>A3.run(yy=y*y) |
相比之下,後者的效能要更好。
類似技巧還可以用在從資料庫中取出的資料集上。
比如要從資料表T中取出欄位month和amount並按month排序,然後追加一列計算amount的累計值。先讀出再追加列的寫法:
A |
B |
|
1 |
=db.query(“select month,amount from T order by month) |
|
2 |
=A1.derive(0:acc) |
>a=0 |
3 |
for A1 |
>A3.acc=(a=a+A3.amount) |
用SQL語句先把列生成好的寫法:
A |
B |
|
1 |
=db.query(“select month,amount,0 as acc from T order by month) |
>a=0 |
2 |
for A1 |
>A2.acc=(a=a+A2.amount) |
對於關注效能的程式設計師,後一種寫法會成為習慣。
原文釋出時間為:2018-12-4
本文作者:蔣步星
本文來自雲棲社群合作伙伴“4GI-A" target="_blank" rel="nofollow,noindex">資料蔣堂 ”,瞭解相關資訊可以關注“shujujiangtang”微信公眾號