Ctrl+K

プログラミングのない世界 (1)

プログラミングのない世界 (1)#

計算結果を記憶する#

あらかじめすべての可能性について計算して保持する#

import itertools
list(itertools.product([0, 1], repeat=2))

[(0, 0), (0, 1), (1, 0), (1, 1)]

len(list(itertools.product([0, 1], repeat=2)))

4

\(2 \times 2 = 4\) の組み合わせについて、divmod() の値 (剰と余の\(2\)要素) を列挙する:

binary_add = [[divmod(i+j,2) for j in [0,1]] for i in [0,1]]
binary_add

[[(0, 0), (0, 1)], [(0, 1), (1, 0)]]

len(binary_add)

2

binary_add[0]

[(0, 0), (0, 1)]

binary_add[1]

[(0, 1), (1, 0)]

[len(l) for l in binary_add]

[2, 2]

binary_add[0][0]

(0, 0)

binary_add[0][1]

(0, 1)

binary_add[1][0]

(0, 1)

binary_add[1][1]

(1, 0)

[binary_add[i][j] for i,j in itertools.product([0,1], repeat=2)]

[(0, 0), (0, 1), (0, 1), (1, 0)]

参考) Pythonのリストは可変長なのでサイズ (型) を取れないが、Numpy行列に変換すると \(2 \times 2 \times 2\) であることが判る:

  • リストと同じようにアクセスできるが、添字を連続して表記することもできる

import numpy as np
x = np.array(binary_add)
x.shape

(2, 2, 2)

x[0]

array([[0, 0],
       [0, 1]])

x[0][0]

array([0, 0])

x[0, 0]

array([0, 0])

参考) Pythonのディクショナリを使う:

  • 要素のアクセス方法はリストと同じ

binary_add = {i : {j : divmod(i+j,2) for j in [0,1]} for i in [0,1]}
binary_add

{0: {0: (0, 0), 1: (0, 1)}, 1: {0: (0, 1), 1: (1, 0)}}

[binary_add[i][j] for i,j in itertools.product([0,1], repeat=2)]

[(0, 0), (0, 1), (0, 1), (1, 0)]

計算するごとに結果をキャッシュに保持する#

計算結果をキャッシュに記憶して、次の計算時はキャッシュされた値を返す:

  • キャッシュが値を持っていない状態を表現する

    • ２行２列の整数型のデータ行列を作る (divmod() の戻り値が2要素なので、\(2 \times 2 \times 2\) 行列になる)

      • np.empty((2,2,2), dtype=int)

    • 同じサイズの行列を作って、データにキャッシュされた値を保持しているか (False) 否か (True) を設定できるようにする

      • np.ma.array(np.empty((2,2,2), dtype=int), mask=np.ones((2,2,2)), dtype=int))

  • データの特別な値をキャッシュに保持されているか否かの判定に使うこともできる

    • 整数: 0 (Falseと等価。今回は、計算結果が0になることがあるので使えない)

    • 整数: -1 (計算結果が負の値になる時は使えない)

    • 浮動小数: NaN

import numpy as np

空の行列 (値は初期化されていない):

np.empty((2,2,2), dtype=int)

array([[[101396964589471,               0],
        [              0,               0]],

       [[              0,               0],
        [              0,               0]]])

全ての要素が \(1\) (True) の行列:

np.ones((2,2,2), dtype=int)

array([[[1, 1],
        [1, 1]],

       [[1, 1],
        [1, 1]]])

組み合わせてマスク付き行列を作る:

x = np.ma.array(np.empty((2,2,2), dtype=int), mask=np.ones((2,2,2), dtype=int))
x

masked_array(
  data=[[[--, --],
         [--, --]],

        [[--, --],
         [--, --]]],
  mask=[[[ True,  True],
         [ True,  True]],

        [[ True,  True],
         [ True,  True]]],
  fill_value=999999,
  dtype=int64)

x[0,0]

masked_array(data=[--, --],
             mask=[ True,  True],
       fill_value=999999,
            dtype=int64)

値を代入していないので masked 状態である:

x.compressed()

array([], dtype=int64)

x[0,0][0], x[0,0][1]

(masked, masked)

x[0,0][0] is np.ma.masked, x[0,0][1] is np.ma.masked

(True, True)

x[0,0] = (0, 1)
x

masked_array(
  data=[[[0, 1],
         [--, --]],

        [[--, --],
         [--, --]]],
  mask=[[[False, False],
         [ True,  True]],

        [[ True,  True],
         [ True,  True]]],
  fill_value=999999)

x[0,0][0], x[0,0][1]

(0, 1)

x[0,0][0] is np.ma.masked, x[0,0][1] is np.ma.masked

(False, False)

class binary_op:

    def __init__(self):
        self.cached_add = np.ma.array(np.empty((2,2,2), dtype=int), mask=np.ones((2,2,2), dtype=int))
        
    def add(self,a,b):
        if a in [0,1] and b in [0,1]:
            if self.cached_add[a,b,0] is np.ma.masked or self.cached_add[a,b,1] is np.ma.masked:
                self.cached_add[a,b] = divmod(a+b,2)
            return tuple(self.cached_add.data[a,b])
        else:
            raise ValueError

bo = binary_op()

bo.cached_add

masked_array(
  data=[[[--, --],
         [--, --]],

        [[--, --],
         [--, --]]],
  mask=[[[ True,  True],
         [ True,  True]],

        [[ True,  True],
         [ True,  True]]],
  fill_value=999999,
  dtype=int64)

一度計算すると結果がキャッシュに保持される:

bo.add(1,1), divmod(1+1,2)

((1, 0), (1, 0))

bo.cached_add

masked_array(
  data=[[[--, --],
         [--, --]],

        [[--, --],
         [1, 0]]],
  mask=[[[ True,  True],
         [ True,  True]],

        [[ True,  True],
         [False, False]]],
  fill_value=999999)

二度目からはキャッシュされた値が戻る:

bo.add(1,1)

(1, 0)
Contents