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

Wednesday, April 24, 2013

Python PIL experiment (a image comparison tool) continued


numpy and PIL

実際に画像に適用してみた所,1024x1024 の大きさの画像では処理に 6 秒程度,消費するメモリサイズは230MBなのだが,3840x2160の画像を利用すると,2.3GBのメモリと263秒の時間がかかることがわかった.この2つの解像度はpixel の数で言えば 8 倍程度で,メモリの処理が比例しているのは良いとしても,処理の時間がかかりすぎる.また,メモリの消費量自体も多すぎる.私はプログラム中で3つのバッファを使っているだけであり,1024x1024の場合には 10 MB程度,3840x2160 の場合には,72MB程度と思っていた.しかし,30倍ものメモリが消費されている.

プロファイルの結果,最内ループの tuple の生成と abs 関数にほとんどの時間がかかっていることがわかった.そこで,この部分を numpy で書くことにした.結果を以下に示す.Intel Core i7-2720 2.20GHz Linux(Kubuntu 12.10, kernel 3.5.0-27), Python 2.7 における結果である.

  • native  230MB, 6.0 seconds for 1024x1024 image
  • numpy 110 MB, 0.21 second for 1024x1024 image
  • native  2300MB, 263 seconds for 3840x2160 image
  • numpy 320 MB, 1.18 second for 3840x2160 image

計算速度は 30 倍から200倍に, メモリサイズも 50% から 15% の消費量と激減している.実は最初の実装では倍程度にしか高速化できなかったので,私は多少失望したのであるが,profile した結果,非0の要素をカウントするための sum関数がほとんどの時間を占めていることに気がついた.この sum 関数は pythonのbuildin のもので,おそらく numpy の data 構造から毎回値を取り出しては計算しているのであろう.これを numpy.sum に変更した所,ほどんどの時間を占めていた sum 関数の消費時間が profile ではほぼ 0 になり,200倍の高速化が達成された.これは matlabに似ている.(実際,numpy は matlab の Python portであるが,いかに性能を出すかでも似ているという意味である.)

ImgCompNumpy.py code

Tuesday, April 23, 2013

Python PIL experiment (a image comparison tool)


概要:
Python の画像 module PIL を使ってみた.

Python PIL module

Python には画像ファイルを処理するのに便利な Python Imaging Library (PIL)という module がある.今回はファイルフォーマットは異なるが,内容が同一かどうかをテストしたいという状況にあった.たとえば,テストの参照となるファイルは圧縮されているが,それと比較するファイルはそうではないというようなものである.convert などのツールを使うということも考えたが,時には使ったことのないツールを使ってみるのもよいだろうと PIL で画像を比較するツールを書いた.

Monday, April 22, 2013

Math objects on programming (1)

概要

プログラミングにおいて数学的な object を使うとプログラムが簡単になることがある.今回この考えが上手くいった例に会ったのでそれを示す.

数学的 object とプログラミング


プログラムのテストにおいて,異るパラメータの組合せを考えるということはよくあることである.組合せを生成する簡単な方法は,多重ループを使うことである.

ここではpython 風の pseudo code を使う.また,実際に動く python のプログラムも公開する.

たとえば,2つのパラメータのリストがあった場合,

 data_size_list = [ 5, 64, 512, ]
 screen_resolution_list = [ 
   '2560x1440', '3840x2160', ]

この組合せは,

  for d in data_size_list:
    for s in screen_resolution_list:
      print_comb(d, s) # output

のように書いて出力することができる.この方法は簡単であるが,ある特定のリストが不要な場合,プログラムコードを変更する必要がある.それで直積の考えを使って組み合わせを生成することにする [1].何の積かというと,集合の積である.ここに k 個の集合があり,その要素の全ての組合せを考える時,k 個の集合の直積を考えている.これは再帰的に定義することができる.

  1. \(k = 0\), つまり 0 個の集合の直積は一つの空リスト([])である.
  2. \(k \geq 0\) の時,       \begin{eqnarray*}       A_1 \times \cdots \times A_k   &=&\left\{(a,t)| a \in A_1, t \in A_2 \times \cdots \times A_k        \right\} \end{eqnarray*}
である.二番目の条件の意味は,既に \(k-1\)の集合から1つづつ要素をとった組合せのリストが生成されているのであれば,\(k\)個の集合のリストを生成するには,\(k\)番目の集合から \(a\) を一つとってリストを生成すれば良いという意味である.この実装例は以下のようになる.

data_size_list = [ 5, 64, 512, ]
screen_resolution_list = [ 
   '2560x1440', '3840x2160', ]
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:
        print i

make_tuple() 関数が直積の実装になっている.

これは直積という数学的 Object を使って組み合わせのプログラムを一般化した例である.こうすることによって,プログラムのコードがデータの方に移った.つまり,データによって何重ループになるかが決まるのであり,どんな組合せのテストをするかが変化するような場合に,プログラムを変更する必要がない.このプログラムの例は単純でループで実装しても良いように思えるがもしれない.確かにこの場合には不要であろうが,今回,私は組合せが多く,様々な条件がテスト毎に変化する状況であったので,このように実装するのは有益であった.

次回は私がこの問題で数学的 object でどんな間違いをしたのか説明しよう.