【Section 3】リストの代わりにベクタを使う（Common Lispと計算効率）

Section 2 では「探索のデータ構造を変える」ことを確認しました。
Section 3 では「格納のデータ構造を変える」方向に目を向けます。

リストとベクタはどちらも線形なコレクションです。
しかし、速い操作と遅い操作がまったく異なります。

リスト（連結リスト）は、先頭への追加が O(1) ですがランダムアクセスが O(n)、
ベクタ（配列、連続メモリに要素が並ぶ構造）は、ランダムアクセスが O(1) ですが先頭への挿入が O(n) です。

さらに「ソートしておくとできること」にも目を向けます。
ソート済みという保証を活かすことで、一般解より一段速い O(n) や O(log n) の実装が書けます。
ここまでの3セクションで「基本的な性能改善の大半」をカバーします。

1. 問題14　リストの n 番目の要素への繰り返しアクセス

整数のリスト lst とインデックスのリスト indices を受け取り、各インデックスの要素を順に合計して返す関数を書いてください。

入力: lst = (10 20 30 40 50)
     indices = (0 2 4)
出力: 90   ← 10 + 30 + 50

入力: lst = (1 2 3 4 5 6 7 8 9 10)
     indices = (0 3 7 9)
出力: 22   ← 1 + 4 + 8 + 10

入力: lst = (100)
     indices = (0 0 0)
出力: 300

nth はリストを先頭から辿るため、インデックスが大きいほど O(index) かかります。
indices が m 個あれば合計 O(m × n) になります。
ベクタに変換してから aref を使えば O(1) でアクセスできます。

Section 2 では「探索を O(n) から O(1) にする」ためにハッシュテーブルを使いました。
問題14では、リストの nth がそもそも O(index) であることを確認し、ベクタへの切り替えを学びます。

1.1. 素直な実装 — アクセス1件あたり O(index)

reduceは、リストをアキュムレータで畳み込みます。
(reduce #’+ ‘(a b c) :key f) = (+ (f a) (f b) (f c))
key でリストの各要素を変換してから演算に使います。

(defun sum-elements-naive (lst indices)
  "nth は先頭から index ステップ辿るので O(index)。"
  (reduce #'+ indices :key (lambda (i) (nth i lst))))Code language: Lisp (lisp)

しかし、インデックスによるアクセスで、nth はリストを先頭から n ステップ辿ることになります。
すると、indices が m 個あり、各インデックスが平均 n/2 なら O(mn) になります。

1.2. 効く実装 — アクセス1件あたり O(1)

ランダムアクセスを繰り返すなら、あらかじめベクタに変換しておくことを考えます。

(defun sum-elements-fast (lst indices)
  "ベクタに変換してから aref でランダムアクセスする。"
  (let ((vec (coerce lst 'vector)))
    (reduce #'+ indices :key (lambda (i) (aref vec i)))))Code language: Lisp (lisp)

coerceを使うと、リストなどのシーケンスを別の型に変換できます。
ここでは、(coerce lst ‘vector) はリストをベクタに変換しています。
この変換コスト O(n) は一度だけです。

あとは、ベクタのアクセスする aref はポインタ演算で O(1)がm回です。
すると、合計：O(n + m)で、素直版の O(nm)より効率的になりました。

Common Lisp のリストは連結リストです。
nth で k 番目にアクセスするにはポインタを k 回辿ります。
ランダムアクセスが必要な場合は coerce や make-array でベクタに変換するのが基本です。
変換コスト O(n) が先行投資となり、m 回のアクセスがあれば O(n + m) で済みます。

2. 問題15　ベクタの最大値を求める（変換コストを払わない）

整数ベクタ vec を受け取り、最大値を返す関数を書いてください。

入力: vec = #(3 1 4 1 5 9 2 6 5 3)
出力: 9

入力: vec = #(100)
出力: 100

入力: vec = #(-5 -3 -7 -1)
出力: -1Code language: PHP (php)

(apply #'max (coerce vec 'list)) とも書けますが、coerce で O(n) のリスト生成が余計に発生し、apply は引数スタックを大量に消費します。
直接走査が O(n) かつ余計な割り当てなしで済みます。

問題14では「リスト → ベクタに変換してから操作」を学びました。
問題15は逆方向：「ベクタをリストに変換してはいけない」という教訓です。
オーダーが同じでもメモリと定数倍のコストが無駄になります。

2.1. 素直な実装 — O(n)だが余計なコスト

いったん、coerce でリストに変換してから、applyで最大値を求めました。

(defun max-vector-naive (vec)
  "coerce でリストに変換してから apply #'max を使う。"
  (apply #'max (coerce vec 'list)))Code language: Lisp (lisp)

しかし、この変換には O(n) がかかるだけでなく、applyで引数スタックを消費するため、大きなベクタでスタックオーバーフローの恐れがあります。

2.2. 効く実装 — O(n)、余計な割り当てなし

ベクタの場合は、applyではなく、ループで回した方が速いです。

(defun max-vector-fast (vec)
  "aref で直接走査する。変換コストなし。"
  (let ((best (aref vec 0)))
    (loop for i from 1 below (length vec) do
      (let ((x (aref vec i)))
        (when (> x best)
          (setf best x))))
    best))

(defun max-vector-reduce (vec)
  "reduce はベクタに対しても動作する"
  (reduce #'max vec))Code language: Lisp (lisp)

あるいは、applyではなく、reduce を使うこともできます。

データ構造を不要に変換しないことが大切です。
オーダーが同じでも変換コスト・メモリ割り当て・スタック消費が発生します。
「ベクタのまま操作する」か「リストのまま操作する」かは、入力のデータ構造を起点に考えてください。

3. 問題16　ベクタへの先頭追加を繰り返す

整数のリスト xs を受け取り、xs の逆順に並んだ整数ベクタを返す関数を書いてください。

入力: xs = (1 2 3 4 5)
出力: #(5 4 3 2 1)

入力: xs = (42)
出力: #(42)

入力: xs = ()
出力: #()Code language: PHP (php)

xs の先頭から取り出して逐次ベクタの先頭に挿入していく素直な実装は、ベクタのシフトが毎回発生して O(n²) になります。
リストで push して coerce する方法なら O(n) で済みます。

問題14・15はベクタの読み取りの話でした。
問題16は書き込みの話で、ベクタの先頭への追加がなぜ高コストかを確認します。

3.1. 素直な実装 — O(n²)

ベクタは先頭への追加が苦手です。

(defun build-vector-front-naive (xs)
  "ベクタの先頭に concatenate で追加し続ける。"
  (let ((vec #()))
    (dolist (x xs vec)
      (setf vec (concatenate 'vector (vector x) vec)))))Code language: Lisp (lisp)

後ろの全要素をずらす必要があるため、concatenate は毎回新しいベクタを作りますO(現在の長さ)。

3.2. 効く実装 — O(n)

いったんリストで組み立ててから、最後にベクタに変換した方がスムーズです。

(defun build-vector-front-fast (xs)
  "リストとして効率よく処理してから、最後に coerce でベクタに変換する。"
  (let ((result nil))
    (dolist (x xs)
      (push x result))
    (coerce (nreverse result) 'vector)))Code language: Lisp (lisp)

push + nreverse は O(n)で、coerce でベクタに変換するのも O(n)なので、合計 O(n) で先頭追加の意味を持つベクタが得られます。

前挿入はリスト向き、ランダムアクセスはベクタ向きです。
データ構造ごとに得意な操作と苦手な操作があります。
変換のコストを理解した上で、最終的なアクセスパターンに合わせた構造を選びます。

4. 問題17　ソート済みリストのマージ

昇順ソート済みの整数リスト a と b を受け取り、マージした昇順リストを返す関数を書いてください。

入力: a = (1 3 5 7)
     b = (2 4 6 8)
出力: (1 2 3 4 5 6 7 8)

入力: a = (1 2 3)
     b = ()
出力: (1 2 3)

入力: a = (1 1 3)
     b = (1 2 4)
出力: (1 1 1 2 3 4)

マージソートの内部処理や、2つのソート済みイベントログを時系列に統合する場面で使います。
(sort (append a b) #'<) と書くと O((m+n) log(m+n)) になりますが、すでに整列済みという情報を活かせば O(m+n) で済みます。

問題16まではデータ構造の形状の話でした。
問題17は「入力が持つ構造的な性質（整列済み）」を捨てないという観点です。

4.1. 素直な実装 — O((m+n) log(m+n))

リストを結合してからソートすると、全体の並べ替えに時間がかかってしまいます。
「すでにソート済み」という情報を捨てて再ソートしているからです。

(defun merge-sorted-naive (a b)
  "結合してからソートし直す。ソートのコストが余計にかかる。"
  (sort (append a b) #'<))Code language: Lisp (lisp)

4.2. 効く実装 — O(m + n)

リスト a, bの両方から car で先頭を取り出し、比較して小さいほうをリストから pop で取り出し、 result に pushしていきます。

(defun merge-sorted-fast (a b)
  "両リストの先頭を比較しながら結果を組み立てる。"
  (let ((result '()))
    (loop
      (cond
        ((null a) (return (nreverse (nconc (reverse b) result))))
        ((null b) (return (nreverse (nconc (reverse a) result))))
        ((<= (car a) (car b))
         (push (pop a) result))
        (t
         (push (pop b) result))))))Code language: Lisp (lisp)

a か b のどちらかが空になったら、残りはnconc で result の前に追加します。
最後は、向きを逆順にすれば完了です。

ベクタ版：

(defun merge-sorted-vector (a b)
  "ベクタで実装すると一度だけ make-array でメモリを確保できる。"
  (let* ((la (length a)) (lb (length b))
         (out (make-array (+ la lb)))
         (ia 0) (ib 0) (io 0))
    (loop while (and (< ia la) (< ib lb)) do
      (if (<= (aref a ia) (aref b ib))
          (progn (setf (aref out io) (aref a ia)) (incf ia))
          (progn (setf (aref out io) (aref b ib)) (incf ib)))
      (incf io))
    (loop while (< ia la) do (setf (aref out io) (aref a ia)) (incf ia) (incf io))
    (loop while (< ib lb) do (setf (aref out io) (aref b ib)) (incf ib) (incf io))
    out))Code language: Lisp (lisp)

「すでに整列済み」という情報を捨てて再ソートするのは情報の無駄遣いです。
マージは O(m+n) で終わるのに、sort を呼ぶと O((m+n) log(m+n)) になります。
問題13（ソート済み重複除去）と同じく「入力の保証を活かす」設計です。

5. 問題18　バブルソートとマージソート

整数ベクタ vec を受け取り、昇順にソートしたベクタを返す関数を書いてください。

入力: vec = #(5 3 8 1 9 2 7 4 6)
出力: #(1 2 3 4 5 6 7 8 9)

入力: vec = #(1)
出力: #(1)

入力: vec = #(3 3 1 2 2)
出力: #(1 2 2 3 3)Code language: PHP (php)

バブルソートは O(n²)、マージソートは O(n log n) です。
SBCL の組み込み sort も O(n log n) で動作しますが、sort は破壊的であるため元のベクタを保持したい場合は (sort (copy-seq vec) #'<) とします。

問題17でマージの O(m+n) を確認したので、マージソートの核心（分割してマージする）が理解しやすくなっています。
問題18は「ソートの計算量」を正面から扱います。

5.1. バブルソート — O(n²)

隣接する要素を比較して交換するのは、直感的ですが非効率です。

(defun bubble-sort (vec)
  "隣接する要素を比較して交換する。教育目的以外では使わない。"
  (let ((n (length vec)))
    (loop for i from (1- n) downto 1 do
      (loop for j from 0 below i do
        (when (> (aref vec j) (aref vec (1+ j)))
          (rotatef (aref vec j) (aref vec (1+ j))))))
    vec))Code language: Lisp (lisp)

(rotatef a b) は a と b を交換しています。

5.2. マージソート — O(n log n)

(subseq seq start end)は、シーケンスの部分列を返します。

(defun merge-sort (vec)
  "分割統治によるマージソート。"
  (let ((n (length vec)))
    (when (<= n 1) (return-from merge-sort vec))
    (let* ((mid   (floor n 2))
           (left  (merge-sort (subseq vec 0 mid)))
           (right (merge-sort (subseq vec mid))))
      (let ((result (make-array n))
            (i 0) (j 0) (k 0))
        (loop while (and (< i (length left)) (< j (length right))) do
          (if (<= (aref left i) (aref right j))
              (progn (setf (aref result k) (aref left i))  (incf i))
              (progn (setf (aref result k) (aref right j)) (incf j)))
          (incf k))
        (loop while (< i (length left))  do (setf (aref result k) (aref left i))  (incf i) (incf k))
        (loop while (< j (length right)) do (setf (aref result k) (aref right j)) (incf j) (incf k))
        result))))
Code language: Lisp (lisp)

ちなみに、実用では組み込みの sort を使うのが便利です。
SBCL はハイブリッドソートで O(n log n)。
ただし、sort は破壊的なので、元を保持したいときは (sort (copy-seq vec) #'<)。

破壊的ソートでは、sort の戻り値を変数で再束縛するのが安全です。

(let ((v (vector 3 1 2)))
  (setf v (sort v #'<))    ; v を sort の結果に再束縛する
  v)                        ; => #(1 2 3)Code language: Lisp (lisp)

等値要素の相対順序を保証したいときは、(stable-sort vec #'<) を使います。

SBCL の sort は O(n log n) です。
stable-sort は等値要素の相対順序を保証します。
自前でソートを実装する機会はほぼありませんが、マージの仕組みを理解するとマージソートの「分割→再帰→マージ」という構造が次の Part（分割統治）への橋渡しになります。

6. 問題19　二分探索

昇順ソート済みの整数ベクタ vec と探す値 target を受け取り、target が存在すればそのインデックスを、なければ nil を返す関数を書いてください。

入力: vec = #(1 3 5 7 9 11 13)
     target = 7
出力: 3

入力: vec = #(1 3 5 7 9 11 13)
     target = 6
出力: nil

入力: vec = #(42)
     target = 42
出力: 0Code language: PHP (php)

線形探索 position は O(n) ですが、ソート済みであることを活かした二分探索は O(log n) で済みます。
n = 10^6 なら線形で最大 10^6 回の比較が、二分探索なら最大 20 回で終わるからです。

問題18でソートを学びました。
「ソートしておくと探索が速くなる」というリターンがここで登場します。
ハッシュテーブルが O(1) 探索を提供するのに対し、二分探索は O(log n) ですが「順序関係」を活用できる点で補完的です。

6.1. 線形探索 — O(n)

positionは、シーケンスの中で条件を満たす最初のインデックスを返し、見つからなければ nil を返します。

(defun linear-search (vec target)
  (position target vec :test #'=))Code language: Lisp (lisp)

6.2. 二分探索 — O(log n)

ソート済みのベクタなら、真ん中のインデックス mid の計算が速いです。

(defun binary-search (vec target)
  "ソート済みベクタから target を二分探索する。"
  (let ((low  0)
        (high (1- (length vec))))
    (loop while (<= low high) do
      (let ((mid (ash (+ low high) -1)))
        (cond
          ((= (aref vec mid) target)
           (return-from binary-search mid))
          ((< (aref vec mid) target)
           (setf low (1+ mid)))
          (t
           (setf high (1- mid))))))
    nil))Code language: Lisp (lisp)

ただし、中間インデックスの計算では注意が必要です。
たとえば、Common Lisp の (/ 5 2) は有理数 5/2 を返すので、整数除算には floor, ceiling, truncate, round のいずれかを使います。
今回は、乗除算 floor(x/2) 切り捨て（負方向）、より高速な右に1ビットシフト(ash x -1) を使いました。

Common Lisp の / は有理数を返すため、整数除算には floor や ash を使います。
この点は C/Java と大きく異なります。
二分探索は問題33（LIS）でも登場し、「ソート済み配列への二分探索」が高速化の核になります。

1. 問題14 リストの n 番目の要素への繰り返しアクセス