Thursday, April 25, 2013

Math objects on programming (2)


単純な組合せを生成することは前回で述べた.しかし,私の仕事では,GPU という高速ではあるが,メモリサイズが小さい計算機を使う必要がある.ここでの data size は GB の単位であり,64 GB とか 512 GB というのは現在のところ,一台の GPU には収まらない.512 GBは我々の使っている一台の計算機の実メモリにも収まらない.そこで,何十台かの計算機に複数の GPU を搭載して,それを協調して使うわけである.ほとんど全ての我々のクライアントは計算機の台数と性能の関係についての情報を要求する.それは我々のクライアントは特定の問題を解く必要があり,そのためには何台の計算機と何台の GPU を購入する必要があるかを知りたいためである.したがって,計算機を何台使ったかについてプログラムのデータ処理のスループット性能がどうかを見たい.そこで,計算機の台数を新たなパラメータとする.
data_size_list = [ 5, 64, 512, ]
screen_resolution_list = [ 
  '2560x1440', '3840x2160', ]
node_count_list = [ 
  1, 2, 4, 8, 16, 32, 64, ]
しかし,データがメモリに収まらなければ遅いことは確実にわかっているので,テストに際しては計算機の台数は data size によって変化させたい.ループの場合には,不要なものを filter out するということが簡単に思いつく.以下のようなプログラムになるだろう.

for d in data_size_list:
  for s in screen_resolution_list:
    for n in node_count_list:
      # FILTER: filter some cases.
      # assume one node can handle 
      # 64G, but not more
      if (n * 64 < d):
        continue
      item_list = [
        d, s, n,
      ]
      comb_list.append(item_list)
しかし,これを直積の考えに適用しようとするとどうなるだろうか.ループの考えから出発すると,データ毎にフィルタ関数を持たせるということを考える.しかし,これでは各リストがフィルタ関数を持つことになる.この考えではプログラムが複雑になる.実際に私はそういう実装をしようとしたが,あまりに複雑な感じがしてしまった.しかもほとんどの filter 関数は何もしないのである.プログラムを少し拡張しようとするともっと複雑になる.ここでの「感じ」というのは上手く説明できないのだが,「なぜこの問題がこんなに複雑な解答になってしまうのだろうか」という疑問である.私は問題を良く理解していない場合,このような疑問を持つことが多い.

そこで数学に戻って考えてみた.生成される組合せは,data size の関数である.だが,これをフィルタ関数とするというのはどういうことだろうか.これはgenerate and test 方式に似ている.しかし,どの組合せが生成されるのかは,data size だけの関数である.ここでようやくわかった.これは data size から node 数への単なる map 関数だったのに,それを数学的には意味のない方法で実装してしまったのだ.結局次のようなコードを実装した.

data_size_list = [ 5, 64, 512, ]
screen_resolution_list = [ 
   '2560x1440', '3840x2160', ]
data_size_node_count_map = {
  5: [1, 2, 4, 8, 16, 32, 64]
  64: [8, 16, 32, 64]
  512: [32, 64]
}
all_list = [
  data_size_list,
  screen_resolution_list,
]
comb_list = []
c_tuple = [''] * len(all_list) 

def make_tuple(idx):
  if(idx >= len(all_list)):
    comb_list.append(
        copy.deepcopy(c_tuple))
  else:
    for i in range(len(all_list[idx])):
      c_tuple[idx] = all_list[idx][i]
      make_tuple(idx + 1)

def gen_combination_list():
    make_tuple(0)
    for i in comb_list:
        gen_with_node(i)
gen_with_node() 関数が data_size_node_count_map()を使って node 数に関する組合せを生成する.このようにすることで,効率的で簡単な実装を作ることができた.私は時々他の人のコードを見て,数学的に変なコードだというふうに思うことがある.これは特に実装する能力は高いが,数学的な思考をコーディングではあまり利用しない人に見られる.

以前私はこういう実装能力の高い人達を尊敬しており,そういうプログラムを書こうとする傾向があった.しかし,数学的 object を導入するとコードが簡単になることがしばしばである.驚いたことには,実装能力の高い人達と遜色のない,時には高速なプログラムが書けることがわかって,その能力をあまり必要とみなくなってしまった.もちろん同じアルゴリズムを実装するのであれば,私のコードの方が遅い.しかし,今回のように間違ったアルゴリズムを採用してしまえば,実装能力の高さは比較的問題にならないことが多い.コードがシンプルな分,バグも少ないことが多い.

今回は自分が数学的 object を正しく使えないという間違いをおかしてしまった.自分をもっと見直すべきだと反省する.

ところで,数学的 object が上手くいくのはなぜだろうか.私は2つの理由を思いつく.一つは数学では何世紀にもわたって問題がどういう部分問題に分解され,よくでてくるパターンが何かが研究されてきている.私がその場で考えた解答よりも多数の天才が何百年にもわたって考えてきた方法が上手くいくことが多いことに不思議はない.実は,私には天才達の考えよりも上手くいったことがある覚えはない.二つ目の理由としては,数学的 object はプログラミング言語でも既にサポートされていることが多いということである.言語のデザイナの多くも数学的 object の問題解決に対する有用性を見い出したのだろうと思う.数学的object が言語によってサポートされている場合,その object はシンプル,かつ効率的に書けることが多い.ここでは 直積と map の考えを使った.map の考えはpython では dictというデータ構造として既にサポートされている.lisp ではmapcar, Java には util に Map, C++ の STL にはそのもの map というtemplate class がある.

簡単な問題ではあるが,興味深い経験でもあった.

References

[1] Hisao Tamaki, ``Introduction to probability theory for the information scientist (in Japanese)'', Saiensu, ISBN4-7819-1012-2, 2002

Implementation example

http://sundayresearch.de/hitoshi/sundayresearch/programming/Python/20130323_math_object/enum_code_20130323.zip

No comments:

Post a Comment