【Section 0】
パフォーマンスの基礎
（Common Lispと計算効率）

by
  • Common Lispで計算効率を学ぶ48題のシリーズで、O(n²)をO(n)やO(1)に改善する実装を扱います。
  • Big-O記法を使ってアルゴリズムの増え方を測り、入力サイズが大きくなるほどオーダーの差が実行時間に直結します。
  • push+nreverseパターン、ハッシュテーブルへの置き換え、累積和など、頻出の最適化手法を体系的に学びます。

関連記事

1. 概要

実装の選択によって O(n²) が O(n log n) や O(1) に変わる問題を48題扱います。
各問題では「素直な実装」と「効く実装」を示し、構文・標準関数・アルゴリズムの三層すべてを丁寧に解説します。
動作確認は SBCL 2.x を想定しています。

48題を6つのセクションに分けており、「日常的な最適化 → アルゴリズム設計 → 処理系の活用」という難易度曲線になっています。
前のセクションで学んだ技法が後のセクションで前提になるため、順に読むことを推奨します。

  • Section 1（問題 1〜5）：基本のリスト操作と走査最適化。
    push＋nreverse パターンを徹底します。
  • Section 2（問題 6〜13）：線形探索からハッシュテーブルへ。
    member・assoc・nth をハッシュテーブルに置き換える体系的な手法を学びます。
  • Section 3（問題 14〜19）：データ構造の選択。
    リスト（連結リスト）とベクタ（配列）の使い分け、ソート済み入力の活用。
    ここまでで「基本的な性能改善の大半」をカバーします。
  • Section 4（問題 20〜28）：前処理と区間アルゴリズム。
    累積和・文字位置インデックス・top-k・スライディングウィンドウをまとめて扱います。
  • Section 5（問題 29〜42）：再帰・分割統治・動的計画法。
    メモ化、DP テーブル、ローリング配列。
    フィボナッチ、べき乗、素数から LCS・ナップサック・グラフまで進みます。
  • Section 6（問題 43〜48 ＋ 付録）：典型アルゴリズムと実装最適化。
    DFS・BFS・Union-Find・KMP・型宣言・SBCL 実践設定をまとめます。

2. 計算量とBig-O記法

アルゴリズムの「速さ」を測るには、実行時間をストップウォッチで計るより先に、「入力サイズが増えたときにステップ数がどう増えるか」を知る必要があります。
同じコードでもマシンが変われば実行時間は変わりますが、ステップ数の増え方は変わりません。
この増え方を記述するのが Big-O 記法です。

正式には、関数 f(n) について「f(n) が O(g(n)) である」とは、十分大きな n に対して f(n) ≤ c × g(n) を満たす定数 c > 0 が存在することを意味します。
言い換えると、「定数倍の差は無視して、増え方の形だけを見る」記法です。

実際のコードでは、基本操作（比較・代入・セルの生成など）を1ステップと数えて、入力サイズ n に対してステップ数がどんな式で表せるかを考えます。
係数や低次の項は無視します。
たとえば 3n + 100 も 0.5n も、どちらも O(n) として扱います。

2.1. 主要なオーダーとその意味

このシリーズで登場する主なオーダーを、小さい順に並べます。

  • O(1)　定数時間
    n に関わらず一定のステップ数で終わります。
    リストの先頭への cons 操作や、ハッシュテーブルへのアクセスがこれにあたります。
  • O(log n)　対数時間
    n が2倍になるとステップ数が1増えます。
    二分探索や、ヒープ・バランス木への挿入がこれにあたります。
    n = 10^9 でも約30ステップしかかかりません。
  • O(n)　線形時間
    n に比例してステップ数が増えます。
    リストを先頭から末尾まで一度だけ走査する操作です。
  • O(n log n)　線形対数時間
    比較ベースのソートの下限がこれです。
    SBCL の sort はマージソートベースで O(n log n) になります。
  • O(n²)　二乗時間
    n の二乗に比例します。
    「長さ n のリストに対して O(n) の操作を n 回繰り返す」ときに発生します。
    たとえばループの中で append を毎回呼ぶと、ループのたびにリスト全体をコピーするため、合計ステップ数が 0 + 1 + 2 + … + (n-1) = n(n-1)/2 になります。

2.2. オーダーの差が実行時間にどう現れるか

同じ問題を O(n) と O(n²) で解いたとき、n が大きくなるにつれて差はどう広がるかを示します。

n = 1,000 のとき：
  O(n)   →       1,000 ステップ
  O(n²)  →   1,000,000 ステップ（1,000倍）

n = 10,000 のとき：
  O(n)   →      10,000 ステップ
  O(n²)  → 100,000,000 ステップ（10,000倍）

n = 100,000 のとき：
  O(n)   →       100,000 ステップ
  O(n²)  → 10,000,000,000 ステップ（100,000倍）

n が10倍になると、O(n) のステップ数も10倍ですが、O(n²) は100倍になります。
競技プログラミングでは n = 10^5 程度でタイムアウトの境界になることが多く、O(n²) では通らないが O(n log n) なら通る、という場面が頻繁に出てきます。

このシリーズ全体を通じて、「O(n²) になっている箇所を見つけて O(n) に直す」というパターンを繰り返します。

3. Common Lisp の基本構文

登場頻度の高い構文を4つのグループに分けて整理します。
各グループで、構文の説明・コード例・パフォーマンス上の注意点の順に示します。

Common Lisp 基本構文 変数と束縛 let : 同時束縛 let* : 逐次束縛（前を参照可） setf : 場所への汎用代入 (setf x 42) 繰り返し dotimes : 固定回数ループ dolist : リスト走査 loop collect : O(n)でリスト構築 (loop for x in lst collect x) 関数定義 defun : トップレベル関数 labels : ローカル再帰関数 末尾再帰 → SBCLが最適化 (labels ((rec (k) …)) …) cons セル cons : O(1) で先頭追加 push + nreverse : 末尾追加の定石 append : O(n) コピー発生 (push x lst) → (nreverse lst)

3.1. 変数と束縛（let, let*, setf）

let は複数の変数を同時に束縛します。
右辺の評価は「let に入る前」の環境で行われるため、(let ((x 1) (y x)) ...) と書いても y は外側の x を参照します（存在しなければエラー）。
let* は前の束縛を後の右辺で参照できる逐次束縛です。
setf は変数だけでなく「場所（place）」に値を代入する汎用代入マクロで、配列要素・構造体スロット・ハッシュテーブルエントリなど、setf できる対象は言語全体で統一されています。

(let ((x 10)
      (y 20))
  (+ x y))  ; => 30

(let* ((x 10)
       (y (* x 2)))   ; x を参照できる
  y)  ; => 20

(let ((x 0))
  (setf x 42)
  x)  ; => 42Code language: JavaScript (javascript)

setf は新しいオブジェクトを生成せずに既存の「場所」を書き換えます。
コピーが発生するかどうかは、setf の対象が何かによって変わります。
ハッシュテーブルのエントリや配列要素を setf する操作はコピーを起こしませんが、(setf x (append x (list item))) のような書き方は append がリスト全体をコピーするため注意が必要です。

3.2. 繰り返し（dotimes, dolist, loop）

dotimes は 0 から n-1 まで変数を動かす固定回数ループです。
dolist はリストの各要素を順に束縛します。
どちらも省略可能な最終引数がループの戻り値になります。
loop は多機能なイテレーションマクロで、collect・sum・count などの集約句を持ちます。

(dotimes (i 5 'done)
  (print i))
;; 0 1 2 3 4 を印字して 'done を返す

(dolist (x '(a b c) 'done)
  (print x))

(loop for i from 1 to 5 collect i)        ; => (1 2 3 4 5)
(loop for i from 0 below 5 by 2 collect i) ; => (0 2 4)
(loop for x in '(1 2 3) sum x)            ; => 6Code language: PHP (php)

loop の collect 句は内部で push + nreverse 相当の処理をするため O(n) で動きます。
collect の代わりに append を手書きで呼ぶと O(n²) になります。
ループ内でリストを組み立てるときは collect か push + nreverse を使うのが原則です。
このパターンは Section 1 で集中的に扱います。

3.3. 関数定義（defun, labels）

defun はトップレベルの名前付き関数を定義します。
labels は関数内でローカルな再帰関数を定義するフォームで、定義した関数自身を本体で呼べる点が flet との違いです。
相互再帰も labels 内に複数の定義を並べることで書けます。

(defun square (x)
  (* x x))

(defun factorial (n)
  (labels ((rec (k acc)
             (if (zerop k)
                 acc
                 (rec (1- k) (* k acc)))))
    (rec n 1)))

上の factorial はアキュムレータ acc を持つ末尾再帰の形です。
SBCL はこの形の末尾呼び出しを最適化してスタックフレームを再利用するため、n が大きくてもスタックオーバーフローが起きません。
素朴な再帰（各呼び出しが戻り値をさらに使う形）は深さに比例してスタックを消費します。
再帰の深さが入力サイズに比例するケースでの対処は Section 5・6 で扱います。

3.4. リストとconsセル（cons, car, cdr, push, pop）

Common Lisp のリストは cons セルの連鎖として実装されています。
各 cons セルは「値」と「次のセルへのポインタ」の2つを持ち、(list 1 2 3) は内部的に (cons 1 (cons 2 (cons 3 nil))) と同じです。
car は先頭要素を返し、cdr は残りのリストを返します。
push は (setf x (cons item x)) の短縮形で先頭への追加、pop は先頭を取り出して変数を cdr に更新します。

;;  [1 | ●]──[2 | ●]──[3 | nil]

(car '(1 2 3))   ; => 1
(cdr '(1 2 3))   ; => (2 3)
(cons 0 '(1 2))  ; => (0 1 2)

(let ((lst '()))
  (push 1 lst)
  (push 2 lst)
  lst)  ; => (2 1)  ← 後入れが先頭に来るCode language: PHP (php)

cons は新しいセルを1つ作って先頭につなぐだけなので O(1) です。
末尾への追加（append）はリスト全体をたどって O(n) かかります。
「末尾に順番に追加したい」場合は、push で先頭に積んで最後に nreverse するのが Common Lisp の定石です。
nreverse はポインタの向きを付け替えるだけで新しいセルを生成しないため、O(n) かつコピーなしで動きます。
このパターンは Section 1 で集中的に扱います。

4. この講座で繰り返すパターン

以降の48題では、次の考え方が形を変えて何度も登場します。

繰り返し登場するパターン コピーを削減する nreverse / nconc で破壊的操作 append → O(n²) に注意 データ構造を選ぶ member/nth → ハッシュテーブル O(mn) → O(n+m) へ 入力の保証を使う ソート済み → 隣接比較のみ 区間クエリ → 累積和で前処理 前処理とクエリ回数 前処理 O(n) → q回クエリ O(1) 利用パターン全体で設計 再帰の深さに注意 末尾再帰 or 反復に変換 深さ∝n → スタックオーバーフロー 型宣言は最後の手段 O改善 → declare / optimize (safety 0) は確認後に適用

割り当てのコストを意識する
concatenate・append・subseq はいずれもコピーを発生させます。
nreverse・nconc の破壊的操作や rotatef によるポインタ交換で、多くの場合コピーを削減できます。
このパターンは Section 1〜3 で繰り返し登場します。

データ構造の選択がボトルネックを決める
member・nth・append の繰り返しが見えたら、ハッシュテーブルかベクタへの置き換えを検討してください。
「n 要素のコレクションに対して m 回の操作」というパターンは、データ構造を変えるだけで O(mn) から O(n + m) に変わります。
このパターンは Section 2・3 で集中的に扱います。

「入力の保証」を見逃さない
ソート済みなら隣接比較だけで重複除去できます。
区間クエリが多ければ累積和で前処理します。
一般解より速くなる手段は、入力の構造的保証の中に隠れています。
このパターンは Section 3・4 で扱います。

前処理と問い合わせ回数のトレードオフ
1回のクエリを O(n) から O(1) にするより、「前処理 O(n) で q 回のクエリを O(1) にする」設計が有効なケースがあります。
アルゴリズム単体ではなく利用パターン全体で計算量を見ます。
このパターンは Section 4 で扱います。

再帰の深さとスタック
深さが入力サイズに比例する再帰は SBCL のデフォルトスタックでオーバーフローします。
末尾再帰への書き換えか、反復への変換で対処します。
このパターンは Section 5・6 と付録 A で扱います。

型宣言は定数倍の改善に使う
アルゴリズムを最適化した後、数値集中ループには declare による型宣言と optimize で定数倍の改善を得られます。
(safety 0) は境界チェックを省くため、正確性を確認してから適用してください。
オーダーを変える改善を先に行い、型宣言は最後の手段として使います。
このパターンは Section 6 で扱います。