- 効率化したコードのバグを防ぐため、遅くても正しい素朴な実装をオラクルとして残し、累積和などの効率版と結果を突き合わせる手法を紹介します。
- テストには Common Lisp の parachute ライブラリと macrolet を使い、境界条件を手動で選んだ固定ケースと、乱数で生成した大量のケースを同じテスト内に並べて実行します。
- #+swank で囲むことで、テストコードは SLIME の REPL 上でのみ評価され、提出コードには含まれません。
- テストが通ったあとは get-internal-real-time でベンチマークを取り、n を倍々に増やして実行時間の比から計算量を実測して確認します。
効率化したコードは間違えやすいです。
累積和のインデックスがずれたり、境界条件を見落としたり。
遅くても正しい素朴な実装をオラクルとして残しておいて、効率化したコードと突き合わせる方法を紹介します1。
1. 題材：区間和クエリ
長さ N の数列 A と、Q 個のクエリ (L, R) が与えられます。
各クエリに対して、A_L + A_{L+1} + … + A_R を求めてください。
制約は N, Q ≤ 10^5 程度を想定します。
1.1. まず素朴な実装を書く
ループで区間を毎回足す O(NQ) の実装です。
遅いですが、正しさは明らかです2。
(defun range-sum-naive (A L R)
(loop for i from L to R
sum (nth (1- i) A)))Code language: Lisp (lisp)1.2. 累積和で効率化する
前計算で累積和を作っておけば、各クエリを O(1) で答えられます3。
(defun build-prefix (A)
(let* ((n (length A))
(prefix (make-array (1+ n) :initial-element 0)))
(loop for i from 1 to n
do (setf (aref prefix i)
(+ (aref prefix (1- i))
(nth (1- i) A))))
prefix))
(defun range-sum-prefix (prefix L R)
(- (aref prefix R)
(aref prefix (1- L))))Code language: Lisp (lisp)インデックスの起算が 1 か 0 か、境界が (1- L) か L か、こういった細かい部分でバグが入りやすいです。
2. macrolet でオラクルと突き合わせる
macrolet を使うと、同じ構造のテストケースを一行ずつ並べて書けます4。
#+swank で囲むと、SLIME の REPL 上だけで評価され、提出コードには含まれません5。
#+swank
(progn
(ql:quickload :parachute)
(let* ((A '(3 1 4 1 5 9 2 6)))
(parachute:define-test range-sum-test
(macrolet ((tc (l r)
`(parachute:is =
(range-sum-naive A ,l ,r)
(range-sum-prefix (build-prefix A) ,l ,r))))
(tc 1 1)
(tc 1 8)
(tc 3 6)
(tc 4 4)
(tc 1 3)
(tc 6 8))))
(parachute:test 'range-sum-test))Code language: Lisp (lisp)テストケースを追加するのは (tc L R) を一行足すだけです。
失敗すると、期待値と実際の値が並んで表示されるので、どこがずれているかすぐわかります6。
2.1. テストを活用するコツ
素朴な実装で怪しいケースを先に調べておくと、テストケースの選び方が自然と決まります。
たとえば累積和なら、L = R = 1（先頭の一要素）、L = 1, R = N（全体）、右端や左端が絡むケースあたりを押さえておくだけで、インデックスのずれはほぼ捕まえられます。
効率化した実装がテストを通ったら、素朴な実装はそのまま残しておいて構いません。#+swank で囲んであるので、提出コードには含まれないからです。
3. ランダム入力で大量に突き合わせる
境界条件は手で選びますが、それ以外は乱数で大量に試す方が見落としを減らせます7。
まず、ランダムな数列とクエリを作る関数を用意します。
(defun make-random-input (n &key (max-val 100))
(loop repeat n collect (1+ (random max-val))))
(defun make-random-query (n)
(let* ((l (1+ (random n)))
(r (+ l (random (- n l -1)))))
(cons l r)))Code language: Lisp (lisp)macrolet は意図して選んだ固定ケースに使い、ランダムなケースは loop で回します。
同じ define-test の中に並べて書けます。
#+swank
(progn
(ql:quickload :parachute)
(let* ((A '(3 1 4 1 5 9 2 6)))
(parachute:define-test range-sum-test
(macrolet ((tc (l r)
`(parachute:is =
(range-sum-naive A ,l ,r)
(range-sum-prefix (build-prefix A) ,l ,r))))
(tc 1 1)
(tc 1 8)
(tc 3 6)
(tc 4 4)
(tc 1 3)
(tc 6 8))
(loop repeat 100
for a = (make-random-input 50)
for (l . r) = (make-random-query (length a))
do (parachute:is =
(range-sum-naive a l r)
(range-sum-prefix (build-prefix a) l r)))))
(parachute:test 'range-sum-test))Code language: Lisp (lisp)100回試して全部通れば、かなり安心できます。
失敗したときは期待値と実際の値が表示されますが、どの入力で失敗したかはわかりません。print を挟んで a、l、r を出力しながら再実行すると、再現ケースを固定ケースに追加できます。
3.1. time で計算量を実測する
テストが通ったら、本当に速くなっているかを確認します。n を倍々に増やして実行時間の比を見れば、O(n) なら比が約 2 倍、O(n²) なら約 4 倍に近づきます8。
(defun make-bench (f)
(lambda (n)
(let* ((a (make-random-input n))
(prefix (build-prefix a)))
(loop repeat n
for (l . r) = (make-random-query n)
do (funcall f a prefix l r)))))
(defun calc-order (bench &key (base 500) (steps 4) (repeat 3))
(loop for i from 0 below steps
for n = (* base (expt 2 i))
for times = (loop repeat repeat
collect (let ((start (get-internal-real-time)))
(funcall bench n)
(- (get-internal-real-time) start)))
for avg = (/ (reduce #'+ times) (float repeat))
collect (cons n avg) into results
finally
(loop for ((n1 . t1) (n2 . t2)) on results
while t2
do (format t "n=~a -> n=~a ratio: ~,2f~%"
n1 n2 (/ t2 t1)))))Code language: Lisp (lisp)呼び出しはこうなります。
#+swank
(progn
(calc-order
(make-bench (lambda (a _prefix l r)
(range-sum-naive a l r))))
(calc-order
(make-bench (lambda (_a prefix l r)
(range-sum-prefix prefix l r)))))Code language: Lisp (lisp)素朴な実装は ratio が 4 に近く、累積和版は 2 に近い値になるはずです。
GC のタイミングで多少ぶれるので、repeat を増やすと安定します。
- テストオラクルとは、プログラムの出力が正しいかどうかを判定する別の仕組みのことです。素朴な実装（ブルートフォース）をオラクルとして使う手法は、競技プログラミングで広く使われています。 – Test oracle: A useful tool for competitive programmers
- この実装の計算量は O(NQ) です。N, Q がともに 10^5 の場合、最大で 10^10 回の演算が必要になり、制限時間内に終わりません。
- 累積和（prefix sum）は、前計算に O(N) かかりますが、クエリの応答は O(1) になります。全体の計算量は O(N + Q) です。 – 累積和 – Wikipedia
macroletはローカルスコープのマクロを定義する特殊形式です。letと同様にスコープが限定されますが、コンパイル時に展開される点が異なります。ここではテストケースの引数パターンを短く書くために使っています。 – The Common Lisp Cookbook – Macros- SWANK は SLIME のバックエンドサーバです。SLIME 接続中はこのパッケージがロードされているため、
(find-package :swank)で SLIME 上かどうかを判定できます。#+swankはその判定を利用したリーダーマクロです。 – 【Common Lisp】コードの修正で自動テストするには？（Parachute） - Parachute の
isは(is 比較関数 期待値 実測値)の順に引数を取ります。失敗時は「実測値 evaluated to X when Y was expected」という形式で表示されます。 – shinmera/parachute - 素朴な実装をオラクルとして乱数入力で大量テストする手法は、プロパティベーステストと呼ばれます。手動でテストケースを選ぶより、入力空間を広く探索できます。 – Property-based Testing and Test Oracles
- この手法はアルゴリズムの経験的な計算量確認によく使われます。
get-internal-real-timeの返す値はinternal-time-units-per-secondで割ると秒単位になります。SBCL では通常ミリ秒単位です。 – The Common Lisp Cookbook – Dates and Times