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 でどんな間違いをしたのか説明しよう．