では、先ほどの Notebook をさらに発展させて、爆発的バックトラッキングの試行回数が指数的に増える様子をアニメーションで可視化する教材にします。
Python では matplotlib.animation を使って、(a+)+ のパターンに対するバックトラック試行の増加を視覚化できます。
Notebook アニメーション化例
# ==========================
# セル7: バックトラック試行回数のアニメーション
# ==========================
import matplotlib.pyplot as plt
import matplotlib.animation as animation
# シンプルモデル：文字列長 n に対するバックトラック試行回数を指数関数でシミュレーション
n_max = 15
x = list(range(1, n_max+1))
# (a+)+ で試行回数は 2^(n-1) に近似
y = [2**(i-1) for i in x]
fig, ax = plt.subplots()
line, = ax.plot([], [], 'ro-', lw=2)
ax.set_xlim(0, n_max+1)
ax.set_ylim(0, max(y)*1.1)
ax.set_xlabel('文字列長 n')
ax.set_ylabel('バックトラック試行回数')
ax.set_title('Catastrophic Backtrackingの試行回数増加')
def init():
line.set_data([], [])
return line,
def animate(i):
line.set_data(x[:i+1], y[:i+1])
return line,
ani = animation.FuncAnimation(fig, animate, frames=n_max, init_func=init, blit=True, repeat=False)
plt.show()
説明
x：文字列の長さ（1文字〜15文字）y：バックトラック試行回数の概算（指数関数的に増加）- 赤丸で「試行回数」を順番に描画 → 文字数が増えると瞬時に指数的に増える様子がわかる
- 実務で
(a+)+のような危険パターンを使うと、文字列長が少し増えただけでも 処理が爆発的に遅くなることが直感的に理解できる
Notebook 全体の流れ
- 危険パターンと安全パターンの表
- 危険パターンの処理時間計測
- 安全パターンの処理時間計測
- 爆発的バックトラッキングの分岐図
- アニメーションで指数的試行回数を可視化
💡 この Notebook を使うと：
- 「なぜ遅くなるのか」が図で直感的に理解できる
- 安全な書き換え例の重要性が実務レベルで体感できる
- 講義や社内研修にもそのまま使える教材になる