【Section 1】
見えにくいリストの中間コピーを減らす
（Common Lispと計算効率）

Common Lisp のリストは「連結リスト」です。

各 cons セルがポインタで次のセルを指す構造なので、
先頭への追加は O(1) ですが、末尾への追加は O(n) かかります。
この非対称性を理解すると、多くのパフォーマンス問題の原因と解決策が同時に見えてきます。

このセクションでは、「末尾への繰り返し追加」が二乗コストになる理由を確認し、push＋nreverse という Lisp 特有のイディオムを身につけます。
文字列連結まで同じ構造の問題で、「中間コピーを避けて最後に1回だけコピーする」という発想によって解きます。

1. 問題1　リストの末尾への追加を繰り返す

整数 n を受け取り、0 から n-1 までの整数を順番に並べたリストを返す関数を書いてください。

入力: n = 5
出力: (0 1 2 3 4)

入力: n = 1
出力: (0)

入力: n = 0
出力: ()Code language: HTTP (http)

競技プログラミングでは「Q 回のクエリに対する答えを順に集めて返す」というパターンが、よく現れます。
そういうときに、末尾への append を使い続けると O(n²)になり 、Q が大きい数字になったときにボトルネック になっていることがよくあります。

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

(defun build-list-naive (n)
  "要素 0 から n-1 を末尾に追加しながらリストを作る。"
  (let ((result '()))
    (dotimes (i n result)
      (setf result (append result (list i))))))Code language: Lisp (lisp)

appendは、2つのリストを連結して「新しいリスト」を返します。
このとき、第1引数の全セルをコピーしてから第2引数を繋ぐため、result の長さが 0, 1, 2, … と増えるにつれコピーコストも増えていきます。

append の内部動作を図で示します。

; result = (0 1 2)、i = 3 のとき：
(append result (list 3))

コピー:  [0]──[1]──[2]──[nil]
                           ↑
追加:                    [3]──[nil]Code language: PHP (php)

合計：0 + 1 + 2 + … + (n-1) = n(n-1)/2 = O(n²)。

1.2. 効く実装 — O(n)

(defun build-list-fast (n)
  "先頭に push して最後に nreverse する。合計 O(n)。"
  (let ((result '()))
    (dotimes (i n)
      (push i result))
    (nreverse result)))Code language: Lisp (lisp)

push は (setf result (cons i result)) と等価です。
cons では、新しい cons セルを1つ作るだけなので O(1)。

その代わり、先頭に追加するため結果は逆順になってしまうので、最後に戻す必要があります。
それが、nreverse です。

nreverse の動作：

nreverse 前: ← push で逆順に積まれた状態
[3]──[2]──[1]──[0]──nil   

 ← ポインタを付け替えただけ
nreverse 後: 
[0]──[1]──[2]──[3]──nil  Code language: CSS (css)

loop の collect 句も、内部では push + nreverse に相当する動作になっています。

(defun build-list-loop (n)
  (loop for i from 0 below n 
        collect i))Code language: Lisp (lisp)

push は O(1)、nreverse は O(n) で一度だけです。
合計 O(n) に対し、append の繰り返しは O(n²) になります。

2. 問題2　加工しながらリストを構築する

整数のリスト xs を受け取り、各要素を二乗した新しいリストを返す関数を書いてください。

入力: xs = (1 2 3 4 5)
出力: (1 4 9 16 25)

入力: xs = (-3 0 4)
出力: (9 0 16)

入力: xs = ()
出力: ()Code language: HTTP (http)

「各要素を変換して同じ順序で返す」操作はデータ処理の基本です。
長いリストに append で逐次追加すると O(n²) になります。

問題1は「逐次追加」でしたが、問題2は「変換しながらの構築」です。
append を使いたくなる場面がより強い形で現れます。

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

(defun square-list-naive (xs)
  "各要素を二乗した新しいリストを作る。"
  (let ((result nil))
    (dolist (x xs result)
      (setf result (append result (list (* x x)))))))Code language: Lisp (lisp)

dolistは、リストの各要素を順に束縛し、最後の引数result がループ終了後の戻り値になります。
append で毎回コピーが発生し、result が長くなるほど遅くなっていきます。

2.2. 効く実装 — O(n)

(defun square-list-fast (xs)
  "push で前に積み、最後に nreverse する。"
  (let ((result nil))
    (dolist (x xs (nreverse result))
      (push (* x x) result))))Code language: Lisp (lisp)

push で O(1) の先頭追加にして、最後にまとめて逆順にする方がよいです。

mapcar を使えばさらに簡潔に書けます。

(defun square-list-mapcar (xs)
  (mapcar (lambda (x) (* x x)) xs))Code language: Lisp (lisp)

mapcarは、リストの各要素に関数を適用して新しいリストを返します。
たとえば、 (mapcar f ‘(a b c)) = (list (f a) (f b) (f c)) と同じです。
この内部は、 push + nreverse 相当の実装をしているので、自然と O(n)になります。

3. 問題3　ネストリストの平坦化（flatten）

任意の深さでネストしたリスト lst を受け取り、すべての原子要素を順番に並べた1次元リストを返す関数を書いてください。

入力: lst = (1 (2 3) (4 (5 6)))
出力: (1 2 3 4 5 6)

入力: lst = ((1 2) (3 4) (5 6))
出力: (1 2 3 4 5 6)

入力: lst = (1 (2 (3 (4))))
出力: (1 2 3 4)

入力: lst = ()
出力: ()Code language: HTTP (http)

ディレクトリツリーや数式の構文木など、ネスト構造を一覧化する場面で使います。

3.1. 素直な実装 — O(n²) になりうる

再帰の中で append を使うと、中間リストが大量に生成されます。

(defun flatten-naive (lst)
  "append を使った再帰版。中間リストを大量に生成する。"
  (cond
    ((null lst) '())
    ((atom lst) (list lst))
    (t (append (flatten-naive (car lst))
               (flatten-naive (cdr lst))))))Code language: Lisp (lisp)

atomは、cons セルでないオブジェクト（数値・シンボル・文字列など）なら t を返す述語関数です。
また、nullは、nil なら t を返す述語関数です。

append を使って (flatten-naive (car lst)) の結果リストをコピーしているのですが、再帰が深くなるほど同じ要素が何度もコピーの対象になってしまいます。

コピーの連鎖を図で示します。

(flatten-naive '((1 2) (3 4)))

→ (append (flatten-naive '(1 2)) (flatten-naive '(3 4)))
→ (append '(1 2) '(3 4))Code language: Lisp (lisp)

3.2. 効く実装 — O(n)

コピーを減らすには、「アキュムレータパターン」を使います。

(defun flatten-fast (lst)
  "アキュムレータパターンでコピーを最小化する。"
  (labels ((rec (node acc)
             (cond
               ((null node) acc)
               ((atom node) (cons node acc)) 
               (t (rec (car node)
                       (rec (cdr node) acc))))))
    (rec lst '())))Code language: Lisp (lisp)

発想としては、append の代わりに「後ろを先に計算してから前を cons する」ことです。
そのため、labels でローカル再帰関数 rec を定義し、引数 acc（増幅変数：accumulator）として「これから後ろに来る要素のリスト」を積み上げていきます。
cdr 側を先に処理（acc を延長）してから car 側を処理し、

動作のトレース：

(flatten-fast '((1 2) 3))

rec '((1 2) 3) '()
  = rec '(1 2) (rec '(3) '())
  = rec '(1 2) (rec 3 (rec '() '()))
  = rec '(1 2) (rec 3 '())
  = rec '(1 2) (cons 3 '())
  = rec '(1 2) '(3)
  = rec 1 (rec '(2) '(3))
  = rec 1 (cons 2 '(3))
  = rec 1 '(2 3)
  = cons 1 '(2 3)
  = '(1 2 3)Code language: Lisp (lisp)

4. 問題4　隣接する重複を除く

整数のリスト lst を受け取り、連続して同じ値が続く場合はひとつだけ残した新しいリストを返す関数を書いてください。

入力: lst = (1 1 2 3 3 3 4)
出力: (1 2 3 4)

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

入力: lst = (5 5 5 5)
出力: (5)

入力: lst = ()
出力: ()Code language: HTTP (http)

ランレングス符号化の前処理や、センサーデータの変化点抽出などで使います。

問題3でアキュムレータの発想を確認しました。
問題4は「直前の値を引き継ぐ」という、スライディングウィンドウの最も単純な形です。
last を使う素直な実装がなぜ遅くなるかを確認します。

4.1. 素直な実装 — O(n²) になりうる

last を毎回呼ぶ実装は O(n²) になります。

(defun remove-adjacent-dups-naive (lst)
  "前の要素を毎回 last で取得している悪例。"
  (when lst
    (loop for x in lst
          when (or (null result)
                   (not (equal x (car (last result)))))
          collect x into result
          finally (return result))))Code language: Lisp (lisp)

lastは、リストの最後の cons セルを返しますが、これも append 同様 result が長くなるほどコストが増えます。

4.2. 効く実装 — O(n)

「直前の値（prev）」を変数で引き継ぐだけで last の繰り返し呼び出しが消えます。

(defun remove-adjacent-dups-fast (lst)
  "直前の要素を変数に保持することで last の呼び出しを排除する。"
  (when lst
    (let ((prev   (car lst))
          (result (list (car lst))))
      (dolist (x (cdr lst) (nreverse result))
        (unless (equal x prev)
          (push x result)
          (setf prev x)))))Code language: Lisp (lisp)

「prev」が前提になるので、先頭要素は無条件で追加します。
次のイテレーションへ引き継ぐために、prev に値をセットします。

5. 問題5　文字列の連結を繰り返す

文字列のリスト strings を受け取り、それらをすべて連結した1つの文字列を返す関数を書いてください。

入力: strings = ("Hello" ", " "World" "!")
出力: "Hello, World!"

入力: strings = ("a" "b" "c" "d" "e")
出力: "abcde"

入力: strings = ("only")
出力: "only"Code language: JavaScript (javascript)

Q 個の回答を改行で繋げて出力する場面や、CSV の各フィールドを結合する処理などで使います。
concatenate も繰り返すと文字列が長くなるにつれ O(n²) になります。

問題1〜4はリストの話でしたが、文字列でもまったく同じ問題が起きます。
足すたびに全内容をコピーする構造が、文字列連結にも潜んでいます。

5.1. 素直な実装 — O(total²/n) ≈ O(n²)

reduceは、アキュムレータの初期値を initial-value で指定し、リストを畳み込みます。
ただ、concatenate は新しい文字列を毎回作るので、すでに作った部分も都度コピーしてしまいます。

(defun join-strings-naive (strings)
  "concatenate を繰り返す。毎回新しい文字列を割り当てる。"
  (reduce (lambda (acc s) (concatenate 'string acc s))
          strings
          :initial-value ""))Code language: Lisp (lisp)

5.2. 効く実装 — O(total chars)

with-output-to-stringは、本体で out ストリームに書き込まれた内容をまとめて文字列として返すマクロです。

(defun join-strings-fast (strings)
  "with-output-to-string でバッファに書き込む。"
  (with-output-to-string (out)
    (dolist (s strings)
      ;; write-string：文字列をストリームに書き込む。
      (write-string s out))))Code language: Lisp (lisp)

この、バッファは自動拡張する動的配列で、追記は O(1)で済みます。
そのため、最終的なコピーは一度だけです。

全体の長さを先に計算して、一括割り当てする方法もあります。

(defun join-strings-preallocate (strings)
  "先に長さを求めて一度だけメモリを確保する。"
  (let* ((total  (reduce #'+ strings :key #'length))
         (result (make-string total))
         (pos    0))
    (dolist (s strings result)
      (replace result s :start1 pos)
      (incf pos (length s)))))Code language: Lisp (lisp)

replaceは、コピー先の配列をコピー元で上書きします。
:start1 でコピー先の開始インデックスを指定します。