Section 5 まででアルゴリズムの主要な設計パターンを網羅しました。
Section 6 は「実践的な典型アルゴリズム」と「処理系レベルの最適化」をまとめます。
前半（問題 43〜46）はグラフアルゴリズムの発展とデータ表現の工夫です。
トポロジカルソート・到達可能性・疎行列・2次元累積和を扱います。
「データの表現形式を変えること」がアルゴリズムの計算量を変える例が続きます。
後半（問題 47〜48）は SBCL の型宣言による定数倍の高速化です。
Section 1〜5 はすべて「計算量のオーダーを変える」改善でしたが、オーダーが最適になったあとはコンパイラへの型情報の提供で 5〜20 倍の差が出ることがあります。
1. グラフとデータ表現（問題 43〜46）
Section 5 でグラフの連結判定・最短路を扱いました。
ここではグラフ操作のさらなる応用と、「データの表現形式を変えること」がアルゴリズムの計算量を変える例を確認します。
2. 問題43 トポロジカルソート
頂点数 n と有向辺のリスト edges を受け取り、トポロジカル順序（依存関係を満たす順序）を返す関数を書いてください。
サイクルがある場合はエラーを発生させます。
入力: n = 6
edges = ((5 2) (5 0) (4 0) (4 1) (2 3) (3 1))
出力: (5 4 2 3 1 0) など (複数の正解がある)
入力: n = 4
edges = ((0 1) (0 2) (1 3) (2 3))
出力: (0 1 2 3) または (0 2 1 3)
入力: n = 3
edges = ((0 1) (1 2) (2 0))
出力: エラー ← サイクルありビルドシステムの依存解決、科目の履修順序決定、タスクのスケジューリングなどで使います。
Kahn のアルゴリズムは BFS の変形で、サイクル検出も自然にできます。
問題42（BFS）の変形です。
入次数 0 のノードを順に取り出すという BFS 的な操作が核心です。
(defun topological-sort (n edges)
"Kahn のアルゴリズム。入次数 0 のノードを順に取り出す。"
(let ((in-degree (make-array n :initial-element 0))
(graph (make-array n :initial-element nil))
(result '()))
(dolist (edge edges)
(destructuring-bind (u v) edge
(push v (aref graph u))
(incf (aref in-degree v))))
(let ((queue (loop for i from 0 below n
when (zerop (aref in-degree i))
collect i)))
(loop while queue do
(let ((v (pop queue)))
(push v result)
(dolist (neighbor (aref graph v))
(decf (aref in-degree neighbor))
(when (zerop (aref in-degree neighbor))
(push neighbor queue)))))
(if (= (length result) n)
(nreverse result)
(error "Graph has a cycle")))))Code language: Lisp (lisp)全頂点が処理されなければサイクルあり。
Kahn のアルゴリズムはサイクル検出が (length result) の比較だけで自然にできます。
DFS 版より実装しやすいのが特徴です。
3. 問題44 グラフの到達可能性と隣接リスト化
有向辺のコンスペアのリスト edges と始点 start、終点 goal を受け取り、start から goal に到達できれば t、できなければ nil を返す関数を書いてください。
入力: edges = ((a . b) (b . c) (c . d) (a . d))
start = a, goal = d
出力: t
入力: edges = ((a . b) (b . c))
start = c, goal = a
出力: nil ← 有向グラフなので逆向きには行けない
入力: edges = ((1 . 2) (2 . 3) (3 . 1)) ← サイクルあり
start = 1, goal = 4
出力: nil
入力: edges = ()
start = x, goal = x
出力: t ← 始点と終点が同じ辺リストをそのまま使って毎ステップ全走査すると O(E²) になります。
隣接リストに変換し visited で再訪を防ぐと O(V + E) になります。
問題41・42では最初から隣接リストで与えられていました。
問題44は「辺リストのまま使う」と何が起きるかを確認します。
3.1. 素直な実装 — 辺リストを毎回全走査
(defun reachable-naive (edges start goal)
"辺リストを直接使って DFS する。再訪防止もない。"
(cond
((eql start goal) t)
(t
(some (lambda (e)
(and (eql (car e) start)
(reachable-naive edges (cdr e) goal)))
edges))))Code language: Lisp (lisp)someは、リストの要素のうち少なくとも1つが条件を満たすか判定し、最初に t が返った時点で終了します。
辺リストを毎回全走査 + 再訪防止なし → 最悪 O(E²)。
3.2. 効く実装 — 隣接リスト + visited で O(V + E)
(defun build-adjacency-list (edges)
"辺リストを隣接リストに変換する。"
(let ((g (make-hash-table :test #'eql)))
(dolist (e edges g)
(push (cdr e) (gethash (car e) g nil)))))
(defun reachable-fast (edges start goal)
(let ((graph (build-adjacency-list edges))
(visited (make-hash-table :test #'eql)))
(labels ((dfs (u)
(cond
((eql u goal) t)
((gethash u visited) nil)
(t
(setf (gethash u visited) t)
(some #'dfs (gethash u graph nil))))))
(dfs start))))Code language: Lisp (lisp)グラフを「辺リストのまま毎回走査する」実装は O(E) × 深さになります。
隣接リストに変換すれば DFS/BFS 全体が O(V + E) になります。
Section 4 の発想と同じく、「前処理でクエリを速くする」設計です。
4. 問題45 疎行列の積
非ゼロ要素を (行 列 値) のトリプルで表現した疎行列 a-triples と b-triples を受け取り、積 C = A × B の非ゼロ要素をトリプルのリストで返す関数を書いてください。
入力: a-triples = ((0 0 1) (0 1 2) (1 2 3))
対応する行列 A:
[[1 2 0]
[0 0 3]]
b-triples = ((0 0 4) (1 0 5) (2 1 6))
対応する行列 B:
[[4 0]
[5 0]
[0 6]]
出力: ((0 0 14) (1 1 18))
対応する積 C:
[[14 0]
[ 0 18]]
C[0][0] = 1*4 + 2*5 = 14
C[1][1] = 3*6 = 18ほとんどが 0 の行列では、密行列の O(nmp) の計算のうち大半が「0 × 何か」です。
非ゼロ要素だけを処理すると計算量が非ゼロ要素数に比例します。
データの「ゼロを持たない」という表現の変化がアルゴリズムの複雑度を変える例です。
4.1. 素直な実装 — O(n²m)
(defun matmul-dense (a b)
"密行列の積。ほとんどが 0 でも全要素を処理する。"
(let* ((n (array-dimension a 0))
(m (array-dimension a 1))
(p (array-dimension b 1))
(c (make-array (list n p) :initial-element 0)))
(loop for i below n do
(loop for j below p do
(loop for k below m do
(incf (aref c i j) (* (aref a i k) (aref b k j))))))
c))Code language: Lisp (lisp)array-dimensionは、配列の指定次元のサイズを返します。
4.2. 効く実装 — 非ゼロ要素だけ処理する
疎行列：(row col value) のトリプルのリスト。
例：((0 1 3.0) (1 2 -1.5)) は a[0][1]=3.0, a[1][2]=-1.5 を意味する。
(defun sparse-to-row-map (triples)
"トリプルリストを「行 → ((列 . 値) ...)」のハッシュテーブルに変換する。"
(let ((rows (make-hash-table :test #'eql)))
(dolist (trip triples rows)
;; destructuring-bind：リストをパターンマッチで変数に分解する。
;; (destructuring-bind (i j v) '(0 1 3.0) ...) で i=0, j=1, v=3.0 になる。
(destructuring-bind (row col val) trip
(push (cons col val) (gethash row rows nil))))))
(defun sparse-matmul (a-triples b-triples)
"非ゼロ要素だけを掛け合わせる。"
(let ((b-rows (sparse-to-row-map b-triples))
(result (make-hash-table :test #'equal)))
(dolist (a-trip a-triples)
(destructuring-bind (ai ak va) a-trip
(dolist (b-entry (gethash ak b-rows nil))
(let* ((bj (car b-entry))
(vb (cdr b-entry))
(key (cons ai bj)))
(incf (gethash key result 0) (* va vb))))))
(let ((out nil))
(maphash (lambda (k v) (push (list (car k) (cdr k) v) out)) result)
out)))Code language: Lisp (lisp)destructuring-bind はリストを変数に分解する強力な構文です。
「0 を持たない」という表現の変化だけで、計算量が非ゼロ要素数に比例します。
データの性質を表現に反映させることが大切です。
5. 問題46 行列の区間クエリ（2次元累積和の活用）
n × m の整数行列 matrix が与えられます。
前処理として2次元累積和を構築し、矩形クエリ「行 r1 から r2、列 c1 から c2 の要素の合計」を O(1) で答える関数を書いてください。
matrix = [[3 0 1 4 2]
[5 6 3 2 1]
[1 2 0 1 5]
[4 1 0 1 7]
[1 0 3 0 5]]
(rect-sum ps 0 0 5 5) → 40 ← 全体の合計
(rect-sum ps 0 0 2 2) → 14 ← 左上2×2: 3+0+5+6 = 14
(rect-sum ps 2 1 4 3) → 3 ← 行2-3、列1-2: 2+0+1+0 = 3画像の矩形領域の輝度合計、2次元ヒストグラムの集計など、クエリが多数ある場面で前処理が効きます。
包除原理で4点の累積和の加減算だけで答えられます。
問題20（1次元累積和）の2次元版です。
前処理で O(n²) の構造を作り、クエリを O(1) にします。
(defun make-2d-prefix-sums (matrix rows cols)
"2次元累積和を構築する。O(rows × cols)。"
(let ((ps (make-array (list (1+ rows) (1+ cols))
:initial-element 0)))
(loop for i from 1 to rows do
(loop for j from 1 to cols do
(setf (aref ps i j)
(+ (aref matrix (1- i) (1- j))
(aref ps (1- i) j)
(aref ps i (1- j))
(- (aref ps (1- i) (1- j)))))))
ps))
(defun rect-sum (ps r1 c1 r2 c2)
"矩形 [r1, r2) × [c1, c2) の合計を O(1) で返す。"
(- (aref ps r2 c2)
(aref ps r1 c2)
(aref ps r2 c1)
(- (aref ps r1 c1))))Code language: Lisp (lisp)1次元の累積和（問題20）と包除原理（全体から上を引いて左を引いて、二重に引いた部分を足す）を組み合わせると2次元に拡張できます。
「前処理のコストを後のクエリで回収する」設計が一貫しています。
6. 型宣言による定数倍の高速化（問題 47〜48）
Section 1〜6 前半まではすべて「計算量のオーダーを変える」改善でした。
ここでは、オーダーが最適になったあとの「定数倍の改善」を扱います。
SBCL 固有の知識ですが、数値集中コードでは 5〜20 倍の差が出ることがあります。
7. 問題47 型宣言による数値演算の高速化
fixnum 型の整数ベクタ vec の要素をすべて合計する関数を書いてください。
型宣言なし版と型宣言あり版を比較します。
入力: vec = (make-array 10000000 :element-type 'fixnum
:initial-contents (loop for i from 1 to 10000000 collect (mod i 100)))
(time (sum-vector-untyped vec))
→ Evaluation took: 0.250 seconds ...
(time (sum-vector-typed vec))
→ Evaluation took: 0.018 seconds ...Code language: PHP (php)型宣言なし版は各 aref に型チェックと boxed 演算が入ります。declare で fixnum を宣言すると SBCL はネイティブの整数加算命令を直接出力し、10倍以上高速になります。
7.1. 型宣言なし
(defun sum-vector-untyped (vec)
"型情報がないため、処理系は汎用パスで計算する。"
(let ((sum 0))
(dotimes (i (length vec) sum)
(incf sum (aref vec i)))))Code language: Lisp (lisp)7.2. 型宣言あり
declareは、コンパイラへの宣言。実行に影響しないが最適化に使われます。
- optimize：最適化の優先度を指定する。各項目は 0〜3。
- speed：実行速度を優先する。
- safety：実行時チェックの量。0 にすると境界チェックが省略される。
- debug：デバッグ情報の量。
(defun sum-vector-typed (vec)
"型宣言で処理系に最適化のヒントを与える。"
(declare (optimize (speed 3) (safety 0) (debug 0)))
(make-array n) はデフォルトで simple-array を返す。
(declare (type (simple-array fixnum (*)) vec))
(let ((sum 0))
(declare (type fixnum sum))
(dotimes (i (length vec) sum)
(declare (type fixnum i))
(incf sum (aref vec i)))))Code language: Lisp (lisp)type 宣言：変数の型を宣言する。
simple-array：調整可能フラグ・fill-pointer を持たない「単純配列」、最もアクセスが速い配列型。
型を指定した配列の作り方：
;; :element-type で要素の型を指定した配列を作る。
;; 処理系はこれを使ってメモリレイアウトを最適化する。
(make-array 100 :element-type 'fixnum :initial-element 0) ; 整数配列
(make-array 100 :element-type 'double-float :initial-element 0.0d0) ; 倍精度浮動小数
(make-array n :element-type 'bit :initial-element 0) ; ビット配列（問題32）Code language: PHP (php)the フォームによるインライン型アサーション：
(defun dot-product (a b)
(declare (optimize (speed 3) (safety 0))
(type (simple-array double-float (*)) a b))
(let ((sum 0.0d0))
(declare (type double-float sum))
(dotimes (i (length a) sum)
(incf sum (* (the double-float (aref a i))
(the double-float (aref b i)))))))Code language: Lisp (lisp)(the type form)は、form の値が type であることを宣言します。
型チェックは行われず、コンパイラへのヒントになる。
(safety 0) は境界チェックを省くため、デバッグ時は (safety 1) で動作確認してから最終段階で適用してください。
8. 問題48 インライン宣言と declaim
fixnum 型の整数ベクタを昇順にソートする関数を書いてください。
型宣言と (declare (inline sort)) の有無による速度差を確認します。
入力: vec = (let ((v (make-array 100000 :element-type 'fixnum)))
(dotimes (i 100000) (setf (aref v i) (- 100000 i)))
v)
(time (sort-fixnum-vector (copy-seq vec)))
→ inline なし: 約 0.08 seconds
inline あり: 約 0.04 seconds (型情報の静的ディスパッチで高速化)Code language: PHP (php)SBCL の sort は maybe-inline のため、デフォルトではインライン化されません。(declare (inline sort)) を追加することで要素型の静的ディスパッチが行われ、比較関数の呼び出しコストが下がります。
declaimは、ファイルレベルでのコンパイラ宣言です。
(declare …) は関数内のみ有効で、(declaim …) はそれ以降のトップレベルに影響します
(declaim (ftype (function (fixnum fixnum) fixnum) fast-add))
(defun fast-add (a b)
(declare (optimize (speed 3) (safety 0)))
(the fixnum (+ a b)))
(defun sort-fixnum-vector (vec)
(declare (inline sort)
(optimize (speed 3) (safety 0))
(type (simple-array fixnum (*)) vec))
(sort vec #'<))Code language: Lisp (lisp)ftypeは、関数の引数型・戻り値型を宣言する。
(function (fixnum fixnum) fixnum) は「fixnum 2つを受け取り fixnum を返す」関数。
declaim はファイル全体に影響するため、型宣言を関数単位で管理したいときは declare を使います。
推測で最適化するより、time マクロや sb-sprof:with-profiling で実測してボトルネックを特定してから手を入れるのが正しい手順です。
sort は maybe-inline として定義されています。
デフォルトではインライン化されず、要素型の静的ディスパッチが行われない。
しかし、(declare (inline sort)) を関数内に書くとインライン展開されます。
maybe-inline な組み込み関数の例： digit-char-p, nthcdr, read-char, read-byte
タイトなループで使うときは (declare (inline …)) をすると、効率がよくなるかもしれません。
disassembleは、関数のコンパイル済みコードを表示します。
型宣言の有無でアセンブリがどう変わるか確認できます。
(disassemble #'sum-vector-untyped)
(disassemble #'sum-vector-typed)Code language: Lisp (lisp)型宣言ありの版では boxed な汎用呼び出しが消えて、fixnum の add 命令に直接変換されているのが見えます。
time マクロは、フォームの実行時間と GC 情報を表示します。
(time (sieve-of-eratosthenes 1000000))
;; => Evaluation took:
;; 0.045 seconds of real time
;; ...Code language: Lisp (lisp)