2010年3月4日 星期四

Multiarray and View

最近有個東西需要用到一個四維陣列,其實本來是用四層的 hash table 下去做的,當然 hash 是不慢,但是因為取值的次數太頻繁,在跑過 profiling 之後確定這邊是一個瓶頸,所以嘗試要重構這個部分。如果為了效能考量,最好的作法就是用一個四維陣列來作。

因為本來 的 code 是有類似 indexed-view 的用法,就是我要固定某一個或是某兩個維度,然後把剩下的維度當作陣列來迭代。之前的 code 在這邊是去迭代那些 hash table,然後把需要的值取出來放到另外一個 hash table 裡面去,所以也不是真的 view,而是重新蒐集值。很慢,但是這份 code 最早是只有兩個維度的,所以當初設計的人這樣做也很合理,只是隨著時間過去,需求的追加,這部分才越來越複雜。

為了效能上的考量,我在考慮這個部分是不是不該重新串值,而是直接使用 view 的手法來取得需要的值,想到這個需求時,我開始思考我要什麼東西,這個過程在我的腦海裡面一直改版。

第一個版本是我要設計一個四維陣列類別,然後另外設計四個 view 類別,分別針對四個維度來 view 那個四維陣列。當然,可想而知,這四個 view 類別的實作會很相似,所以我是不是應該把這四個設計成一個?

所以第二個版本是我要設計一個四維陣列,還有一個 view 類別,接一個參數,用來 view 那個四維陣列,而參數可以指定我要固定的那一個維度。但是如果我想要固定兩個維度怎麼辦?我是不是應該讓這個 view class 可以套用在自己身上,也就是 templating 這個 view class?但是一旦這樣作,view 的維度就不一定是三維,而有可能是一維、二維。所以我應該用個 recursive class template 手法來做這件事?

那第三個版本就是我要設計一個四維陣列,還有一個 resursive class template 的 view 類別,用來 view 我的陣列,還有我的陣列的 view,還有 view 的 view。這樣我幹嘛不把陣列也設計成 recursive class template?這樣以後還可以重複使用,那為了重複使用,我也應該把這個陣列的型別也設計成 template。

所以第四個版本是我 要設計一個 resursive class template 可以用來定義任意維度的陣列,還有一個 view 可以用來 view 任意維度的陣列或是 view(只要我的陣列跟 view 提供相同的 interface)。這樣的話,那我幹嘛不直接用 boost::multiarray 呢?這樣我只需要設計 view 的部份就可以了。ㄟ……等等,如果我是 multiarray 的作者,我應該會想提供 view 的功能,不知道 boost::multiarray 有沒有 view 可以用?查一下好了……嗯……有。

第五個版本:

#include <boost/multi_array.hpp>

心得是那些偉大的心智真的看的很遠很遠。當我想到這個可能性的時候,他們已經做完了。