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

No comments:

Post a Comment