目次と前回の記事
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 の一覧とこれまでに作成したデータファイルについては、下記の記事を参照して下さい。
今回の記事の内容
前回の記事では BitBoard クラスが 任意の大きさ の 〇×ゲームの ゲーム盤を扱うことができるようにするために calc_same_hashables 以外のメソッドの修正 を行いました。今回の記事では 残りの calc_same_hashabels の 修正を行うために必要な処理 について説明します。
同一局面のハッシュ可能な値を計算 する calc_same_hashables では、ゲーム盤を表す ビットボード の 左右の反転と転置 の処理を行う必要があります。以前の記事では 3 x 3 の大きさ のゲーム盤を表す ビットボード に対して、delta swap を利用 した 左右の反転と転置 の処理を行う方法を紹介しましたが、BitBoard クラスでは 任意の大きさ のゲーム盤を表す ビットボードに対する処理 を行う必要があります。今回の記事では 左右の反転 を行うために 必要な処理 として、ビット列の反転処理 について紹介します。なお、転置処理については反転処理の後で説明します。
ビット列の反転処理とは何か
2 次元のゲーム盤 を表す ビットボード の 左右の反転処理 を説明する前に、より単純なビット列 の 反転処理 について説明し、その方法を応用 して 2 次元のビットボード左右の反転処理を行う ことにします。1 次元のビット列の反転処理をどのように応用するかについては次回以降の記事で説明します。
ビット列の反転は、ビット長を指定 して ビット列の並びを逆にする という処理です。例えば下図は 8 ビット の 0b01001101 の ビット列の反転 を表す図です。図では 反転前 と 反転後 の ビットの対応をわかりやすくする ため、反転前 のビット列の ビットの色 を 0 番から 7 番までの色 が 白から徐々に黒くなる色 で塗りつぶしました。以後の図でも同様です。
同じ数値 を表す ビット列 でも、指定したビット長が変わる と 反転した際に計算される値が変化する 点に注意が必要です。例えば、上記と同じ値 である 0b1001101 を 7 ビット のビット列として 反転 を行うと、下図のように 上記とは異なるビット列が計算 されます。
下記は 0b01001101 を 7 ビット と 8 ビット のビット列として 反転 した場合の値を表す表です。異なる値が計算される ことを確認して下さい。
| ビット長 | 計算される値 |
|---|---|
| 7 | 0b1011001 |
| 8 | 0b10110010 |
このようなビット列の反転処理を行うアルゴリズムについて少し考えてみて下さい。
定義する関数の仕様
今回の記事では以前の記事と同様に、いくつかのアルゴリズム で ビット列の反転処理を行う関数を定義 し、その 処理速度を比較 することにします。
定義するビット列の反転処理を行う 関数の仕様 は以下のようにします。
-
関数名 は
reversexとする。ただし、最後の x には数字 が入る -
仮引数
bに 反転を行うビット列の値 を、lengthに ビット長を代入 する -
ビット長が
lengthのビット列 としてbを 反転した値 を計算して 返り値として返す
各ビットを順番に計算する方法
ビット長が n のビット列の 反転処理 を行う方法として、反転後の 0 番から n - 1 番まで のビットを 順番に計算する という方法が考えられます。下記の表からわかるように、ビット列の 反転処理 によって i 番 のビットは n - 1 - i 番 のビットに 移動する ので、reverse1 を下記のプログラムのように定義することができます。
| 反転前のビットの番号 | 0 | 1 | 2 | ・・・ | i | ・・・ | n - 1 |
|---|---|---|---|---|---|---|---|
| 反転後のビットの番号 | n - 1 | n - 2 | n - 3 | ・・・ | n - i - 1 | ・・・ | 0 |
-
2 行目：ビット列を反転した値を計算する変数を
0で初期化する -
3 行目：繰り返し処理によって 0 ~
length - 1番のビットに対する処理を行う -
4 行目：
bのi番のビットが1であるかどうかを、bとi番のビットのみが 1 である1 << iとの AND 演算が0でないことで判定する -
5 行目：
resultとlength - 1 - i番のビットのみが 1 である1 << (length - i - 1)の OR 演算を行う事で、resultのlength - 1 - i番のビットを 1 にする
1 def reverse1(b, length):
2 result = 0
3 for i in range(length):
4 if b & (1 << i):
5 result |= 1 << (length - i - 1)
6 return result
行番号のないプログラム
def reverse1(b, length):
result = 0
for i in range(length):
if b & (1 << i):
result |= 1 << (length - i - 1)
return result
下記は先程の図の 0b01001101 に対して 8 ~ 16 のビット長 としての 反転処理 を reverse1 で行うプログラムで、実行結果から reverse1 が正しい処理を行う ことが確認できました。
b = 0b01001101
for length in range(8, 17):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse1(b, length):0{length}b}")
実行結果
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
興味がある方は他のビット列や、ビット長で確認してみて下さい。
処理速度の検証
下記は ビット長 が 10、100、1000、10000、100000、1000000 の場合の reverse1 の 処理速度を計測 するプログラムです。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
%timeit reverse1(b, length)
実行結果
bit length = 10
1.02 μs ± 14.4 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
8.53 μs ± 30.9 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
99.8 μs ± 299 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 10000
1.34 ms ± 2.92 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 100000
22.5 ms ± 1.75 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
bit length = 1000000
1.03 s ± 3.15 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
下記は 上記の実行結果 をまとめた表です。処理時間の単位は μs で小数点以下第 2 桁で四捨五入しました。倍率 の列は、一つ上の処理時間との倍率 を表します。なお、数値の大きさをわかりやすくするために、3 桁ごとに「,」（カンマ）で区切りました。小数点と間違えない ように注意して下さい。
| ビット長 | 処理時間 | 倍率 |
|---|---|---|
| 10 | 1.0 | |
| 100 | 8.5 | 8.4 |
| 1,000 | 99.8 | 11.7 |
| 10,000 | 1,340.0 | 13.4 |
| 100,000 | 22,500.0 | 16.8 |
| 1,000,000 | 1,330,000.0 | 45.8 |
上記の表から ビット長が小さい場合 は ビットと処理時間はほぼ比例 し、ビット長が大きくなる と 比例よりも大きく増加する ことがわかります。
ただし、〇× ゲームの ビットボードのビット数 はゲーム盤の マスの数と同じ なので、100 × 100 という 巨大なゲーム盤 でもビットボードの ビット数は 10000 に過ぎません。そのため、〇×ゲームに限らず 多くのゲーム のゲーム盤を表す ビットボード の reverse1 による反転処理の 処理時間 は、上記の表から マスの数にほぼ比例する と考えて良いでしょう。
ビット列の長さと処理時間が比例しない理由
reverse1 は ビット長の数 だけ 繰り返し処理 を行うので、処理時間 は ビット長に比例するはず だと思った人がいるかもしれませんので、reverse1 の処理時間 がビット列の ビット長が大きく なると、ビット長と比例しなくなる理由 について説明します。
その理由は、これまでの記事で何度か言及してきたように、CPU が 一度に行うことができる ビット演算を含む様々な演算の ビット数が限られている ため、ビット長が増える と 演算の処理時間も増える からです。
下記はそのことを検証するプログラムで、ビット長 が 10、100、1000、10000、100000、1000000 のビット列の 加算と AND 演算 の処理時間を計測するプログラムです。〇× ゲームではビットボードの乗算は行わないので検証を行っていませんが、興味がある方は乗算などの他の演算の処理速度も計測してみて下さい。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
b1 = 1 << (length - 1)
b2 = (1 << length) - 1
print(f"bit length = {length}")
print("加算")
%timeit b1 * b2
print("AND 演算")
%timeit b1 & b2
print()
実行結果
bit length = 10
加算
35.8 ns ± 0.143 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
AND 演算
42.7 ns ± 0.226 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
bit length = 100
加算
75 ns ± 0.934 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
AND 演算
49.6 ns ± 0.133 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
bit length = 1000
加算
1.25 μs ± 21.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
AND 演算
58.7 ns ± 0.997 ns per loop (mean ± std. dev. of 7 runs, 10,000,000 loops each)
bit length = 10000
加算
16.7 μs ± 47.7 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
AND 演算
209 ns ± 1.53 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100000
加算
219 μs ± 7.05 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
AND 演算
1.27 μs ± 2.98 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 1000000
加算
2.95 ms ± 8.89 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
AND 演算
11.8 μs ± 16.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
下記は上記の 実行結果をまとめた表 で単位は ns で小数点以下第一で四捨五入しました。
| ビット長 | 加算 | AND 演算 |
|---|---|---|
| 10 | 36 | 43 |
| 100 | 75 | 50 |
| 1,000 | 1250 | 59 |
| 10,000 | 16,700 | 209 |
| 100,000 | 219,000 | 1,270 |
| 1,000,000 | 2,950,000 | 11,800 |
かなり専門的で難しい話になるので理由は省略しますが、表から以下の事が確認できます。
- AND 演算のほうが 繰上りの計算を行う必要がある 加算よりも処理が単純 なので 処理速度が速い
- ビット長が増える と加算と AND 演算の 処理時間も増える
- 加算 と AND 演算 はビット長が 一定以下 の場合は 処理時間 が ビット長に比例 するよりも 緩やかに増える
- 加算 はビット長が 一定以上大きく なると 処理時間 が ビット長に比例 するよりも 大きく増える
- AND 演算 はビット長が 大きくなる と 処理時間がビット長にほぼ比例 するようになる
演算の処理時間 が ビット長が増えると長くなる ということは、reverse1 内での 1 回の繰り返しの処理時間 が その分だけ増える ということです。例えば、実際には違いますが、仮に n ビット のデータの 演算の処理時間 t が ビット長に比例 する場合は $\boldsymbol{t = an}$（ただし、$a > 0$）という 式で表されます。reverse1 では ビット長の回数だけ繰り返し処理を行う ので、その仮定が正しい場合の演算の 全体の処理時間 は $t = an × n = \boldsymbol{an^2}$ のように、ビット長の 2 乗に比例 する処理時間がかかります。
各ビットを順番に計算する別のアルゴリズム
各ビットを順番に計算 する下記のような 別のアルゴリズム があり、いろんなウェブページを見た所 こちらのほうが一般的によく紹介されている のではないかと思います。
-
bを反転したビット列を計算する変数resultを0で初期化する - 下記の処理を
length回行う-
resultを 1 ビット左シフトする -
resultの 0 番のビットの値をbの 0 番のビットの値にする -
bを 1 ビット右シフトする
-
行われる処理の説明
上記のアルゴリズムで行われる処理を 0b01001101 を 8 ビット のビット列として 反転する処理 を具体例として説明します。
下図は上記の 手順 1 の処理の後の状態 を表す図で、b に 0b01001101 が、result に 0 が代入 されています。なお、下図の result の各ビットの値のように、元の b のビットと関係のない 0 のビット は 黄色で塗りつぶす ことにします。また、下記の処理ではいずれの場合も b と result の 8 番以降のビットはすべて 0 になるので左シフト演算によるビットの対応を明確にしたい場合を除いて図では表記を 省略する ことにします。
下記は 1 回目 の 手順 2 で行われる処理を表す図です。
手順 2-1 では result が 1 ビット左シフト されますが、result の値は 0 だった ので result の値は 0 のまま変化しません。
手順 2-2 では result の 0 番 のビットが b の 0 番 のビットの値である 1 になります。
手順 2-3 では b が 1 ビット右シフト された結果、b から 元の 0 番のビットが削除 され、i 番のビット が 元の i + 1 番のビット になります。
下記は 2 回目 の 手順 2 で行われる処理を表す図です。行われる処理は上記と同じなので説明は省略しますが、2 回の繰り返し処理 によって 元の b の 0 番と 1 番 のビットの値が result の 1 番と 0 番 の ビットに移動 したことがわかります。
下図は 3 回目以降 の処理の結果を表す図で、繰り返し処理 が 1 回行われるたび に b のビット が 右から順番 に result を左にずらしながら 0 番のビットに追加 されていき、8 回目の処理 によって result に b を反転したビット列が計算される ことが確認できます。
下図は このアルゴリズム が b と result のビット を 赤線の矢印の方向 に 1 ビットずつずらす という処理を行うことを表します。
reverse2 の定義
下記は 上記のアルゴリズム で処理を行う reverse2 を定義するプログラムです。なお、retval << 1 によって計算される ビット列の 0 番 のビットは 0 になる ので、b の 0 番のビットを表す b & 1 との OR 演算 を行うことで 0 番のビット が b の 0 番のビットの値 になるビット列が計算されます。
- 2 行目：手順 1 の処理を行う
-
3 行目：ビット長を表す
length回の繰り返し処理を行う -
4 行目：
retvalを 1 ビット左シフトしたretval << 1とbの 0 番のビットの値との OR 演算を行った値をresultに代入することで、手順 2-1 と 手順 2-2 の処理を行う - 5 行目：手順 2-3 の処理を行う
1 def reverse2(b, length):
2 retval = 0
3 for i in range(length):
4 retval = (retval << 1) | (b & 1)
5 b >>= 1
6 return retval
行番号のないプログラム
def reverse2(b, length):
retval = 0
for i in range(length):
retval = (retval << 1) | (b & 1)
b >>= 1
return retval
下記は 先程と同じ反転処理 を reverse2 で行うプログラムです。実行結果は先ほどと同じ なので省略しますが、実行結果から reverse2 が正しい処理を行う ことが確認できました。
for length in range(8, 17):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse2(b, length):0{length}b}")
下記は reverse2 の 処理速度を計測 するプログラムです。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
%timeit reverse2(b, length)
実行結果
bit length = 10
1.08 μs ± 11.2 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
12.1 μs ± 224 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
151 μs ± 3.73 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 10000
3.37 ms ± 22.4 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
bit length = 100000
159 ms ± 1.1 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
bit length = 1000000
14.3 s ± 20.6 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
下記は reverse1 と reverse2 の 処理時間をまとめた表 です。単位は μs で小数点以下第 2 桁で四捨五入しました。
| ビット長 | reverse1 |
倍率 | reverse2 |
倍率 |
|---|---|---|---|---|
| 10 | 1.0 | 1.1 | ||
| 100 | 8.5 | 8.4 | 12.1 | 11.2 |
| 1,000 | 99.8 | 11.7 | 151.0 | 12.5 |
| 10,000 | 1,340.0 | 13.4 | 3,370.0 | 22.3 |
| 100,000 | 22,500.0 | 16.8 | 159,000.0 | 47.2 |
| 1,000,000 | 1,330,000.0 | 45.8 | 14,300,000.0 | 89.9 |
上記の表から reverse2 は reverse1 と同様に ビット長が小さい場合 は ビットと処理時間はほぼ比例 し、ビット長が大きくなる と 比例よりも大きく増加する ことがわかります。
また、reverse2 のほうが 処理速度が大幅に遅くなる ことが確認できました。これは、reverse1 が下記のプログラムの 4 行目 のように ビットが 0 の場合は何も処理を行わない こと、処理速度を計測 した reverse1 で反転処理を行う 0b01001101 の 1 のビットの数が 4 のように 少ないことが原因 です。
1 def reverse1(b, length):
2 result = 0
3 for i in range(length):
4 if b & (1 << i):
5 result |= 1 << (length - i - 1)
6 return result
そこで、すべてのビットが 1 のビット列に対する reverse1 と reverse2 の 処理時間 を下記のプログラムで 計測 してみることにします。すべてのビットが 1 であるビット列の計算方法について忘れた方は 前回の記事を復習して下さい。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
b2 = (1 << length) - 1
print("reverse1")
%timeit reverse1(b2, length)
print("reverse2")
%timeit reverse2(b2, length)
実行結果
bit length = 10
reverse1
1.49 μs ± 8.45 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
reverse2
1.13 μs ± 5.52 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
reverse1
18.9 μs ± 33.8 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
reverse2
16 μs ± 115 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
reverse1
241 μs ± 1.81 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
reverse2
213 μs ± 1.65 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 10000
reverse1
5.05 ms ± 123 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
reverse2
5.34 ms ± 114 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
bit length = 100000
reverse1
191 ms ± 3.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
reverse2
285 ms ± 2.52 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
bit length = 1000000
reverse1
15.6 s ± 27.3 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
reverse2
26.5 s ± 91.1 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
下記は 上記の実行結果をまとめた表 です。処理時間の単位は μs で、小数点以下第 2 位で四捨五入しました。
| ビット長 | reverse1 |
倍率 | reverse2 |
倍率 |
|---|---|---|---|---|
| 10 | 1.5 | 1.1 | ||
| 100 | 18.9 | 12.7 | 16.0 | 14.2 |
| 1,000 | 241.0 | 12.8 | 213.0 | 13.3 |
| 10,000 | 5,050.0 | 21.0 | 5,340.0 | 25.1 |
| 100,000 | 191,000.0 | 37.8 | 285,000.0 | 53.4 |
| 1,000,000 | 1,560,000.0 | 81.7 | 26,500,000.0 | 93.0 |
上記から、ビット長が 1000 以下 のように 小さい場合 は reverse2 の方が 処理速度が若干速い ことが確認できます。これは、繰り返しの中で行う処理 が reverse2 の方が reverse1 よりも 少しだけ単純 だからではないかと思われます。
一方 ビット長が 10000 以上 の場合は reverse1 のほうが 処理速度が速くなる ようです。詳しい検証を行うと記事がかなり長くなってしまうので省略しますが、これはおそらく 繰り返し処理の過程 で b や result に代入される値 の ビット長が関係している のではないかと思われます。興味がある方はそのことを検証してみて下さい。
上記から 1 のビットが非常に多いことがあらかじめわかっている場合を除けば、reverse1 のアルゴリズムの方が 処理速度が高速になる可能性が高い ことがわかりました。
アルゴリズムの改良
reverse1 と reverse2 のアルゴリズムはどちらも 無駄な処理を行う場合がある ので 改良することができます。どのように改良できるかについて少し考えてみて下さい。
reverse1 と reverse2 はいずれもビット長を表す length 回の繰り返し処理 を行いますが、実際には 繰り返し処理の回数を減らすことができる場合 があります。
reverse1 の場合は、b の 1 である最も大きな番号 より 大きな番号のビットはすべて 0 なので、それらのビットに対する処理を行う必要はありません。1 である最も大きな番号のビット は以前の記事 で説明したように bit_length メソッドで計算できる ので、その回数だけ繰り返し処理を行えば十分 です。下記はそのように reverse1 を修正した reverse3 の定義 です。
-
3 行目：
bit_lengthメソッドで計算した回数だけ繰り返し処理を行うように修正した
1 def reverse3(b, length):
2 result = 0
3 for i in range(b.bit_length()):
4 if b & (1 << i):
5 result |= 1 << (length - i - 1)
6 return result
行番号のないプログラム
def reverse3(b, length):
result = 0
for i in range(b.bit_length()):
if b & (1 << i):
result |= 1 << (length - i - 1)
return result
修正箇所
-def reverse1(b, length):
+def reverse3(b, length):
result = 0
- for i in range(length):
+ for i in range(b.bit_length()):
if b & (1 << i):
result |= 1 << (length - i - 1)
return result
reverse2 の場合は、b が 0 になった時点 で、残りの b のビットはすべて 0 になることが確定します。そのため その時点 で result を残りのビットだけ左シフト演算 を行うことで 残りの繰り返し処理を省略 することができます。
例えば b = 0b0000101 を 8 ビットのビット列 として result2 のアルゴリズムで反転処理を行うと、3 回目の繰り返し処理 の後で下図のように b が 0 になります。残りの 5 回分 の繰り返し処理では b の 0 番のビットが常に 0 になるので、下図のように result を 5 ビット左シフト することで、残りの 5 回分 の繰り返し処理を 省略する ことができます。
下記はそのように reverse2 を修正した reverse4 の定義 です。
-
3 行目：
bが0になるまで繰り返し処理を行う -
6 行目：繰り返しのたびに
lengthから1を引くことで、lengthに残りのビット数が計算されるようにする -
7 行目：
retvalを残りのビット数であるlengthビットだけ左シフトした値を返すように修正する。なお、すべてのビットに対する繰り返し処理が行われた場合はlengthが0となり、0 ビットの左シフトは何も行わないのでretvalそのものが返される
1 def reverse4(b, length):
2 retval = 0
3 while b:
4 retval = (retval << 1) | (b & 1)
5 b >>= 1
6 length -= 1
7 return retval << length
行番号のないプログラム
def reverse4(b, length):
retval = 0
while b:
retval = (retval << 1) | (b & 1)
b >>= 1
length -= 1
return retval << length
修正箇所
-def reverse2(b, length):
+def reverse4(b, length):
retval = 0
- for i in range(length):
+ while b:
retval = (retval << 1) | (b & 1)
b >>= 1
+ length -= 1
- return retval
+ return retval << length
処理の確認と処理速度の計測
下記は 先程と同じ反転処理 を reverse3 と reverse4 で行うプログラムです。実行結果は先ほどと同じ なので省略しますが、実行結果から reverse3 と reverse4 が正しい処理を行う ことが確認できました。
for length in range(8, 17):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse3(b, length):0{length}b}")
print(f"0b{reverse4(b, length):0{length}b}")
下記は b = 0b01001101 と すべてのビットが 1 であるビット列に対しする reverse3 と reverse4 の 処理速度を計測 するプログラムです。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
b2 = (1 << length) - 1
print("reverse3")
%timeit reverse3(b, length)
%timeit reverse3(b2, length)
print("reverse4")
%timeit reverse4(b, length)
%timeit reverse4(b2, length)
実行結果
bit length = 10
reverse3
834 ns ± 4.01 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.49 μs ± 8.64 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
reverse4
777 ns ± 2.39 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
1.19 μs ± 12 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
reverse3
936 ns ± 12.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
18.7 μs ± 212 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
reverse4
786 ns ± 2.45 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
17.1 μs ± 376 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
reverse3
1.07 μs ± 2.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
237 μs ± 2.23 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
reverse4
920 ns ± 32.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
222 μs ± 778 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 10000
reverse3
1.77 μs ± 9.45 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
4.94 ms ± 133 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
reverse4
972 ns ± 40.5 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
5.35 ms ± 110 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
bit length = 100000
reverse3
5.67 μs ± 98.3 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
188 ms ± 2.12 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
reverse4
1.11 μs ± 42 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
283 ms ± 1.71 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
bit length = 1000000
reverse3
45.4 μs ± 222 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
15.1 s ± 67.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
reverse4
2.7 μs ± 135 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
25.7 s ± 97.7 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
下記は reverse1 ~ reverse4 の 処理時間をまとめた表 です。上段が 0b01001101、下段がすべてのビットが 1 の場合です。処理時間の単位は μs で小数点以下で第 2 桁で四捨五入し、比較しやすい ように reverse1 と reverse3、reverse2 と reverse4 を 並べました。
| ビット長 | reverse1 |
reverse3 |
reverse2 |
reverse4 |
|---|---|---|---|---|
| 10 | 1.0 1.5 |
0.8 1.5 |
1.1 1.1 |
0.8 1.2 |
| 100 | 8.5 18.9 |
0.9 18.7 |
12.1 16.0 |
0.8 17.1 |
| 1,000 | 99.8 241.0 |
1.1 237.0 |
151.0 213.0 |
0.9 222.0 |
| 10,000 | 1,340.0 5,050.0 |
1.8 4,940.0 |
3,370.0 5,340.0 |
1.0 5,350.0 |
| 100,000 | 22,500.0 191,000.0 |
5.7 188,000.0 |
159,000.0 285,000.0 |
1.1 283,000.0 |
| 1,000,000 | 1,330,000.0 1,560,000.0 |
45.4 15,100,000.0 |
14,300,000.0 26,500,000.0 |
2.7 25,700,000.0 |
表から 以下の事が確認 できました。
-
1である最も大きなビットの番号が小さい の場合はreverse3とreverse4のほうがreverse1とreverse2よりも 処理速度が速くなる。ビット長が大きい程 そのことが 顕著であり、ビット長が増えてもreverse3とreverse4の処理時間は あまり増えない -
すべてのビットが
1の場合はreverse3、reverse4の 処理速度 はreverse1とreverse2と ほぼ変わらない
delta swap を利用したアルゴリズム
別の方法として、以前の記事で紹介した ビット列の特定のビットを入れ替える 処理を行う delta swap を利用した方法が考えられます。
delta swap を行う関数の定義
プログラムを実装しやすくするために、delta swap を行う下記のような delta_swap という関数を定義 することにします。
- 仮引数
bに delta swap を行うビット列、仮引数maskとdeltaに delta swap で利用するビットマスクと交換するビットの間隔を代入する - 返り値として
bに対して delta swap を行った値を返す
下記は delta_swap の定義を行うプログラムです。プログラムの意味について忘れた方は以前の記事を復習して下さい。
def delta_swap(b, mask, delta):
c = (b ^ (b >> delta)) & mask
return c ^ (c << delta) ^ b
処理速度を最重視する場合は以前の記事のように delta swap を行う関数を定義しないほうが高速になりますが、今回の記事ではわかりやすさを重視して実装を行うことにします。
delta swap で 1 ビットずつ交換を行うアルゴリズム
以前の記事で説明したように delta swap は 交換するビットの間隔が等しい 場合は 複数のビットをまとめて交換 することができますが、例えば 8 ビット のビット列の 反転処理 の場合は下記の表のように 交換するビットの間隔がすべて異なる ので 1 ビットずつ交換する という方法が考えられるでしょう。
| 入れ替えるビット | 0、7 | 1、6 | 2、5 | 3、4 |
|---|---|---|---|---|
| 間隔 | 7 | 5 | 3 | 1 |
n ビット のビット列の場合は、n が偶数 の場合は下記の表のようになります。
| 入れ替えるビット | 0、n - 1 | 1、n - 2 | 2、n - 3 | … | n / 2 - 1、n / 2 |
|---|---|---|---|---|---|
| 間隔 | n - 1 | n - 3 | n - 5 | … | 1 |
n が奇数 の場合は下記の表のようになり、真ん中 の (n - 1) / 2 番 のビットは 入れ替える必要はありません。
| 入れ替えるビット | 0、n - 1 | 1、n - 2 | 2、n - 3 | … | (n - 1) / 2 - 1、 (n - 1) / 2 + 1 |
|---|---|---|---|---|---|
| 間隔 | n - 1 | n - 3 | n - 5 | … | 2 |
上記の表から n ビット のビット列 b の反転処理 は以下のアルゴリズムで行うことができることがわかります。なお、range を利用した 繰り返し処理 では 0 から特定の整数未満 の繰り返し処理を行うので、下記では 数値の範囲 を 未満 で表記しました。
-
n が偶数 の場合
i を 0 から n / 2 未満 までの整数とした 繰り返し処理 で i 番 と n - 1 - i 番 のビットを delta swap で入れ替える -
n が奇数 の場合
i を 0 から (n - 1) / 2 未満 までの整数とした 繰り返し処理 で i 番 と n - 1 - i 番 のビットを delta swap で入れ替える
n が偶数と奇数 の場合で 異なる のは i の範囲だけ です。n が偶数と奇数の場合で処理を変える のは if 文の 条件式の計算の処理 の分だけ 時間がかかってしまう、プログラムが長く なってしまうという 欠点がある ので、上記の処理を一つにまとめる ことにします。
n が奇数 の場合は (n - 1) / 2 は整数 なので、それに 0.5 を加算 した (n - 1) / 2 + 1 / 2 = n / 2 の 整数の部分 を表す 商 は (n - 1) / 2 と同じ値 になります。Python では // という 演算子で商を計算 できるので、この演算子を利用すると (n - 1) / 2 = n // 2 となります。
n が偶数 の場合は n / 2 は整数なので、奇数の場合と同様に n / 2 = n // 2 となります。
従って、上記のアルゴリズムの i の範囲 は、n が偶数でも奇数でも「0 から (n - 1) // 2 未満」となることがわかりました。
reverse5 の定義
下記は上記のアルゴリズムで処理を行う reverse5 を定義するプログラムです。
-
2 行目：
0からlength // 2未満までの繰り返し処理を行う -
3 行目：繰り返し処理の中では
i<length - 1 - iなので、delta swap のビットマスクはi番のビットのみが1となる1 << iとなる。また、交換するビットの番号の差はlength - 1 - i - i=length - 1 - 2 * iとなるので、それらの値を実引数に記述してdelta_swapを呼び出し、その返り値をbに代入する
1 def reverse5(b, length):
2 for i in range(length // 2):
3 b = delta_swap(b, 1 << i, length - 1 - 2 * i)
4 return b
行番号のないプログラム
def reverse5(b, length):
for i in range(length // 2):
b = delta_swap(b, 1 << i, length - 1 - 2 * i)
return b
下記は 先程と同じ反転処理 を reverse5 で行うプログラムです。実行結果は先ほどと同じ なので省略しますが、実行結果から reverse5 が正しい処理を行う ことが確認できました。
for length in range(8, 17):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse5(b, length):0{length}b}")
下記は reverse5 の 処理速度を計測 するプログラムです。reverse5 のアルゴリズムは 1 のビットの数に影響されない ので b = 0b01001101 に対する計測だけ を行いました。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
%timeit reverse5(b, length)
実行結果
bit length = 10
1.3 μs ± 6.96 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
15.6 μs ± 117 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
185 μs ± 4.34 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 10000
4.02 ms ± 40.1 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
bit length = 100000
187 ms ± 914 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
bit length = 1000000
16.1 s ± 30.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)
下記は 最も時間がかかる、すべてのビットが 1 の場合の reverse1、reverse2 と上記の実行結果をまとめた表です。
| ビット長 | reverse1 |
倍率 | reverse2 |
倍率 | reverse5 |
倍率 |
|---|---|---|---|---|---|---|
| 10 | 1.5 | 1.1 | 1.3 | |||
| 100 | 18.9 | 12.7 | 16.0 | 14.2 | 15.6 | 12.0 |
| 1,000 | 241.0 | 12.8 | 213.0 | 13.3 | 185.0 | 11.9 |
| 10,000 | 5,050.0 | 21.0 | 5,340.0 | 25.1 | 4,020.0 | 21.7 |
| 100,000 | 191,000.0 | 37.8 | 285,000.0 | 53.4 | 187,000.0 | 46.5 |
| 1,000,000 | 1,560,000.0 | 81.7 | 26,500,000.0 | 93.0 | 16,100,000.0 | 86.1 |
delta swap は 1 度で 2 つのビットの交換 を行う事ができるので、繰り返しの回数 を reverse1 や reverse2 の半分 に減らすことができますが、delta swap で行う処理は reverse1 で 2 つ分のビットの計算 を行う処理と 同じくらい複雑 なので、reverse1 と処理時間はほとんど変わらない ようです。また、reverse1 のように ビットが 0 の場合の処理を省略 したり、reverse3 や reverse4 のように 繰り返し処理の回数を減らすことはできません。従って、このような delta swap の利用方法 は 処理速度の面 では あまり有効ではない ことがわかります。
分割統治法による delta swap を利用した方法
delta swap は 複数のビットをまとめて交換できる点が優れている ので、reverse5 のように 1 つのビットだけを交換 するアルゴリズムは 効果的な利用方法でありません。
そこで、delta swap で 複数のビットをまとめて交換 する もっと効率の良いアルゴリズム を紹介します。
アルゴリズムの説明
これから紹介する アルゴリズムの特徴 は、ビット列 を 複数の部分に分割 し、分割した それぞれのビット列に対して同じ処理をまとめて行う という点にあります。下記はそのアルゴリズムです。なお、下記の 手順 2 の表記を統一 するために、分割を行う前 の 元のビット列 を 1 つに分割された ビット列と 表記する ことにします。
- 最初はすべてのビットを持つ 1 つのビット列に分割 した 状態から開始 する
- 分割した すべてビット列のビット長が 1 になるまで 下記の処理を 繰り返す
- ビット長が 2 以上 の すべての分割したビット列 に対して下記の処理を行う
- ビット長が偶数 の場合は 均等なビット長 で 左右に 2 つに分割 し、分割したビット列 を delta swap でまとめて交換 する
- ビット長が奇数 の場合は 真ん中の 1 ビット とその 左右のビット列 で 3 つに分割 し、左右のビット列 を delta swap でまとめて交換 する
具体例によるアルゴリズムの手順の説明
わかりづらいと思いますので、具体例として 8 ビットの長さ の 0b001001101 をこのアルゴリズムで 反転する手順 を図で詳しく説明します。
1 回目の手順 2 の処理
最初 は 0 ~ 7 番 のビットを持つ 1 つのビット列に分割 された 状態から開始 します。
0 ~ 7 番 の 8 個 のビット列の ビットの個数は 8 なので 手順 2 の処理を行います。
下図は 1 回目の手順 2 で行う処理を図示したものです。
0 ~ 7 番 の ビットの個数は偶数 なので、上図のように 赤線 で 4 個ずつ均等 にビット列を 左右に分割 し、delta swap で交換 します。交換するビット は下記の表のように すべての間隔が 4 で等しい ので、以前の記事で説明したように delta swap でまとめて交換 できます。
| 交換するビット | 0 と 4 | 1 と 5 | 2 と 6 | 3 と 7 |
|---|---|---|---|---|
| 間隔 | 4 | 4 | 4 | 4 |
具体的には下記のプログラムのように 0、1、2、3 番 のビットを 1 とする 0b00001111 をビットマスク、delta を 4 とした delta swap で上記の計算を行うことができます。実行結果から正しい計算が行われることが確認できます。なお、計算結果 は 1 回目 の手順 2 の計算なので b1 という変数に代入しました。この後で行う 2 回目以降 の手順 2 の 計算結果 も 同様に b2、b3 という変数に代入することにします。
print(f"0b{b:08b}")
b1 = delta_swap(b, 0b00001111, 4)
print(f"0b{b1:08b}")
実行結果
0b01001101
0b11010100
手順 2 の計算の意味
下記は 手順 2 で 計算したビット列 と、このアルゴリズムで 最終的に計算 する b を反転したビット列 を 並べた図 です。
上図からわかるように、赤い線で分割 した図の 上部のそれぞれのビット列 は、下記のように 最終的に求めたい 図の 下部の対応するビット列 を 反転した値 になります。
- 上部の 0 ~ 3 番のビットを反転すると、下部の 0 ~ 3 番のビット列になる
- 上部の 4 ~ 7 番のビットを反転すると、下部の 4 ~ 7 番のビット列になる
このことから、手順 2 は 1 つ の ビット長が 8 のビット列の 反転処理 を、2 つ の ビット長が 4 のビット列の 反転処理に変換 するという処理が行われることがわかります。
ビット長が奇数の場合の手順 1 の処理
ビット列の ビット長が奇数の場合 も 同様の計算が行われる ことを示します。下記は ビット長 が 奇数の 7 の場合の 手順 2 の処理 を表す図です。
上図 のように 真ん中の 3 番 のビットを除いて、0 ~ 2 番 と 4 ~ 6 番 のビットに 左右に均等に分割 し、それらを delta swap で交換 します。上図からわかるように、赤い線 で 3 番 のビットを 中心に左右に 3 分割 した真ん中の図の それぞれのビット列 は、下記のように 最終的に求めたい 図の 下部の対応するビット列を反転 した値になっています。
- 真ん中の 0 ~ 2 番のビットを反転すると、下部の 0 ~ 2 番のビット列になる
- 真ん中の 3 番のビットを反転すると、下部の 3 番のビットと同じになる（一つしかビットがないので反転しても変わらない）
- 真ん中の 4 ~ 6 番のビットを反転すると、下部の 4 ~ 6 番のビット列になる
このことから、手順 2 は 1 つ の ビット長が 7 のビット列の 反転処理 を、2 つ の ビット長が 3 のビット列の 反転処理に変換 するという処理が行われることがわかります。なお、もうひとつの分割した 真ん中 の 3 番のビットは 1 つしかない ので それ以上の反転処理を行う必要はありません。
偶数と奇数 の場合で行われる 処理 から、手順 2 の処理は、ビット列の反転処理 を、2 つの半分の長さ のビット長（端数は切り捨て）の ビット列の反転処理 に変換するという処理を行っていることがわかります。また、下記の性質 から 手順 2 を 有限の回数行う ことで ビット列の反転処理が行われる ことがわかります。
- 1 回の手順 2 の ビット列の分割処理 で ビット長が半分（端数切り捨て） の 2 倍の個数のビット列が生成 される
- ビット長が奇数 の場合はそれに加えて 真ん中にあるビット長が 1 の ビット列が 1 つ生成 される
- 手順 2 の処理によって、分割されたすべてのビット列には 元の同じ位置にあるビット列を反転 したビット列が 計算される
- 手順 2 の処理で 分割したビット列 の ビット長が必ず減る ので、有限回の手順 2 の処理で分割されたビット列の ビット長が必ず 1 になる
- 分割された長さが 1 のビット列の ビット は、元のビット列を反転した位置に移動 しているので、すべての分割されたビット列のビット長が 1 になった時点で すべてのビットが反転した ビット列が計算されたことになる
このような、大きな規模の処理 を 処理の規模を小さくした複数の処理に変換 することで計算を行うアルゴリズムのことを 分割統治法（divide and conqurer method）と呼びます。
分割統治法 は 巨大な問題 を そのまま解くことが難しい 場合などで、その問題を小さく分割して解きやすくする というアルゴリズムです。上記のアルゴリズムはこの後で説明するように 手順 2 で小さく分割した複数のビット列 に対する 次の手順 2 の処理 を 1 回の delta swap でまとめて行うことができる ので 非常に効率の良い処理 を行うことができます。
ただし、すべての問題 が大きな問題を 小さく分割することで解きやすくなるわけではありません。分割することでかえって 手間が増えることもある ので、どのような問題でも分割統治法が有効であるとは限らない 点に注意が必要です。
分割統治法 を利用した 効率的なアルゴリズム の代表例として、並べ替え を行う クイックソート があります。
参考までに分割統治法とクイックソートの Wikipedia の項目を下記に記します。
分割統治法は、古代のローマ帝国が、征服した地域を都市ごとに分割することで効率的に支配したという統治法から名づけられています。また、ヨーロッパ諸国が植民地を支配した際の統治法も同様の支配を行ったので分割統治法と呼ばれています。
参考までに本来の意味での分割統治の Wikipedia の項目を下記に記します。
2 回目の手順 2 の処理
1 回目 の 手順 2 の処理では 2 つの ビット長が 4 のビット列に 分割した ので 次の手順 2 の処理を行います。下図は 2 回目の 手順 2 の処理を表す図です。
上図 のように 1 回目の手順 2 の処理で 分割した 0 ~ 3 番 と 4 ~ 7 番 のビット列を それぞれ水色の線 で 左右に均等に分割 し、それらを delta swap で交換 します。
上図から計算された 図の真ん中のビット列 は 下記のような性質を持つ ことがわかります。
- 真ん中の 0、1 番のビットを反転すると、下部の 0、1 番のビット列になる
- 真ん中の 2、3 番のビットを反転すると、下部の 2、3 番のビット列になる
- 真ん中の 4、5 番のビットを反転すると、下部の 4、5 番のビット列になる
- 真ん中の 6、7 番のビットを反転すると、下部の 6、7 番のビット列になる
このことから、2 回目の手順 2 は 2 つ の ビット長が 4 のビット列の 反転処理 を、4 つ の ビット長が 2 のビット列の 反転処理に変換 するという処理が行われることがわかります。
2 回目の手順 2 の処理を行うプログラム
1 回目の手順 2 では ビット列を均等に分割 するので、分割された ビット列の長さはすべて同じ1 になります。2 回目の手順 2 では、その 分割したビット列 を さらに均等に分割して交換 するので、交換するビットの間隔 は下記の表のように すべてが 2 で等しくなる ので、delta swap でまとめて交換 することができます。
| 入れ替えるビット | 0 と 2 | 1 と 3 | 4 と 6 | 5 と 7 |
|---|---|---|---|---|
| 間隔 | 2 | 2 | 2 | 2 |
具体的には下記のプログラムの 3 行目 のように 0、1、4、5 番 のビットを 1 とする 0b00110011 をビットマスク、delta を 2 とした delta swap で 2 回目の手順 2 の計算を行うことができ、実行結果から 正しい計算が行われる ことが確認できます。
b2 = delta_swap(b1, 0b00110011, 2)
print(f"0b{b2:08b}")
実行結果
0b01110001
3 回目の手順 2 の処理を行うプログラム
2 回目 の 手順 2 の処理では 4 つの ビット長が 2 のビット列に 分割された ので 次の手順 2 の処理を行います。下図は 3 回目の 手順 2 の処理を表す図です。
上図 のように 2 回目の手順 2 の処理で分割した 4 つのビット列を それぞれ緑色の線 で 左右に均等に分割 し、それらを delta swap で交換 します。
分割されたビット列 の ビット長はすべて 1 になるのでここで処理は終了します。また、図から 実際に b を反転したビット列が計算 できたことが確認できます。
下記は 3 回目の手順 2 で 入れ替えるビットと間隔 を表す表です。先ほどと同様の理由 から 交換するビットの間隔 は下記の表のように すべて 1 で等しくなる ので、delta swap でまとめて交換 することができます。
| 入れ替えるビット | 0 と 1 | 2 と 3 | 4 と 5 | 6 と 7 |
|---|---|---|---|---|
| 間隔 | 1 | 1 | 1 | 1 |
具体的には下記のプログラムのように 0、2、4、6 番 のビットを 1 とする 0b01010101 をビットマスク、delta を 1 とした delta swap で上記の計算を行うことができ、実行結果から 正しい計算が行われる ことが確認できます。
b3 = delta_swap(b2, 0b01010101, 1)
print(f"0b{b3:08b}")
実行結果
0b10110010
全体の処理の流れ
下図は 全体の処理の流れ を表す図です。
図からわかるように、1 回の手順 2 の処理で 分割を行うたび に ビット長を半分 にして 交換を行い、ビット長が すべて 1 になった時点で ビット列の反転が計算 されます。上図にはありませんが、ビット長が奇数 の場合は 真ん中のビットは交換する必要がない ので、真ん中のビットを除いたビット で 均等に分割 が行われます。
ビットマスクと delta の計算方法
任意のビット長 のビット列に対して このアルゴリズムで計算を行うため には、手順 2 で delta swap を行う際に必要となる ビットマスク と delta を 計算する必要 があります。どのように計算すればよいかについて少し考えてみて下さい。
最初のビットマスクの計算方法
以下では ビット長が n の ビット列の反転 を行うことを考えます。最初 の 手順 2 の処理では ビット長が n のビット列を 2 つに分割 して delta swap で交換 します。
以前の記事で説明したように、delta swap で利用する ビットマスク は、交換するビット のうち 番号が小さいほうのビットを 1 とした ビット列 です。
n が偶数 の場合はビット列を 左右に均等に分割 して交換するので、ビットマスク は 0 以上 n / 2 未満 の n / 2 個のビットが 1 となるビット列です。
n が奇数 の場合はビット列を 真ん中のビットで左右に均等に分割 して交換するので、ビットマスク は 0 以上 (n - 1) / 2 未満 の (n - 1) / 2 個のビットが 1 となるビット列です。
これは 先程説明 した状況と同じなので、上記を下記のようにまとめることができます。
-
最初のビットマスク は 0 番から n // 2 個 の
1が並んだビット列である - そのようなビットマスクは
(1 << (n // 2)) - 1という式で計算できる
最初の delta の計算方法
delta swap で利用する delta は、交換するビットの間隔 を表します。
n が偶数 の場合は 0 番 のビットを n / 2 番のビットと交換 するのでその 間隔は n / 2 です。
n が奇数 の場合は 0 番 のビットを 真ん中の (n - 1) / 2 番の次の (n + 1) / 2 番のビットと交換 するのでその 間隔は (n + 1) / 2 です。
n が偶数 の場合は n / 2 は整数 なので、それに 0.5 を足した (n + 1) / 2 を切り捨てた値 は n / 2 と等しく なります。従って (n + 1) を 2 で割った商は n / 2 と等しくなるので、n / 2 = (n + 1) // 2 が成り立ちます。
n が奇数 の場合は (n + 1) / 2 は整数 なので、(n + 1) を 2 で割った商は (n + 1) / 2 と等しくなるので、(n + 1) / 2 = (n + 1) // 2 が成り立ちます。
上記から 最初の delta は (n + 1) // 2 という式で計算できることがわかりました。
下記は 上記の式を利用 して 0b01001101 に対して ビット長が 7 と 8 の場合の 1 回目の手順 2 の処理を行うプログラムです。
for length in [7, 8]:
print(f"ビット長 = {length}")
mask = (1 << (length // 2)) - 1
print(f"mask = 0b{mask:0{length}b}")
delta = (length + 1) // 2
print(f"delta = {delta}")
print(f"b = 0b{b:0{length}b}")
print(f"delta swap = 0b{delta_swap(b, mask, delta):0{length}b}")
print()
実行結果
ビット長 = 7
mask = 0b0000111
delta = 4
b = 0b1001101
delta swap = 0b1011100
ビット長 = 8
mask = 0b00001111
delta = 4
b = 0b01001101
delta swap = 0b11010100
実行結果 と先程示した 下図を比べ て 正しい計算が行われていることを確認 して下さい。
なお、n が奇数の場合 に分割される 真ん中の 1 ビットのビット列 は 反転しても位置が変わらない ので それ以上処理を行う必要はありません。そのため、以後は説明を省略 します。
i 回目の手順 2 での delta の計算方法
2 回目以降 の i 回目の手順 2 での delta は 簡単に計算できる ので、その計算方法について先に説明します。
1 回目の手順 2 では 2 つ の ビット長が n // 2 の ビット列が計算 されます。2 回目の手順 2 では それらのビット列 に対して 同様の分割処理が行われる ので、4 つ の ビット長が (n // 2) // 2 の ビット列が計算 されます。以後の 手順 2 でも 同様の処理が行われる ので下記の事がわかります。
最初のビット列 の ビット長 を $\boldsymbol{n_0}$、i 回目の手順 2 の後 で 分割された各ビット列 の ビット長 を $\boldsymbol{n_i}$ と表記すると、下記の式が成り立つ。
- $\boldsymbol{n_0 = n}$
- $\boldsymbol{n_i = n_{i - 1} \ //\ 2}$ （ただし、$i ≧ 1$ とする）
また、i 回目の 手順 2 では 同じ長さのビット列 に対して 均等なビット長で左右に分割して交換する員処理を行う ので、交換するビットの間隔 は すべて等しく なり、1 回目の手順 2 と同じ方法 で delta を計算 することができます。従って、下記のことがわかります。
i 回目の手順 2 での delta swap の delta の値を $\boldsymbol{d_i}$ と表記すると、下記の式が成り立つ。
$\boldsymbol{d_i = (n_{i-1} + 1) \ //\ 2}$
2 回目の手順 2 のビットマスクの計算方法
表記を簡単にする ために、i 回目の手順 2 で利用する ビットマスク を $\boldsymbol{m_i}$ と表記することにします。先ほど示したように $\boldsymbol{m_1 = (1 << n_1) - 1}$ となります。
以下の説明では、分割したビット列のビット長 と delta が異なる場合 の具体例として、下図のような 最初のビット列 の ビット長が 9 の場合 で説明します。図の 上部 に 1 回目の手順 2 で行われる処理 を、下部 に 1 回目の手順 2 で計算される ビットマスク、分割したビット列のビット長（$n_1$）、delta（$d_1$）を図示しました。
2 回目の手順 2 では上図の 左右に 2 つに分割 された ビット長が $\boldsymbol{n_1}$ の 各ビット列 を 均等に分割 して delta swap で交換 する処理を行います。
2 回目の手順 2 で利用する ビットマスク を表す $\boldsymbol{m_2}$ は、下図のように、1 回目の手順 2 で 左右に分割した部分に対応 する 緑色 で塗りつぶされた部分と 紫色 で塗りつぶされた部分に 分けて考える ことができます。また、ビットの番号が小さいほう の図の 右（right） にある 緑色のビット列 を $\boldsymbol{m_{2r}}$、左（left） にある 紫色のビット列 を $\boldsymbol{m_{2l}}$ と表記すると、$\boldsymbol{m_2}$ はそれらの ビット列をあわせる OR 演算 による 下記の式で計算 することができます。
$\boldsymbol{m_2 = m_{2r} \ | \ m_{2l}}$
ビットの番号が小さいほう の 緑色 の $\boldsymbol{m_{2r}}$ は 0 番 から $\boldsymbol{n_1}$ 番未満 の ビット長が $\boldsymbol{n_1}$ のビット列なので、1 回目の手順 2 のビットマスクの計算と 同様の理由 から 下記の式で 式で計算 することができます。
$\boldsymbol{m_{2r} = (1 << n_2) - 1}$
2 回目の手順 2 の処理では ビットの番号が大きいほう のビット列と、小さいほうのビット列 に対して、同様の入れ替えの処理を行う ので、上図の 紫色 の部分を表す $\boldsymbol{m_{2l}}$ は下記のような性質を持ちます。
- 紫色 の $\boldsymbol{m_{2l}}$ の ビットの並び は、緑色 の $\boldsymbol{m_{2r}}$ の ビットの並びと同じ になる
-
紫色 の $\boldsymbol{m_{2l}}$ と 緑色 の $\boldsymbol{m_{2r}}$ の 間隔 は 1 回目の手順 2 の
deltaである $\boldsymbol{d_1}$ と同じ になる。$\boldsymbol{d_2}$ ではない 点に注意すること
従って、紫色 の $\boldsymbol{m_{2l}}$ は、緑色 の $\boldsymbol{m_{2r}}$ を 左に $\boldsymbol{d_1}$ ビットシフト演算 を行った 下記の式で計算 することができます。
$\boldsymbol{m_{2l} = m_{2r} << d_1}$
式がかなり多くなってややこしくなりまし方、$\boldsymbol{m_2}$ を求めるために必要な値 を 計算する式がすべて揃った ので、これで $\boldsymbol{m_2}$ を計算できる ようになりました。
下記は 上記ので説明した式 を利用して 0b001001101 に対して 9 ビットのビット列の反転処理 の 1 回目と 2 回目 の 手順 2 の処理を行うプログラムです。なお、$\boldsymbol{b_i}$ の値を代入する 変数の名前 を bi のように命名 しました。上記で説明した式の計算を順番に行っているだけなので説明は省略します。実行結果と 先程の図 を見比べて 正しい処理が行われることが確認 して下さい。
b0 = b
n0 = 9
print(f"b0 = 0b{b0:09b}")
print(f"n0 = {n0}")
print("1 回目の手順 2 の処理")
n1 = n0 // 2
print(f"n1 = {n1}")
d1 = (n0 + 1) // 2
print(f"d1 = {d1}")
m1 = (1 << (n0 // 2)) - 1
print(f"m1 = 0b{m1:09b}")
b1 = delta_swap(b0, m1, d1)
print(f"b0 = 0b{b0:09b}")
print(f"b1 = 0b{b1:09b}")
print()
print("2 回目の手順 2 の処理")
n2 = n1 // 2
print(f"n2 = {n2}")
d2 = (n1 + 1) // 2
print(f"d2 = {d2}")
m2r = (1 << (n1 // 2)) - 1
print(f"m2r = 0b{m2r:09b}")
m2l = m2r << d1
print(f"m2l = 0b{m2l:09b}")
m2 = m2r | m2l
print(f"m2 = 0b{m2:09b}")
b2 = delta_swap(b1, m2, d2)
print(f"b1 = 0b{b1:09b}")
print(f"b2 = 0b{b2:09b}")
実行結果
b0 = 0b001001101
n0 = 9
1 回目の手順 2 の処理
n1 = 4
d1 = 5
m1 = 0b000001111
b0 = 0b001001101
b1 = 0b110100010
2 回目の手順 2 の処理
n2 = 2
d2 = 2
m2r = 0b000000011
m2l = 0b001100000
m2 = 0b001100011
b1 = 0b110100010
b2 = 0b011101000
3 回目の手順 2 のビットマスクの計算方法
3 回目の手順 2 では下図の 赤線と青線 で 4 つに分割 された ビット長が $\boldsymbol{n_2}$ の 各ビット列 を 均等に分割 して delta swap で交換 する処理を行います。
先程と同様 に、3 回目の手順 2 で利用する ビットマスク を表す $\boldsymbol{m_3}$ を、上図のように 4 つに分割 されたビット列に 対応する青、緑、オレンジ、紫 で塗りつぶされた部分に 分けて考える ことにします。
このうちの 右 の 青色と緑色 で塗りつぶされた部分のビット列を $\boldsymbol{m_{3r}}$、左 の オレンジ色と紫色 で塗りつぶされた部分のビット列を $\boldsymbol{m_{3l}}$ と表記すると、その範囲 は 2 回目の 手順 2 で分割した $\boldsymbol{m_{2r}}$ と $\boldsymbol{m_{2r}}$ と同じになる ので、$\boldsymbol{m_3}$ は 下記の式で計算 できます。左シフトでずらすビット数 は $d_2$ ではなく、その 1 つ前の $\boldsymbol{d_1}$ である点に注意して下さい。
$\boldsymbol{m_{3l} = m_{3r} << d_1}$
$\boldsymbol{m_{3} = m_{3r} \ | \ m_{3l}}$
$\boldsymbol{d_1}$ は計算済 なので $\boldsymbol{m_{3r}}$ を計算 できれば、$\boldsymbol{m_{3}}$ を計算できる ことがわかりました。
$\boldsymbol{m_{3r}}$ の 左 にある 青色の部分 を $\boldsymbol{m_{3rl}}$、右 にある 緑色の部分 を $\boldsymbol{m_{3rr}}$ と表記すると、それらは全体の中で右端に並んでいる ので 2 回目の手順 2 と同様の理由から の 下記の式で計算 することができます。こちらの 左シフトでずらすビット数 は $\boldsymbol{d_2}$ です。
$\boldsymbol{m_{3rr} = (1 << n_3) - 1}$
$\boldsymbol{m_{3rl} = m_{3rr} << d_2}$
$\boldsymbol{m_{3r} = m_{3rr} \ | \ m_{3rl}}$
以上で $\boldsymbol{m_3}$ を計算することができるようになりました。
下記は 上記ので説明した式 を利用して 0b001001101 に対して 9 ビットのビット列の反転処理 の 3 回目 の 手順 2 の処理を行うプログラムです。実行結果と 先程の図 を見比べて 正しい処理が行われることが確認 して下さい。
print("3 回目の手順 2 の処理")
n3 = n2 // 2
print(f"n3 = {n3}")
d3 = (n2 + 1) // 2
print(f"d3 = {d3}")
m3rr = (1 << (n2 // 2)) - 1
print(f"m3rr = 0b{m3rr:09b}")
m3rl = m3rr << d2
print(f"m3rl = 0b{m3rl:09b}")
m3r = m3rr | m3rl
print(f"m3r = 0b{m3r:09b}")
m3l = m3r << d1
print(f"m3l = 0b{m3l:09b}")
m3 = m3r | m3l
print(f"m3 = 0b{m3:09b}")
b3 = delta_swap(b2, m3, d3)
print(f"b2 = 0b{b2:09b}")
print(f"b3 = 0b{b3:09b}")
print(f"b = 0b{b:09b}")
実行結果
3 回目の手順 2 の処理
n3 = 1
d3 = 1
m3rr = 0b000000001
m3rl = 0b000000100
m3r = 0b000000101
m3l = 0b010100000
m3 = 0b010100101
b2 = 0b011101000
b3 = 0b101100100
b = 0b001001101
任意の回数の手順 2 のビットマスクの計算方法
上記の例 では 3 回目の手順 2 の処理で すべて の分割された ビット列のビット長が 1 になったので 処理は終了 しますが、最初のビット列 の ビット長がもっと長い 場合は 4 回以上の手順 2 の処理を 行う必要があります。
その場合は、3 回目の手順 2 の ビットマスクを求める手順 を さらに繰り返す ことで ビットマスクを計算 することができます。
具体的には 手順 2 を 1 回繰り返すたび に分割された ビット列の数が倍 になるので、i 回目の手順 2 の処理によって ビット列の数が $\boldsymbol{2^i}$ 個 になります。例えば 4 回目の手順 2 の処理ではビット列を $2 ^ 4$ = 16 個に分割 するので、下記の手順でビットマスクを計算 することができます。なお、先程と同様の表記法 を使った場合は、下記の 手順 1 の式 は $\boldsymbol{m_{3rrr} = (1 << n_4) - 1}$ のようになりますが、わかりづらい と思いましたので ビットマスクの計算の過程を表す記号 を $\boldsymbol{m}$ に統一 して、その値を更新していく ことにしました。
- 下記の式で 右端の 1 個 のビット列を 2 個に分割して交換 する ビットマスクを計算する
$\boldsymbol{m = (1 << n_4) - 1}$ - 下記の式で 上記で求めたビットマスク を利用して、右端からの 2 個分 の ビット列をまとめて合計 4 個に分割して交換 するビットマスクを計算する
$\boldsymbol{m = m \ |\ (m << d3)}$ - 下記の式で 上記で求めたビットマスク を利用して、右端からの 4 個分 の ビット列をまとめて合計 8 個に分割して交換 するビットマスクを計算する
$\boldsymbol{m = m \ |\ (m << d2)}$ - 下記の式で 上記で求めたビットマスク を利用して、右端からの 8 個分 の ビット列をまとめて合計 16 個に分割して交換 するビットマスクを計算する
$\boldsymbol{m = m \ |\ (m << d1)}$
上記から、最初の処理の後 では 左シフト演算 で ずらすビット数以外 は 同じ処理を繰り返し行う ことがわかります。また、左にずらすビット数 は 毎回増えて いき、手順 2 の処理で 過去に利用した delta の値 を 順番にさかのぼって利用する ことがわかります。何故そのようになるかについてわからない方は、図を描いて確認 することをお勧めします。
下記は i 回目の手順 2 のビットマスクを計算するアルゴリズムです。
下記の処理 を 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{d_{i-j}}$は、過去の delta を 順番に遡って利用する ことを表します。
reverse6 の定義
下記は上記で説明したアルゴリズムでビット列の反転処理を行う reverse6 を定義するプログラムです。
-
2 行目：過去の
deltaを記録する変数を空の list で初期化する -
3 行目：分割したビット列の長さを表す
lengthが1になるまで繰り返し処理を行う。最初は分割されていない状態なのでlengthはbのビット長が代入されている -
4 行目：手順 2 の
deltaをlengthから計算する -
5 行目：手順 2 で分割したビット列のビット長を計算して、
lengthを更新する - 6 行目：分割された右端のビット列に対応するビットマスクを計算する
-
7、8 行目：過去に計算した
deltaをdeltalist[::-1]によってdeltalistの逆順で新しく計算した順に取り出すことで、先程示した手順でビットマスクを計算する。繰り返す回数は、過去に計算したdeltaの回数と等しいので、回数を数える必要はない -
9 行目：計算したビットマスクと
deltaを利用して delta swap の計算を行う -
10 行目：今回の手順 2 の処理で計算した
deltaをdeltalistの要素に追加する -
11 行目：繰り返し処理が終わった時点で
bのビット列を反転した値がbに計算されているので、それを返り値として返す
1 def reverse6(b, length):
2 deltalist = []
3 while length > 1:
4 delta = (length + 1) // 2
5 length //= 2
6 mask = (1 << length) - 1
7 for d in deltalist[::-1]:
8 mask |= mask << d
9 b = delta_swap(b, mask, delta)
10 deltalist.append(delta)
11 return b
行番号のないプログラム
def reverse6(b, length):
deltalist = []
while length > 1:
delta = (length + 1) // 2
length //= 2
mask = (1 << length) - 1
for d in deltalist[::-1]:
mask |= mask << d
b = delta_swap(b, mask, delta)
deltalist.append(delta)
return b
下記は 先程と同じ反転処理 を reverse6 で行うプログラムです。実行結果は先ほどと同じ なので省略しますが、実行結果から reverse6 が正しい処理を行う ことが確認できました。
for length in range(8, 17):
print(f"bit length = {length}")
print(f"0b{b:0{length}b}")
print(f"0b{reverse6(b, length):0{length}b}")
下記は reverse6 の 処理速度を計測 するプログラムです。reverse6 のアルゴリズムは 1 のビットの数に影響されない ので 0b01001101 に対する計測だけ を行いました。
for length in [10, 100, 1000, 10000, 100000, 1000000]:
print(f"bit length = {length}")
%timeit reverse6(b, length)
実行結果
bit length = 10
1.57 μs ± 17.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)
bit length = 100
4.6 μs ± 71.2 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 1000
10.1 μs ± 172 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
bit length = 10000
39.7 μs ± 405 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
bit length = 100000
239 μs ± 1.44 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)
bit length = 1000000
2.59 ms ± 10.2 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)
下記は 最も時間がかかる、すべてのビットが 1 の場合の reverse1、reverse2 と上記の実行結果をまとめた表です。reverse5 は reverse1 と処理時間があまり変わらないので省略しました。
| ビット長 | reverse1 |
倍率 | reverse2 |
倍率 | reverse6 |
倍率 |
|---|---|---|---|---|---|---|
| 10 | 1.5 | 1.1 | 1.6 | |||
| 100 | 18.9 | 12.7 | 16.0 | 14.2 | 4.6 | 2.9 |
| 1,000 | 241.0 | 12.8 | 213.0 | 13.3 | 10.1 | 2.2 |
| 10,000 | 5,050.0 | 21.0 | 5,340.0 | 25.1 | 39.7 | 3.9 |
| 100,000 | 191,000.0 | 37.8 | 285,000.0 | 53.4 | 239.0 | 6.0 |
| 1,000,000 | 1,560,000.0 | 81.7 | 26,500,000.0 | 93.0 | 2,590.0 | 10.8 |
上記の表から reverse6 のアルゴリズムは reverse1 や reverse2 と比較して以下のような性質を持つことがわかりました。
- ビット長が 10 の場合は処理速度はあまり変わらないが ビット長が 100 を超える と 圧倒的に高速 になる
- ビット長が 100,000 以下 の場合の 処理時間 は ビット長の比例よりも緩やかに増える
- ビット長が 1,000,000 の場合は 処理時間 は ビット長にほぼ比例する
実は、reverse6 で ビットマスクを計算するアルゴリズム はあまり 効率が良いものではありません。次回の記事では もっと効率の良い ビットマスクを計算する アルゴリズムを紹介する ので、余裕がある方はその方法について少し考えてみて下さい。
今回の記事のまとめ
今回の記事では さまざまなビット列の反転処理 を行うアルゴリズムを紹介し、その中で分割統治法を利用したアルゴリズムが最も高速であることを示しました。次回の記事では reverse6 を改良したアルゴリズムや、他のアルゴリズムなどを紹介する予定です。
本記事で入力したプログラム
| リンク | 説明 |
|---|---|
| marubatsu.ipynb | 本記事で入力して実行した JupyterLab のファイル |
次回の記事
-
ただし、ビット長が奇数の場合に分割される真ん中の 1 ビットのビット列は除きます ↩