目次と前回の記事
Python のバージョンとこれまでに作成したモジュール
本記事のプログラムは Python のバージョン 3.13 で実行しています。また、numpy のバージョンは 2.3.5 です。
| リンク | 説明 |
|---|---|
| marubatsu.py | Marubatsu、Marubatsu_GUI クラスの定義 |
| ai.py | AI に関する関数 |
| mbtest.py | テストに関する関数 |
| util.py | ユーティリティ関数の定義 |
| tree.py | ゲーム木に関する Node、Mbtree クラスなどの定義 |
| gui.py | GUI に関する処理を行う基底クラスとなる GUI クラスの定義 |
AI の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
今回の記事の内容
今回の記事では前回の記事に引き続き ビット列の反転処理 のアルゴリズムを紹介します。
分割統治法による delta swap を利用した方法の改良
前回の記事では 分割統治法 による delta swap を利用した ビット列の反転 を行う下記のアルゴリズムを紹介しました。
- 最初はすべてのビットを持つ 1 つのビット列に分割 した 状態から開始 する
- 分割した すべてビット列のビット長が 1 になるまで 下記の処理を 繰り返す
- ビット長が 2 以上 の すべての分割したビット列 に対して下記の処理を行う
- ビット長が偶数 の場合は 均等なビット長 で 左右に 2 つに分割 し、分割したビット列 を delta swap でまとめて交換 する
- ビット長が奇数 の場合は 真ん中の 1 ビット とその 左右のビット列 で 3 つに分割 し、左右のビット列 を delta swap でまとめて交換 する
今回の記事では、前回の記事と同様に下記の記号を用いて説明を行います。
- 反転するビット列の ビット長 を $\boldsymbol{n}$ と表記する
- i 回目の手順 2 の処理によって 分割されたビット列 の ビット長 を $\boldsymbol{n_i}$ と表記する。ただし、分割する前のビット列の ビット長が奇数 の場合に 3 つに分割された、中央のビット長が 1 のビット列 は 考慮に入れない ものとする
- 式を共通した方法で記述できるように、$\boldsymbol{n_0 = n}$ と表記する
-
i 回目の手順 2 の delta swap の計算 で利用する ビットマスク を $\boldsymbol{m_i}$、
deltaを $\boldsymbol{d_i}$ と表記する
前回の記事で説明したように、$\boldsymbol{n_i}$ と $\boldsymbol{d_i}$ は下記の式によって、一つ前の手順 2 計算 した $\boldsymbol{n_{i-1}}$ と を 元に計算 することができます。
- $n_i = n_{i - 1} \ //\ 2$
- $d_i = (n_{i - 1} + 1) \ //\ 2$
また、下記の理由から $\boldsymbol{n_i + d_i = n_{i - 1}}$ が成り立ちます。ただし、// は 商を計算する演算子 です。このことは後で図でも示します。
- $\boldsymbol{n_i + d_i = n_{i - 1} \ //\ 2 + (n_{i - 1} + 1) \ //\ 2}$ である
- $\boldsymbol{n_{i - 1}}$ が偶数 の場合は $\boldsymbol{n_{i - 1} \ //\ 2 = \frac{n_{i - 1}}{2}}$、$\boldsymbol{(n_{i - 1} + 1)\ //\ 2 = \frac{n_{i - 1}}{2}}$ なので、$\boldsymbol{n_i + d_i = n_{i - 1}}$ となる
- $\boldsymbol{n_{i - 1}}$ が奇数 の場合は $\boldsymbol{n_{i - 1} \ //\ 2 = \frac{(n_{i - 1} - 1)}{2}}$、$\boldsymbol{(n_{i - 1} + 1)\ //\ 2 = \frac{(n_{i - 1} + 1)}{2}}$ なので、$\boldsymbol{n_i + d_i = n_{i - 1}}$ となる
前回の記事のアルゴリズムの問題点
前回の記事 では、上記の i 回目の手順 2 の delta swap の計算に必要な ビットマスクを表す $\boldsymbol{m_i}$ を計算 する下記のアルゴリズムを紹介しました。
下記の処理 を i 回繰り返す ことにより $\boldsymbol{m}$ に $\boldsymbol{m_i}$ の値が計算 される。ただし、繰り返した回数 を 0 から数えた値を j とする
- $\boldsymbol{j = 0}$ の場合は下記の式によって 右端の 1 個 のビット列を 2 個に分割して交換 する ビットマスクを計算 する
$\boldsymbol{m = (1 << n_i) - 1}$ - $\boldsymbol{j ≠ 0}$ の場合は、下記の式によって 右端の $\boldsymbol{2^{j}}$ 個 のビット列を 2 倍の $\boldsymbol{2^{j+1}}$ 個 に まとめて分割して交換 する ビットマスクを計算 する
$\boldsymbol{m = m \ |\ (m << d_{i-j})}$
このアルゴリズムでは、$\boldsymbol{m_i}$ を計算 するために、上記の 手順 1 を 1 回、手順 2 を i - 1 回繰り返す 必要があります。例えば、$\boldsymbol{m_5}$ を計算 するためには、下記の 合計 5 回の計算 を行う必要があります。
$m = (1 << n_5) - 1$
$m = m\ |\ (m << d_4)$
$m = m\ |\ (m << d_3)$
$m = m\ |\ (m << d_2)$
$m = m\ |\ (m << d_1)$
このように、このアルゴリズムは 手順 2 を行う回数が多くなるほど、ビットマスクの計算 に必要な 処理が多くなる という問題があります。
直前の手順 2 で計算したビットマスクを利用する方法
$\boldsymbol{m_i}$ を計算 する別のアルゴリズムとして、$d_i$ や $n_i$ と同様に、直前の i - 1 回目で計算 したビットマスクである $\boldsymbol{m_{i-1}}$ を利用する という方法があります。
具体的には $\boldsymbol{m_i}$ は 常に 下記の 2 つの式で計算 することができます。
$\boldsymbol{m = m_{i-1}\ \text{&}\ (m_{i - 1} >> d_i)}$
$\boldsymbol{m_i = m\ | \ (m << d_{i - 1})}$
ただし、最初の $\boldsymbol{m_1}$ だけ は、先程と同様に下記の式で計算します。
$\boldsymbol{m_1 = (1 << n_1) - 1}$
意味がわからない人が多いと思いますので、上記の式で $\boldsymbol{m_i}$ を計算できることを、ビット長が 11 の $\boldsymbol{n_0 = 11}$ の場合の ビット列の反転 の場合を 具体例を挙げて説明 します。
なお、ビット長を 11 ビット にした理由は 手順 2 で分割されたビット列 の ビット数が奇数 の場合でも 正しい処理が行われる ことを示すためです。
1 回目の手順 2 のビットマスクの計算処理
1 回目の手順 2 では下記の式で、$\boldsymbol{n_1}$、$\boldsymbol{d_1}$、$\boldsymbol{m_1}$ が計算されます。
$n_1 = n_0 \ //\ 2 = 11 \ //\ 2 = 5$
$d_1 = (n_0 + 1) \ //\ 2 = 12\ //\ 2 = 6$
$m_1 = (1 << n_1) - 1 = (1 << 5) - 1 = 0b00000011111$
2 回目の手順 2 のビットマスクの計算処理
2 回目の手順 2 では下記の式で、$\boldsymbol{n_2}$、$\boldsymbol{d_2}$、$\boldsymbol{m_2}$ が計算されます。なお、$\boldsymbol{m_2}$ の 具体的な計算結果 については 図で示します。
$n_2 = n_1\ //\ 2 = 6\ //\ 2 = 3$
$d_2 = (n_1 + 1) \ //\ 2 = 7\ //\ 2 = 3$
$m = m_{2-1}\ \text{&}\ (m_{2 - 1} >> d_2) = m_1\ \text{&}\ (m_1 >> d_2)$
$m_2 = m\ | \ (m << d_{2 - 1}) = m\ | \ (m << d_1)$
下図は 上記の式 で $\boldsymbol{m_2}$ の計算の過程 を表す図です。以降の図では、ビットマスク の 1 のビット を 黄色で塗りつぶす ことにします。
前回の記事と同様に、$\boldsymbol{m_2}$ を 赤線で左右に分割 した $\boldsymbol{m_{2L}}$ と $\boldsymbol{m_{2R}}$ という 2 つのビット列に分けて考える ことにします。なお、前回の記事では $m_{2l}$ のように l と r を小文字で表記しましたが、$l$ がわかりづらいと思いましたので今回の記事では大文字にしました。
最初の $\boldsymbol{m = m_1\ \text{&}\ (m_1 >> d_2)}$ は、下記の理由から $\boldsymbol{m_{2R}}$ を計算 します。
- 2 回目の手順 2 の処理では、1 回目の手順 2 の処理で上図の 赤線で左右に分割 された 2 つのビット列 を 青線 で 左右に分割 する
- $\boldsymbol{m_1}$ は上図からわかるように 赤線で左右に分割 された 右の $\boldsymbol{m_{2R}}$ と同じ範囲のビットをすべて
1とする値である - $\boldsymbol{m_{2R}}$ は 右端から 一番右の青線までの $\boldsymbol{n_2}$ 個の
1が並ぶ ビット列である - 先程説明したように、$\boldsymbol{n_i + d_i = n_{i - 1}}$ が成り立つので $\boldsymbol{n_2 + d_2 = n_1}$ となる。この式を変形すると $\boldsymbol{n_1 - d_2 = n_2}$ となる
- $\boldsymbol{m_1 >> d_2}$ によって 0 番から $\boldsymbol{n_1}$ 個の
1が並ぶ $\boldsymbol{m_1}$ のビット列の、右端の $\boldsymbol{d_2}$ 個の1が削除 されて 残りの1が右端に並ぶ ので、$n_1 - d_2 = \boldsymbol{n_2}$ 個の1が右端に並ぶ $\boldsymbol{m_{2R}}$ が計算 される - $\boldsymbol{m = m_1\ \text{&}\ (m_1 >> d_2)}$ は、$\boldsymbol{m_{2R}}$ の範囲 のビットが すべて
1である $\boldsymbol{m_1}$ と $\boldsymbol{m_{2R}}$ の AND 演算 を行うので $\boldsymbol{m_{2R}}$ が計算 される
なお、$\boldsymbol{m_1 >> d_2}$ だけ で $\boldsymbol{m_{2R}}$ が計算される ので、$\boldsymbol{m_1}$ との AND 演算は不要ではない かと思った方がいるかもしれませんが、この AND 演算は 3 回目以降の手順 2 のビットマスクを 計算する際に必要となる 演算です。そのことについてはこの後で説明します。
$\boldsymbol{n_2 + d_2 = n_1}$ が成り立つことを 上図で説明 すると以下のようになります。なお、上図では $n_1$ は奇数ですが、$\boldsymbol{n_1}$ が偶数 の場合は、2 つの青線が同じ位置で重なっている ものと考えて下さい
- $\boldsymbol{n_1}$ は 青線で左右に分割 された 左のビット列のビット長 と、右端から左の青線まで のビット列の ビット長を合計した値 である
- 青線で左右に分割 されたビット列の ビット長 は どちらも $\boldsymbol{n_2}$ である
- delta swap で行う処理から、青線で左右に分割 された 右のビット列 を $\boldsymbol{d_2}$ ビット左シフト演算 すると、左のビット列の位置に重なる ので $\boldsymbol{d_2}$ は 右端から左の青線までのビット長 を表す
前回の記事で説明したように、$\boldsymbol{m_2}$ は 下記の式で計算 することができます。
$m_2 = m_{2R}\ |\ m_{2L}$
$m_{2L} = m_{2R} << d_{1}$
上記で示したように、$\boldsymbol{m = m_{2R}}$ なので、下記の式が成り立つ ことが示されました。
$\boldsymbol{m_2 = m\ | \ (m << d_1)}$
3 回目の手順 2 のビットマスクの計算処理
3 回目の手順 2 では下記の式で $\boldsymbol{n_3}$、$\boldsymbol{d_3}$、$\boldsymbol{m_3}$ が計算されます。
$n_3 = n_2\ //\ 2 = 2\ //\ 2 = 1$
$d_3 = (n_2 + 1) \ //\ 2 = 3\ //\ 2 = 1$
$m = m_2\ \text{&}\ (m_2 >> d_3)$
$m_3 = m\ | \ (m << d_2)$
下図は 上記の式 で $\boldsymbol{m_3}$ の計算の過程 を表す図です。
前回の記事と同様に、$\boldsymbol{m_3}$ を 赤線で左右に分割 したビット列を $\boldsymbol{m_{3L}}$ と $\boldsymbol{m_{3R}}$ と表記し、それらを 青線で分割 した $\boldsymbol{m_{3LL}}$、$\boldsymbol{m_{3LR}}$、$\boldsymbol{m_{3RL}}$、$\boldsymbol{m_{3RR}}$ という 4 つのビット列に分けて考えることにします。
最初の $\boldsymbol{m = m_2\ \text{&}\ (m_2 >> d_3)}$ が、$\boldsymbol{m_{3LR}}$ と $\boldsymbol{m_{3RR}}$ の範囲のビットマスク を まとめて計算 することを示します。
3 回目の手順 2 の処理では、2 回目の手順 2 の処理で 4 つに分割した $\boldsymbol{m_{3LL}}$、$\boldsymbol{m_{3LR}}$、$\boldsymbol{m_{3RL}}$、$\boldsymbol{m_{3RR}}$ の 範囲のビット列 を、それぞれ 緑線 で 左右に分割 します。
先程計算した $\boldsymbol{m_2}$ は上図からわかるように、青線で左右に分割 された 2 つのビット列の 右側の $\boldsymbol{m_{3LR}}$ と $\boldsymbol{m_{3RR}}$ の 範囲のビットが 1 になったビット列です。従って、$\boldsymbol{m_2 >> d_3}$ という右シフト演算によって 下記の計算 が行われます。
- $\boldsymbol{n_i + d_i = n_{i - 1}}$ から、$\boldsymbol{n_2 - d_3 = n_3}$ という式が成り立つ
- $\boldsymbol{m_{3RR}}$ の範囲 のビット列に 注目する と以下の事が成り立つ
-
0 番から $\boldsymbol{n_2}$ 個 の
1が並ぶ ビット列の、右端の $\boldsymbol{d_3}$ 個の1が削除 されて 残りの1が右端に並ぶ ので、$n_2 - d_3 = \boldsymbol{n_3}$ 個の1が右端に並ぶ。従って $\boldsymbol{m_{3RR}}$ の範囲のビットマスクが計算 される
-
0 番から $\boldsymbol{n_2}$ 個 の
- $\boldsymbol{m_{3LR}}$ の範囲 のビット列に 注目する と以下の事が成り立つ
- $\boldsymbol{m_{3LR}}$ の範囲 の 右端から $\boldsymbol{n_2}$ 個の
1が並ぶ ビット列の、右端の $\boldsymbol{d_3}$ 個の1が $\boldsymbol{m_{3LR}}$ の範囲の外 にずれて、残りの $\boldsymbol{n_3}$ 個の1が $\boldsymbol{m_{3LR}}$ の範囲の右端に並ぶ
- $\boldsymbol{m_{3LR}}$ の範囲 の 右端から $\boldsymbol{n_2}$ 個の
また、$\boldsymbol{m = m_2\ \text{&}\ (m_1 >> d_3)}$ によって 下記の計算 が行われます。
- $\boldsymbol{m_{3RR}}$ の範囲 のビット列に 注目する と、2 回目の手順 2 で説明したのと同じ理由から $\boldsymbol{m_{3RR}}$ の範囲 の ビットマスクが計算 される
- $\boldsymbol{m_{3LR}}$ の範囲 のビット列に 注目する と、以下の計算が行われた結果 $\boldsymbol{m_{3LR}}$ の範囲のみ の ビットマスクが計算 される
- 2 回目の手順 2 で説明したのと同じ理由から、$\boldsymbol{m_{3LR}}$ の範囲 に対しては 正しいビットマスクの値が計算 される
- $\boldsymbol{m_{3RR}}$ の場合と異なり、$\boldsymbol{m_2 >> d_3}$ という右シフト演算によって $\boldsymbol{m_{3LR}}$ の範囲外のビットが
1になるが、下記の理由から $\boldsymbol{m}$ の それらのビットはすべて0になる - $\boldsymbol{m_2}$ の $\boldsymbol{m_{3LR}}$ の範囲の右 には上図が示すように $\boldsymbol{d_2}$ 個以上の
0のビットが並ぶ - $\boldsymbol{d_3 = (d_2 + 1)\ //\ 2}$ から $\boldsymbol{d_3 ≦ d_2}$ が成り立つ ので、$\boldsymbol{m_{3LR}}$ の範囲の外にずれた $\boldsymbol{d_3}$ 個の
1のビットに 対応する $\boldsymbol{m_2}$ のビットはすべて0である - 従って、$\boldsymbol{m_{3LR}}$ の範囲外 のビットと $\boldsymbol{m_2}$ のビットの AND 演算 は すべて
0になる
上記から、$\boldsymbol{m = m_2\ \text{&}\ (m_1 >> d_3)}$ によって、$\boldsymbol{m_{3LR}}$ と $\boldsymbol{m_{3RR}}$ の範囲 のビットマスクである $\boldsymbol{m_{3LR}\ |\ m_{3RR}}$ を まとめて計算できる ことがわかります。
また、図からわかるように下記の式が成り立ちます。
$\boldsymbol{m << d_2}$
$= (m_{3LR}\ |\ m_{3RR}) << d_2$
$= m_{3LR} << d_2 + m_{3RR} << d_2$
$= \boldsymbol{m_{3LL}\ |\ m_{3RL}}$
このことから、$\boldsymbol{m << d_2}$ によって $\boldsymbol{m_{3LR}}$ と $\boldsymbol{m_{3RR}}$ の範囲 のビットマスクを まとめて計算できる ことがわかります。
上記から下記の式が成り立つので、$\boldsymbol{m_3}$ を計算できる ことがわかります。
$\boldsymbol{m\ |\ (m << d_2)}$
= $\boldsymbol{(m_{3LR}\ |\ m_{3RR})\ |\ (m_{3LL}\ |\ m_{3RL})}$
= $\boldsymbol{m_{3LR}\ |\ m_{3RR}\ |\ m_{3LL}\ |\ m_{3RL}}$
= $\boldsymbol{m_3}$
説明は省略しますが、4 回目以降の手順 2 の処理が必要な場合でも、同様の計算 が行われた結果、下記の式 で ビットマスクが正しく計算 されます。
$\boldsymbol{m = m_{i-1}\ \text{&}\ (m_{i - 1} >> d_i)}$
$\boldsymbol{m_i = m\ | \ (m << d_{i - 1})}$
reverse7 の定義
下記は上記で説明したアルゴリズムでビット列の反転処理を行う reverse7 を定義するプログラムです。関数名は前回の記事で定義した reverse6 の続きです。なお、下記のプログラムでは $\boldsymbol{n_i}$、$\boldsymbol{d_i}$ 、$\boldsymbol{m_i}$ を表すデータを length、delta、mask を更新しながら記録 しています。また、reverse6 と異なり、過去の delta の一覧を記録しておく必要はありませんが、一つ前の delta の値が必要 なので その値を prevdelta に記録 することにしました。
-
1 ~ 3 行目：
reverse7で必要となる前回の記事で定義したdelta_swapを定義する -
5 行目：仮引数
lengthには $\boldsymbol{n_0}$ が代入される -
6 行目：ビットマスクを計算する変数
maskをNoneで初期化する -
7 行目：分割したビット列の長さを表す
lengthが1になるまで繰り返し処理を行う -
8 行目：手順 2 の $\boldsymbol{d_i}$ を $\boldsymbol{n_{i-1}}$ を表す
lengthから計算 する -
9 行目：手順 2 の $\boldsymbol{n_i}$ を $\boldsymbol{n_{i-1}}$ を表す
lengthから計算 し、その値でlengthを更新する。その結果lengthには $\boldsymbol{n_i}$ が代入される -
10、11 行目：
maskがNoneの場合は 1 回目の手順 2 の処理が行われているので、$\boldsymbol{m_1 = (1 << n_1) - 1}$ の式でビットマスクを計算する -
12 ~ 14 行目：
maskがNoneでない 場合はmaskに $\boldsymbol{m_{i-1}}$ が、prevdeltaには $\boldsymbol{d_{i-1}}$ が代入されており、それを利用して先程説明した方法で $\boldsymbol{m_i}$ のビットマスクの計算を行い、その値でmaskを更新する。なお、prevdeltaはこの後の 16 行目で値を更新する -
15 行目：計算したビットマスクと
deltaを利用して delta swap の計算を行う -
16 行目：次の繰り返し処理では先ほど
deltaに代入した $\boldsymbol{d_i}$ の値が必要になるので、その値をprevdeltaに代入する
1 def delta_swap(b, mask, delta):
2 c = (b ^ (b >> delta)) & mask
3 return c ^ (c << delta) ^ b
4
5 def reverse7(b, length):
6 mask = None
7 while length > 1:
8 delta = (length + 1) // 2
9 length //= 2
10 if mask is None:
11 mask = (1 << length) - 1
12 else:
13 m = mask & (mask >> delta)
14 mask = m | (m << prevdelta)
15 b = delta_swap(b, mask, delta)
16 prevdelta = delta
17 return b
行番号のないプログラム
def delta_swap(b, mask, delta):
c = (b ^ (b >> delta)) & mask
return c ^ (c << delta) ^ b
def reverse7(b, length):
mask = None
while length > 1:
delta = (length + 1) // 2
length //= 2
if mask is None:
mask = (1 << length) - 1
else:
m = mask & (mask >> delta)
mask = m | (m << prevdelta)
b = delta_swap(b, mask, delta)
prevdelta = delta
return b
修正箇所
-def reverse6(b, length):
+def reverse7(b, length):
- deltalist = []
+ mask = None
while length > 1:
delta = (length + 1) // 2
length //= 2
- mask = (1 << length) - 1
- for d in deltalist[::-1]:
- mask |= mask << d
+ if mask is None:
+ mask = (1 << length) - 1
+ else:
+ m = mask & (mask >> delta)
+ mask = m | (m << prevdelta)
b = delta_swap(b, mask, delta)
prevdelta = delta
return b
下記は 前回の記事先程と同じ反転処理 を reverse7 で行うプログラムです。実行結果の見た目だけでは正しいかどうかがわかりづらいと思いましたので、前回の記事で定義した reverse1 と同じ結果になる事を確認できる ようにしました。実行結果の reverse1 との比較がすべて等しいことから reverse7 が正しい処理を行う ことが確認できました。
def reverse1(b, length):
result = 0
for i in range(length):
if b & (1 << i):
result |= 1 << (length - i - 1)
return result
b = 0b01001101
for length in range(8, 17):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse7(b, length):0{length}b}")
print(reverse7(b, length) == reverse1(b, length))
実行結果
bit length = 8
0b01001101
0b10110010
True
bit length = 9
0b001001101
0b101100100
True
bit length = 10
0b0001001101
0b1011001000
True
bit length = 11
0b00001001101
0b10110010000
True
bit length = 12
0b000001001101
0b101100100000
True
bit length = 13
0b0000001001101
0b1011001000000
True
bit length = 14
0b00000001001101
0b10110010000000
True
bit length = 15
0b000000001001101
0b101100100000000
True
bit length = 16
0b0000000001001101
0b1011001000000000
True
下記は前回の記事と同様の方法で reverse7 の 処理時間を計測 するプログラムです。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
%timeit reverse7(b, length)
実行結果
bit length = 10
1.16 μs ± 8.93 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
3.05 μs ± 15.5 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
6.45 μs ± 11.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 10000
34.4 μs ± 917 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 100000
261 μs ± 1.2 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 1000000
3.58 ms ± 37.9 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
下記は 今回の記事の改良を行う前の reverse6 と上記の実行結果をまとめた表です。
| ビット長 | reverse6 |
倍率 | reverse7 |
倍率 |
|---|---|---|---|---|
| 10 | 1.6 | 1.2 | ||
| 100 | 4.6 | 2.9 | 3.1 | 2.6 |
| 1,000 | 10.1 | 2.2 | 6.5 | 2.1 |
| 10,000 | 39.7 | 3.9 | 34.4 | 5.3 |
| 100,000 | 239.0 | 6.0 | 261.0 | 7.6 |
| 1,000,000 | 2,590.0 | 10.8 | 3,580.0 | 13.7 |
上記の結果から、ビット長が 10,000 以下 の場合は reverse7 のほうが処理速度が高速 になりますが、100,000 以上になる逆に低速になる ことが確認できました。このことから、ビット長 が 10,000 と 100,000 の間のどこか で reverse6 と reverse7 の 処理速度が逆転する ことがわかります。
ビット長が非常に大きい場合に reverse7 のほうが遅くなる理由の検証
ビット長が長くなる と reverse7 の方が遅くなる のは筆者も意外だったのですが、その理由を検証した結果、おそらく 下記が原因ではないか と思われます。
例えば ビット長が 16 の場合の 最後の 4 回目の手順 2 の処理は、reverse6 では 下記の手順でビットマスクが計算 されます。なお、式が長くなるので $n_i$ や $d_i$ などの計算式は省略します。また、データのビット長を明確にする ために 2 進数の先頭の 0 は省略 しました。
mask = (1 << 1) - 1 = 0b1
mask = 0b1 | (0b1 << 2) = 0b101
mask = 0b101 | (0b101 << 4) = 0b1010101
mask = 0b1010101 | (0b1010101 << 8) = 0b101010101010101
最初の式を除くと、上記では 上から順番 に ビット長が 2、4、8 のビット列 に対する OR 演算 と 左シフト演算 が 1 回ずつ行われる ことがわかります。
一方、reverse7 では 下記の手順でビットマスクが計算 されます。
m = 0b11001100110011 & (0b11001100110011 >> 1) = 0b1000100010001
mask = 0b1000100010001 | (0b1000100010001 << 2) = 0b101010101010101
上記では 上から順番 に ビット長が 14 と 13 のビット列 に対する AND 演算 と 左または右シフト演算 が 1 回ずつ行われる ことがわかります。
上記から 最後の手順 2 の処理では reverse6 のアルゴリズムは 計算式の数は多い が、計算するビット列 の ビット長が短い ことがわかります。一方、reverse7 のアルゴリズムは 計算式の数は常に 2 回 ですが、計算するビット列 の ビット長 が reverse6 の場合と比較して 約 2 倍以上 になることがわかります。
前回の記事 で検証したように、Python の AND 演算 は ビット長が小さい場合 は ビット長に比例するよりも緩やか に 処理速度が増加 しますが、ビット長が長くなる と ビット長にほぼ比例 するようになります。この性質は上記で利用している OR 演算、右シフト演算、左シフト演算 の場合も 同様 です1。そのため、ビット長が 100,000 のように 非常に長くなる と、長いビット長の演算を 2 回 行う reverse7 の方 が、短いビット長の演算を複数回 行う reverse6 よりも 処理時間が長くなってしまう ことになるようです。
なお、正方形 のゲーム盤の ビットボード の ビット長が 10,000 を超える のは ゲーム盤のサイズ が 100 x 100 を超える場合 なので、ほとんどのゲーム のゲーム盤を表す ビットボードの反転処理 は、reverse7 のほうが処理速度が速くなる と思います。
上記で「思います」のようにあいまいな言い方をしたのは、上記が計算式から考えた理屈であるからです。実際には他にも reverse7 が遅くなる原因があるかもしれませんので、正確な原因を解明するためにはより本格的な検証を行う必要があります。例えば、かなり専門的な知識が必要になるのでおおざっぱな説明になりますが、扱うデータの量が多くなると、CPU のキャッシュという仕組みが原因で処理速度が遅くなるという現象があるので、それが影響している可能性があります。
なお、CPUのキャッシュの効率を意識したプログラミングは、プログラミングの中級者にとっても難しいのではないかと思います。また、正直に言うと筆者も完全に理解しているわけではないので、本記事では扱わないことにします。
また、今後の記事でも言及する予定ですが、Python は計算処理が速い言語ではないので、処理速度を最速にしたいのであれば Python より処理速度が高速な別の言語でプログラムを実装したほうがよいでしょう。ただし、本記事はタイトルが示すように Python で 〇×ゲームの AI を実装することを目的とした記事なので、Python での実装を続けることにします。
分割統治法による全ビットの交換を利用した方法の改良
ここまでで紹介した reverse6 や reverse7 の ビット列の反転アルゴリズム は、おそらく 一般的にはほとんど紹介されていない 方法ではないかと思います。分割統治法を利用した一般的に良く紹介されているビット列の反転を行うアルゴリズムを紹介します。
全ビットを交換するアルゴリズム
delta swap は、ビット列の中で 間隔が等しい複数のビット を まとめて効率よく交換 するアルゴリズムです。delta swap の 別の特徴 としては、ビット列の中で 移動しないビットが存在しても良い というものがあり、その性質を満たすため に以前の記事で説明した XOR 演算の性質を利用 していますが、おそらく多くの方にとって delta swap のアルゴリズムは直観的でなく、わかりづらいと思っているのではないかと思います。
ビット列の ビットを交換する際 に、すべてのビットを交換する ことで 移動しないビットが存在しない場合 は、delta swap よりも直観的 で、高速 な下記のアルゴリズムがあります。なお、下記のアルゴリズムの名称を調べてみたのですがわからなかったので、本記事では 全ビットの交換アルゴリズム と表記することにします。
- 交換するビットの組の数 を $\boldsymbol{n}$（$n ≧ 1$）とする
- 交換するビットの組 を $\boldsymbol{x_i}$、$\boldsymbol{y_i}$（$\boldsymbol{0 ≦ i < n}$、$\boldsymbol{x_i > y_i}$）とする。ただし、交換するビットの番号 を表す $\boldsymbol{x_i}$ と $\boldsymbol{y_i}$ がすべて異なる ものとする
- すべての $\boldsymbol{i}$ に対して $\boldsymbol{x_i - y_i = delta}$ となる 整数 $\boldsymbol{delta}$ が存在する
- すべてのビット が 交換するビットに含まれる ものとする。
上記の条件 1 ~ 3 は以前の記事で説明した delta swap の条件 で、4 番の条件 がビット列の中で 移動しないビットが存在しない ことを表します。
上記の条件が満たされている場合は、下記のアルゴリズムで 任意のビット列 b に対して上記の ビットの値を交換した値の計算 を行うことができます。
-
すべての $\boldsymbol{x_i}$ 番のビットを
1、それ以外のビットを0とした ビットマスクmask1を計算 する -
すべての $\boldsymbol{y_i}$ 番のビットを
1、それ以外のビットを0とした ビットマスクmask2を計算 する -
((b & mask1) >> delta) | ((b & mask2) << delta)という式で計算できる
行われる計算の説明
具体例として、0b01001101 に対して上記のアルゴリズムで「0、1、2、3 番」と「4、5、6、7 番」の ビットをまとめて交換 する処理を説明します。
交換する ビットの間隔 は 4 なので delta = 4、上記の 手順 1、2 から mask1 = 0b11110000、mask2 = 0b00001111 になります。
下記は ((b & mask1) >> delta) の 処理を表す図 です。図の色 は以下の意味を表します。
| 色 | 意味 |
|---|---|
| 水色 | 交換する $x_i$ に対応するビット |
| 緑色 | 交換する $y_i$ に対応するビット |
| 黄色 | ビットマスクの 1 のビット |
| 白色 | 必ず 0 になるビット |
上図から、以下の事がわかります。
-
b & mask1によってbから $\boldsymbol{x_i}$ のビットの値を 取り出したビット列を計算 する -
(b & mask1) >> deltaによってbの $\boldsymbol{x_i}$ のビットの値を $\boldsymbol{y_i}$ の位置に移動したビット列を計算 する
下記は ((b & mask2) << delta) と 残りの処理 を表す図です。
上図から先程と同様の理由で (b & mask2) << delta によって b の $\boldsymbol{y_i}$ のビットの値を $\boldsymbol{x_i}$ の位置に移動したビット列が計算 されることがわかります。
また、先程計算した (b & mask1) >> delta と (b & mask2) << delta の OR 演算 によって b の $\boldsymbol{x_i}$ と $\boldsymbol{y_i}$ のビットが 交換された値が計算される ことがわかります。
別の例として「0、1、4、5 番」と「2、3、5、7 番」のビットを交換する処理を説明します。交換する ビットの間隔は 2 なので delta = 2、上記の手順 1、2 から mask1 = 0b11001100、mask2 = 0b00110011 になります。
下記は (b & mask1) >> delta の処理を表す図です。
上図から (b & mask1) >> delta によって、先程と同様 に b の $\boldsymbol{x_i}$ のビットの値を $\boldsymbol{y_i}$ の位置に移動 した ビット列が計算 されることがわかります。
図は同様なので省略しますが、(b & mask2) << delta によって b の $\boldsymbol{y_i}$ のビットの値を $\boldsymbol{x_i}$ の位置に移動 した ビット列が計算 され、(b & mask1) >> delta と (b & mask2) << delta の OR 演算 によって b の $\boldsymbol{x_i}$ と $\boldsymbol{y_i}$ の ビットが交換された値が計算 されます。
なお、ビット長が 8 のビット列の ビットを全交換する例 としては もう一つ「0、2、4、6 番」と「1、3、5、7 番」がありますが、上記と同様 なので説明は省略します。興味がある方は実際に確認してみて下さい。
delta swap と同じ処理を行うアルゴリズム
上記のアルゴリズム に、移動しないビットの値を 1 とする mask3 という ビットマスクを加える ことで、下記の式で delta swap と同じ計算 を行うことができます。
((b & mask1) >> delta) | ((b & mask2) << delta) | (b & mask3)
新たに加わった b & mask3 は 移動しないビットの値だけを計算 するので、先程の ((b & mask1) >> delta) | ((b & mask2) << delta) との OR 演算 を行うことで、移動しないビットが存在 する場合の delta swap と同じ計算 を行うことができます。
上記のアルゴリズムも名称がわからなかったので、本記事では delta swap と同じ処理を行うアルゴリズム と表記することにします。
処理時間の比較
delta swap と上記で紹介した 2 種類のアルゴリズム の 処理時間を比較 することにします。
-
delta swap は 全ビットの交換処理を行うこともできる ので、
0b01001101に対して delta swap と 全ビットの交換アルゴリズム で 「0、1、2、3 番」と「4、5、6、7 番」のビットを交換する -
0b01001101に対して delta swap と delta swap と同じ処理を行うアルゴリズム で 「0、1、2 番」と「5、6、7 番」のビットを交換する
下記は 前者の処理時間を計測 するプログラムです。
# 計算に必要なデータを変数に代入する
b = 0b01001101
mask1 = 0b11110000
mask2 = 0b00001111
delta = 4
%%timeit
# delta swap の計算
c = (b ^ (b >> delta)) & mask2
c ^ (c << delta) ^ b
実行結果
136 ns ± 0.166 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
# 全ビットの交換アルゴリズム
%timeit ((b & mask1) >> delta) | ((b & mask2) << delta)
実行結果
120 ns ± 0.0841 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
下記は 後者の計算 を行うプログラムで、下記の mask1、mask2、mask3、delta で正しい計算が行われる ことが確認できます。
b = 0b01001101
mask1 = 0b11100000
mask2 = 0b00000111
mask3 = 0b00011000
delta = 5
# delta swap の計算
c = (b ^ (b >> delta)) & mask2
print(f"0b{c ^ (c << delta) ^ b:08b}")
print(f"0b{((b & mask1) >> delta) | ((b & mask2) << delta) | (b & mask3):08b}")
実行結果
0b10101010
0b10101010
下記は 後者の処理時間を計測 するプログラムです。
%%timeit
# delta swap の計算
c = (b ^ (b >> delta)) & mask2
c ^ (c << delta) ^ b
実行結果
135 ns ± 0.236 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
# delta swap と同じ処理を行うアルゴリズム
%timeit ((b & mask1) >> delta) | ((b & mask2) << delta) | (b & mask3)
実行結果
175 ns ± 1.16 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
下記は上記の実行結果をまとめた表です。
| delta swap | 今回の記事のアルゴリズム | |
|---|---|---|
| 全ビットの交換 | 136 ns | 120 ns |
| 一部のビットの交換 | 135 ns | 175 ns |
上記から、全ビットを交換する場合 は 今回の記事で紹介したアルゴリズム のほうが、一部のビットを交換 する場合は delta swap のほうが高速 であることが確認できました。また、同じ処理を行うので当然ですが、delta swap は 処理時間がほぼ同じ になります。
上記のような結果になる理由 はそれぞれのアルゴリズムで 行われる演算の回数を比較 することで確認できます。
下記の delta swap の計算式では XOR 演算が 3 回、AND 演算が 1 回 、右シフト演算が 1 回、左シフト演算が 1 回 行われます。
c = (b ^ (b >> delta)) & mask2
c ^ (c << delta) ^ b
下記の 全ビットの交換アルゴリズム の計算式では、AND 演算 が 2 回、OR 演算が 1 回、右シフト演算が 1 回、左シフト演算が 1 回 行われます。
((b & mask1) >> delta) | ((b & mask2) << delta)
下記の delta swap と同じ処理を行うアルゴリズム では、AND 演算 が 3 回、OR 演算が 2 回、右シフト演算が 1 回、左シフト演算が 1 回 行われます。
((b & mask1) >> delta) | ((b & mask2) << delta) | (b & mask3)
下記は 上記をまとめた表 です。
| XOR | AND | OR | 右シフト | 左シフト | |
|---|---|---|---|---|---|
| delta swap | 3 | 1 | 0 | 1 | 1 |
| 全ビットの交換 | 0 | 2 | 1 | 1 | 1 |
| delta swap と同じ演算 | 0 | 3 | 2 | 1 | 1 |
上記からいずれの場合も 右シフトと左シフト演算の回数は同じ ですが、XOR、AND、OR 演算の回数が異なる ことがわかります。Python の XOR、AND、OR 演算 は計算する 値のビット長が同じ であれば、下記のプログラムの実行結果のように 処理時間はほぼ同じ になります2。
%timeit mask1 & mask2
%timeit mask1 | mask2
%timeit mask1 ^ mask2
実行結果
29.5 ns ± 0.145 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
29.8 ns ± 0.152 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
29.9 ns ± 0.107 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
そこで、先程の表の XOR、AND、OR 演算の合計を計算 すると下記の表のようになります。
| XOR、AND、OR | 右シフト | 左シフト | |
|---|---|---|---|
| delta swap | 4 | 1 | 1 |
| 全ビットの交換 | 3 | 1 | 1 |
| delta swap と同じ演算 | 5 | 1 | 1 |
上記の表から 演算処理の回数 は下記のように、先程計測した 処理時間の順番と同じになる ことが確認でき、全ビットを交換する場合 は 全ビットの交換アルゴリズム を、全ビットを交換しない場合 は delta swap を利用したほうが良い ことが確認できました。
全ビットの交換 ＜ delta swap ＜ delta swap と同じ処理
なお、処理時間が非常に重要でない場合は、わかりやすさを重視して delta swap を利用しないアルゴリズムを利用しても良いと思います。
厳密には処理時間は演算の回数だけでは決まらない場合がありますが、大雑把には演算の回数に比例することが多いと考えても良いと思います。
ビットマスクの個数の削減
全ビットを交換するアルゴリズム の下記の式では 2 種類のビットマスクが必要 になるので、reverse7 と比較 して ビットマスクの計算処理が増える という問題があります。
((b & mask1) >> delta) | ((b & mask2) << delta)
この問題を解決する方法として、下記の性質 から ビットマスクを mask2 の 1 つに減らす という方法があります。わかりづらいと思った方は図を描いてみると良いでしょう。
-
((b & mask1) >> delta)はb & mask1の計算結果をdeltaビット右にシフト するという演算であるが、bとmask1を それぞれdeltaビット右にシフトしてから その 結果を AND 演算 しても 同じ計算結果になる ので 下記の式が成り立つ3
((b & mask1) >> delta) = (b >> delta) & (mask1 >> delta) -
mask1をdeltaビット右にシフト するとmask2になる ので 下記の式が成り立つ
mask2 = mask1 >> delta - 上記から
((b & mask1) >> delta) = (b >> delta) & mask2が成り立つので、下記のように ビットマスクをmask2の 1 つに減ら すことができる
((b & mask1) >> delta) | ((b & mask2) << delta)
= ((b >> delta) & mask2) | ((b & mask2) << delta)
また、この mask2 は delta swap で利用するビットマスクと同じもの なので、delta swap と同じ方法で計算 することができます。
全ビットの交換アルゴリズムを利用したビット列の反転処理
delta swap を利用 した ビット列を反転 するアルゴリズムでは、ビット列 を下記のように 分割して交換する処理 を行います。
- ビット長が偶数 の場合はビット列を 均等に分割して交換 する
- ビット長が奇数 の場合はビット列を 真ん中のビット とその 左右のビットに 3 分割 し、その 左右のビット列を交換 する
上記から ビット長が偶数 の場合は すべてのビットを交換する ので、全ビットの交換アルゴリズムを利用できる ことがわかりますが、ビット長が奇数 の場合は 真ん中のビットを移動せずに 左右のビットを 交換する必要がある ので delta swap を利用する必要 があります。
従って、分割したビット列のビット長 が 常に偶数になる場合 は delta swap より高速な 全ビットの交換アルゴリズムを常に利用できる ことになります。また、そのような場合は 分割前 のビット列のビット長が 分割後の 2 倍になる ので、最初のビット列 の ビット長 は 2 を複数回掛け算 した値である $\boldsymbol{2^n}$ という式で表される 2 のべき乗 になります。
従って、ビット列の反転処理 を行う際に ビット長 を 2 のべき乗の値として計算 することで、全ビットの交換アルゴリズムだけ を使ってビット列を反転することができます。
ただし、そうやって計算したビット列 は、求めたいビット列とは異なる値 になります。例えば 0b00001101 を反転する際 に、ビット長を 5 と $2^3 =$ 8 として計算すると、下記のプログラムの実行結果のように 異なる値が計算 されます。
# ビット長を 5 として反転する
print(f"0b{reverse7(0b00001101, 5):08b}")
# ビット長を 8 として反転する
print(f"0b{reverse7(0b00001101, 8):08b}")
実行結果
0b00010110
0b10110000
下図は 上記の計算を表す図 です。ビット長が 5 を超える、反転前の 5 から 7 番の 0 のビットに対応するビット を 緑色 で塗りつぶしました。また、反転前の 0 から 4 番のビット を 反転したビット を 赤枠 で表記しました。
上図から以下の事がわかります。
- ビット長が異なっていても 0 ~ 5 番を反転したビット を表す 赤枠の並びは同じ である
-
ビット長を 8 として反転した場合は 左端の 3 つの緑色の
0のビット が 右端に移動 する - 上図のように、ビット長を 8 として 反転した値 を、ビット長の差 である 8 - 5 = 3 ビット右にシフト する事で、ビット長を 5 として 反転した値を計算 できる
全ビットの交換によるビット列の反転処理のアルゴリズム
上記から、全ビットの交換アルゴリズムのみ を利用した ビット列 b を ビット長が n のビット列として 反転するアルゴリズム は以下のようになります。
- $\boldsymbol{n ≦ 2^m}$ となる 最小の整数 $\boldsymbol{m}$ を求める
- b を ビット長が $\boldsymbol{2^m}$ のビット列として 全ビットの交換アルゴリズム を利用して反転する
- 上記で計算した値を $\boldsymbol{2^m - n}$ ビット右にシフト する
従って、このアルゴリズムでは $\boldsymbol{n ≦ 2^m}$ となる 最小の整数 $\boldsymbol{m}$ を求める必要 があります。$m$ を求める方法について少し考えてみて下さい。
$m$ が $n ≦ 2^m$ となる最小の整数でなくても正しい値を計算できますが、繰り返し処理の回数が増えるので処理時間が長くなります。
m を求めるアルゴリズム
以前の記事で紹介した 対数 を利用して計算する方法もありますが、対数がわかりづらいと思う方 は、$n$ から $m$ を求めるのではなく、逆に $\boldsymbol{m}$ が決まった時 の $\boldsymbol{n}$ のとりうる範囲 について考えてみると良いでしょう。
$\boldsymbol{m}$ は $\boldsymbol{n ≦ 2^m}$ となる 最小の整数 なので $\boldsymbol{n}$ は $\boldsymbol{2^{m-1}}$ より大きな整数 です。$\boldsymbol{2^{m-1}}$ より大きな最小の整数 は $\boldsymbol{2^{m-1}} + 1$ なので、$\boldsymbol{2 ^{m-1} + 1 ≦ n}$ であることがわかります。
この不等式と $\boldsymbol{n ≦ 2^m}$ を組み合わせる と、下記の式が成り立つ ことがわかります。
$\boldsymbol{2^{m-1} + 1 ≦ n ≦ 2^m}$
$\boldsymbol{2 ^ {m-1}}$ と $\boldsymbol{2^m}$ を 2 進数で表現 すると、それぞれ 1 の後ろ に $\boldsymbol{m - 1}$ と $\boldsymbol{m}$ 個の 0 が並んだ値 になります。例えば $\boldsymbol{m=5}$ の場合は $\boldsymbol{2 ^ {m-1} = 0b10000}$、$\boldsymbol{2 ^ {m} = 0b100000}$ です。従って、$\boldsymbol{m = 5}$ の場合は 下記の式が成り立ちます。
$\boldsymbol{0b10001 ≦ n ≦ 0b100000}$
次に、上記の不等式から それぞれ 1 を引く と下記の不等式になります。
$\boldsymbol{2^{m-1} ≦ n - 1 ≦ 2^m - 1}$
$\boldsymbol{m = 5}$ の場合は上記の不等式は下記のようになります。
${0b10000 ≦ n - 1 ≦ 0b11111}$
上記の $\boldsymbol{n - 1}$ の範囲の値を 以前の記事 で説明した、先頭の 1 のビットまで の ビット長を計算 する bit_length メソッドで計算すると $\boldsymbol{m}$ と同じ 5 になります。また、0b10000 より 1 小さい整数 は 0b1111 なので bit_length の値 は 4 に、0b11111 より 1 大きい整数 は 0b100000 なので bit_length の値は 6 になります。従って、bit_length の値が $\boldsymbol{m}$ と同じ になる 整数の範囲 は $\boldsymbol{n - 1}$ の範囲に等しい ことがわかります。
この性質 は $\boldsymbol{m}$ が任意の正の整数でも成り立つ ので、下記のプログラム で n に対する m を計算 することができます。
m = (n - 1).bit_length()
例えば $\boldsymbol{2 ^ 5 = 32}$ なので、$\boldsymbol{n = 32}$ の場合は $\boldsymbol{m = 5}$、$\boldsymbol{n = 33}$ の場合は $\boldsymbol{m = 6}$ になります。下記のプログラムの実行結果から上記の式で 正しく計算されることが確認 できます。
n = 32
print((n - 1).bit_length())
n = 33
print((n - 1).bit_length())
実行結果
5
6
対数を利用して $m$ を計算する方法について説明します。
対数は単調増加するという性質があるので、不等式の各値に対して対数を計算しても不等式は成立します。そこで、$2^{m-1} < n ≦ 2^m$ に対して 2 を底とする対数を計算すると以下のようになります。
$m-1 < \log_2 n ≦ m$
従って $m$ の数値を切り上げた値を $\lceil x \rceil$ と表記すると、$m$ は下記の式で計算することができます。
$m = \lceil \log_2{n} \rceil$
python では切り上げと 2 を底とする対数は math モジュールの ceil と log2 という関数で計算できるので、下記のプログラムで m を計算することができます。
m = math.ceil(math.log2(n))
下記は n が 32 と 33 の場合に m を計算するプログラムで、実行結果から正しい計算が行われることが確認できます。
import math
n = 32
print((math.ceil(math.log2(n))))
n = 33
print((math.ceil(math.log2(n))))
実行結果
5
6
下記は bit_length を利用した場合と上記の方法で m を計算する処理時間を計測するプログラムです。実行結果から bit_lentgh を利用した場合の方が処理速度が 2 倍以上高速であることが確認できました。これは、対数の計算が bit_length の計算よりも複雑で時間がかかることが原因です。また、本記事で対数を利用する方法を最初に紹介しなかった理由はこの処理速度の差にあります。
import math
%timeit (n - 1).bit_length()
%timeit (math.ceil(math.log2(n)))
実行結果
35.1 ns ± 0.171 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
80.9 ns ± 0.229 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
reverse8 の定義
下記は上記で説明したアルゴリズムで処理をおこなう reverse8 を定義したプログラムです。mask の計算方法 は reverse7 と同じ なので説明を省略します。
なお、下記のプログラムでは reverse7 からの 修正を少なくするため に、length には $\boldsymbol{n}$ ではなく、$\boldsymbol{2^m}$ を代入 することにしました。ただし、$\boldsymbol{n}$ の値は $\boldsymbol{2^m -n}$ を計算する際に必要 となるので lengthorig という仮引数に代入することにしました。
-
1 行目：仮引数
lengthをlengthorigに修正した -
3 行目：
lengthorig以上 の 最小の 2 のべき乗の値 を計算してlengthに代入 する -
4 行目：最後の計算結果 を 右シフトするビット数 を計算する。ビット長（length）の差分（differnce）なので
ldiffという名前の変数に代入した -
6 ~ 12 行目：
lengthは常に偶数 なので、deltaは 常にlengthと同じ値になる ため、deltaとprevdeltaを廃止 してlengthとprevlengthに置き換えた - 12 行目：delta swap を 全ビットの置換のアルゴリズムの処理 に 置き換えた
-
14 行目：計算結果 を
ldiffビット右にシフト した値を返すように修正した
1 def reverse8(b, lengthorig):
2 mask = None
3 length = 1 << (lengthorig - 1).bit_length()
4 ldiff = length - lengthorig
5 while length > 1:
6 length //= 2
7 if mask is None:
8 mask = (1 << length) - 1
9 else:
10 m = mask & (mask >> length)
11 mask = m | (m << prevlength)
12 b = ((b >> length) & mask) | ((b & mask) << length)
13 prevlength = length
14 return b >> ldiff
行番号のないプログラム
def reverse8(b, lengthorig):
mask = None
length = 1 << (lengthorig - 1).bit_length()
ldiff = length - lengthorig
while length > 1:
length //= 2
if mask is None:
mask = (1 << length) - 1
else:
m = mask & (mask >> length)
mask = m | (m << prevlength)
b = ((b >> length) & mask) | ((b & mask) << length)
prevlength = length
return b >> ldiff
修正箇所
-def reverse7(b, length):
+def reverse8(b, lengthorig):
mask = None
+ length = 1 << (lengthorig - 1).bit_length()
+ ldiff = length - lengthorig
while length > 1:
- delta = (length + 1) // 2
length //= 2
if mask is None:
mask = (1 << length) - 1
else:
- m = mask & (mask >> delta)
+ m = mask & (mask >> length)
- mask = m | (m << prevdelta)
+ mask = m | (m << prevlength)
- b = delta_swap(b, mask, delta)
+ b = ((b >> length) & mask) | ((b & mask) << length)
+ prevdelta = delta
- prevlength = length
return b >> ldiff
下記は 先ほどとほぼ同じ反転処理 を reverse8 で行うプログラムです。ただし、繰り返し処理の回数が変化 しても 正しい処理が行われることを確認できる ように、繰り返し処理の回数 が 4 回から 5 回に変化 する ビット長 が $\boldsymbol{2^4 + 1 = 17}$ の場合の計算も行う ようにしました。実行結果から reverse8 が正しい処理を行う ことが確認できました。
b = 0b01001101
for length in range(8, 18):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse8(b, length):0{length}b}")
print(reverse8(b, length) == reverse1(b, length))
実行結果
bit length = 8
0b01001101
0b10110010
bit length = 9
0b001001101
0b101100100
bit length = 10
0b0001001101
0b1011001000
bit length = 11
0b00001001101
0b10110010000
bit length = 12
0b000001001101
0b101100100000
bit length = 13
0b0000001001101
0b1011001000000
bit length = 14
0b00000001001101
0b10110010000000
bit length = 15
0b000000001001101
0b101100100000000
bit length = 16
0b0000000001001101
0b1011001000000000
下記は先ほどと同様の方法で reverse8 の 処理時間を計測 するプログラムです。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
%timeit reverse8(b, length)
実行結果
bit length = 10
1.44 μs ± 12.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
2.93 μs ± 10.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
5.61 μs ± 9.49 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 10000
43.9 μs ± 85.5 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 100000
351 μs ± 2.24 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 1000000
3.57 ms ± 15.6 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
下記は先ほどの reverse6、reverse7 と上記の実行結果をまとめた表です。
| ビット長 | reverse6 |
倍率 | reverse7 |
倍率 | reverse8 |
倍率 |
|---|---|---|---|---|---|---|
| 10 | 1.6 | 1.2 | 1.4 | |||
| 100 | 4.6 | 2.9 | 3.1 | 2.6 | 2.9 | 2.0 |
| 1,000 | 10.1 | 2.2 | 6.5 | 2.1 | 5.6 | 1.9 |
| 10,000 | 39.7 | 3.9 | 34.4 | 5.3 | 43.9 | 7.8 |
| 100,000 | 239.0 | 6.0 | 261.0 | 7.6 | 351.0 | 8.0 |
| 1,000,000 | 2,590.0 | 10.8 | 3,580.0 | 13.7 | 3,570.0 | 10.2 |
上記から、ビット長が 100、1000 の場合は reverse8 が処理速度が最速 になりますが、ビット長が 10,000 と 100,000 の場合は 処理速度が最も遅くなる ことが確認できました。
ビット長が 10 の場合に reverse8 よりも遅くなる理由 は、reverse7 では行わない 最初の length = 1 << (lengthorig - 1).bit_length() と最後の return b >> ldiff の処理によるものだと思います。ビット長が短い場合 は 繰り返し処理の回数が少ない ので、delta swap と 全ビットの交換アルゴリズム の 処理時間の差 よりも、おそらく 上記の処理 による 処理時間の増加の方が多い ことが原因だと思います。
ビット長が 10,000 以上の場合に 処理速度が遅くなる理由 は、reverse8 では reverse7 以上のビット長 で 計算を行う ことが原因だと思います。
$\boldsymbol{2^{m-1} + 1 ≦ n ≦ 2 ^ m}$ なので、reverse7 と reverse8 の ビット長の差 は 0 以上 $2 ^ m - 2^{m-1} + 1 = \boldsymbol{2 ^ {m - 1} - 1}$ 以下になります。そのため、n が大きくなって m 大きくなるほど、ビット長の差の最大値も非常に大きく なります。ビット長の差が大きい場合 は 同じ式 であっても 処理時間が長くなる ため、reverse8 の方が 処理速度が遅くなります。
例えば ビット長が 10,000 の場合は reverse8 では 1 << (10000 - 1).bit_length() = 16384 のビット長 で反転処理を行うので、reverse7 の 1.5 倍以上 の 6384 ビットも長いビット長 で反転処理が行われた結果、処理速度が reverse6 よりも遅く なります。
一方、ビット長が 1,000,000 の場合は reverse8 では 1 << (1000000 - 1).bit_length() = 1,048,576 なので、ビット長は 48,576 も長いですが、1,000,000 と比べる 約 1.04 倍にすぎない ので ビット長の差による処理時間の差 は ほとんど生じません。そのため、reverse6 よりも 少しだけ処理速度が速くなる ようです。
以下は上記の reverse8 の性質をまとめたものです。
- ビット長が約 10 の場合は
reverse6よりも少しだけ遅い - ビット長が 1000 を超えるくらいまでは
reverse6よりも速い - ビット長がそれより大きい場合は、$n$ と $2^m$ の比率が小さければ
reverser6よりも速いが、そうでなければ遅くなる
ビット長を限定した反転アルゴリズム
全ビットを交換するアルゴリズムを利用 した ビット列の反転アルゴリズム として よく見かける のが、下記のプログラムのように ビット長 を 2 のべき乗 の 32 などの ビット数に限定 した処理を行う reverse32 のような関数です。ビット長が 32 の場合に 必要なビットマスクと delta を あらかじめ計算した値 を プログラムの中に直接記述 することで、それらの計算を行う必要がなくなる 分だけ 処理速度が高速 になります。なお、ビットマスク を 2 進数で記述すると長くなりすぎるので、下記では 16 進数で記述 しました。
def reverse32(b):
b = (b >> 16) | ((b & 0x0000ffff) << 16)
b = ((b >> 8) & 0x00ff00ff) | ((b & 0x00ff00ff) << 8)
b = ((b >> 4) & 0x0f0f0f0f) | ((b & 0x0f0f0f0f) << 4)
b = ((b >> 2) & 0x33333333) | ((b & 0x33333333) << 2)
return ((b >> 1) & 0x55555555) | ((b & 0x55555555) << 1)
下記は b = 0b01001101 に対して reverse32 と reverse8 で ビット長が 32 のビット列として ビット列の反転 を行うプログラムで、同じ結果が表示される ことから reverse32 が正しい処理を行うことが確認 できました。
print(f"0b{reverse8(b, 32):032b}")
print(f"0b{reverse32(b):032b}")
実行結果
0b10110010000000000000000000000000
0b10110010000000000000000000000000
下記は 上記の処理時間を計測 するプログラムで、同じアルゴリズムで計算 を行っているにも関わらず、ビット長を限定した reverse32 のほうが 処理速度が 2 倍以上高速になることが確認 できました。
%timeit reverse8(b, 32)
%timeit reverse32(b)
実行結果
1.83 μs ± 5.08 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
840 ns ± 1.09 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
今回の記事のまとめ
今回の記事では 全ビットを交換するアルゴリズム を紹介し、それを利用したビット列を反転するアルゴリズム を紹介しました。また、ビット数が非常に大きくない場合 はそのアルゴリズムが これまで紹介したアルゴリズムの中 で 処理速度が最速 になることを示しました。
ビット列を反転するアルゴリズムはもう少しあるので、次回の記事ではそれらを紹介した後で、ビットマップの反転処理を実装することにします。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
次回の記事