Section 1 では「どこに追加するか」が性能を決めることを確認しました。
Section 2 では「どこを探索するか」という別の軸に焦点を当てます。
member・assoc・nth は、いずれも先頭から辿る線形探索で O(n) です。
これらをループ内で繰り返すと O(n²) になります。
一方、ハッシュテーブルの gethash は O(1) が期待値。
なので、探索が何度も繰り返される状況ではデータ構造を切り替えるだけでオーダーが変わります。
最も遭遇頻度が高い最適化のひとつです。
問題 6〜13 はすべてこの変換のバリエーションで、「存在確認」「頻度集計」「重複除去」「辞書引き」「集合演算」「フィルタリング」という日常的な操作をまとめて整理しましょう。
1. 問題6 要素の存在確認をリストで行う
文字列のリスト collection と問い合わせのリスト queries を受け取り、各クエリが collection に含まれるかを t または nil のリストで返す関数を書いてください。
入力: collection = ("apple" "banana" "cherry")
queries = ("banana" "grape" "apple")
出力: (t nil t)
入力: collection = ("a" "b" "c")
queries = ("d" "e")
出力: (nil nil)
入力: collection = ()
queries = ("x")
出力: (nil)Code language: JavaScript (javascript)「ユーザーIDが登録済みかを一括チェックする」「NGワードリストに該当するかを判定する」など、集合への繰り返し問い合わせで現れます。
1.1. 素直な実装 — クエリ1件あたり O(n)
(defun batch-member-naive (queries collection)
"queries の各要素が collection にあるかを調べる。"
(mapcar (lambda (q) (member q collection :test #'equal))
queries))Code language: Lisp (lisp)mapcarは、リストの各要素に関数を適用して新しいリストを返します。
:test キーワード引数で比較関数を指定し、#’equal で文字列・リストの構造的同一性を判定しています。
この中の、member がループの中に入ったときに要注意。
リストを先頭から線形探索するので、O(|collection|)。
つまり、リストが大きいほど遅くなってしまうのです。
1.2. 効く実装 — クエリ1件あたり O(1)
(defun batch-member-fast (queries collection)
"ハッシュテーブルに変換してから問い合わせる。"
(let ((ht (make-hash-table :test #'equal
:size (length collection))))
(dolist (item collection)
(setf (gethash item ht) t))
(mapcar (lambda (q) (gethash q ht))
queries)))Code language: Lisp (lisp)member の O(n) を gethash の O(1) に変える典型パターンです。
構築には O(n) と、少し時間がかかります。
しかし、問い合わせが複数回あればすぐに元を取れます。
make-hash-tableは、ハッシュテーブルを作ります。
keyに文字列を扱う場合は :test #'equal を忘れずに指定してください。
同一性の判定には、:test で eq / eql / equal / equalp などを指定できます。
もし、eql だと文字列の中身が正しく比較されないので注意が必要です。
ちなみに、:size はバケット数のヒント。
要素数がわからないと、テーブルの作り直しが発生することがあります。
正確でなくてよいが、要素数に近い値を渡すと最初のリハッシュを避けられるので、少し効率的です。
2. 問題7 要素の出現頻度を数える
整数のリスト xs を受け取り、各値の出現回数をハッシュテーブルで返す関数を書いてください。
入力: xs = (1 2 1 3 2 1)
出力: {1 → 3, 2 → 2, 3 → 1}
入力: xs = (5 5 5 5)
出力: {5 → 4}
入力: xs = (1 2 3)
出力: {1 → 1, 2 → 1, 3 → 1}Code language: HTTP (http)「各文字の出現回数を数えてから判定する」問題は頻出です。
たとえば「文字列がアナグラムかどうか判定する」問題では、両文字列の頻度テーブルを比較します。
2.1. 素直な実装 — O(n²)
問題6では「存在するかどうか」だけを調べました。
問題7は「何回出てきたか」を数えるため、assoc を使う実装が自然に思い浮かびます。
(defun frequencies-naive (xs)
"association list（alist）で頻度を管理する。"
(let ((result nil))
(dolist (x xs result)
(let ((cell (assoc x result :test #'eql)))
(if cell
(incf (cdr cell))
(push (cons x 1) result))))))Code language: Lisp (lisp)alistは、(key . value) のリストです。
assocは、allistをキーで線形探索し、見つかれば (key . value) のコンスペアを返します。
cdr は「コンスペアの右側」なので、ここでは現在のカウント値。
incfで指定した場所を 1 増やしています。
(setf (cdr cell) (1+ (cdr cell))) と同じ。
初めて出てきた値は、カウント 1 で alist に追加する。
しかし assoc も線形探索なので、種類数が増えるほど O(k)。
合計 O(n × k)で、最悪全要素が異なる値なら O(n²)。
問題6と同じ問題が起きます。
2.2. 効く実装 — O(n) 期待値
(defun frequencies-fast (xs)
"ハッシュテーブルで頻度を管理する。"
(let ((table (make-hash-table :test #'eql)))
(dolist (x xs table)
(incf (gethash x table 0)))))Code language: Lisp (lisp)alistではなく、hash-tableにするだけで、効率的に動作します。
gethash の第3引数はデフォルト値で、キーが存在しないとき 0 を返します。
そこに incf することで、「初回は 0 → 1、以降は前の値 + 1」になります。
もし、デフォルト値がなければ、初回かどうかを別途確認する必要があります。
(multiple-value-bind (val found-p) (gethash x table)
(if found-p
(setf (gethash x table) (1+ val))
(setf (gethash x table) 1)))Code language: Lisp (lisp)しかし、デフォルト値を設定すれば1行で書けます。
(incf (gethash x table 0))Code language: Lisp (lisp)gethash の戻り値は place として扱われるため、incf で直接書き換えられます。
assoc はリストを毎回頭から探すので O(k) かかります。gethash は O(1) 期待値です。
集計は探索と更新の繰り返しなので、探索のデータ構造がそのままボトルネックになります。
ハッシュテーブルの全体から結果を取り出すには、maphash を使います。
全 (key, value) ペアに関数を適用し、戻り値は nil（副作用専用）です。
(let ((table (frequencies-fast '(a b a c b a))))
(maphash (lambda (k v) (format t "~a: ~a~%" k v)) table))
;; => a: 3
;; b: 2
;; c: 1Code language: Lisp (lisp)3. 問題8 重複を除いたリストを作る
整数のリスト xs を受け取り、初出順を保ちながら重複を除いたリストを返す関数を書いてください。
入力: xs = (3 1 4 1 5 9 2 6 5 3)
出力: (3 1 4 5 9 2 6)
入力: xs = (1 2 3)
出力: (1 2 3)
入力: xs = (1 1 1)
出力: (1)Code language: HTTP (http)「訪問済みノードのリストを管理する」「ログから一意なユーザーIDを抽出する」などで使います。member で重複チェックするたびに O(n) かかるため、n が大きいと O(n²) になります。
問題6では「あるかどうか」、問題7では「何回あるか」を調べました。
問題8は「まだ出ていないか」を判定します。
「見たかどうか」を管理するデータ構造が性能の鍵になります。
3.1. 素直な実装 — O(n²)
すでみた要素 seen をリストで管理すると、長くなるほど member のコストが増える。
(defun unique-naive (xs)
"すでに見た要素を member で確認しながら追加する。"
(let ((seen '()))
(dolist (item xs (nreverse seen))
(unless (member item seen :test #'equal)
(push item seen)))))Code language: Lisp (lisp)unlessは、 (when (not cond) …) と同じで、条件が false のときだけ本体を実行します。
3.2. 効く実装 — O(n) 期待値
(defun unique-fast (xs)
"ハッシュテーブルで既出確認を O(1) にする。"
(let ((ht (make-hash-table :test #'equal))
(result '()))
(dolist (item xs (nreverse result))
(unless (gethash item ht)
(setf (gethash item ht) t)
(push item result)))))Code language: Lisp (lisp)「すでに見たか」を管理するデータ構造がリストかハッシュテーブルかで全体の計算量が変わります。
問題6（存在確認）・問題7（頻度集計）・問題8（重複除去）は、同じ「探索をハッシュテーブルに置き換える」という解法を持つ三兄弟です。
4. 問題9 alist vs ハッシュテーブル
(キー 値) のペアリスト pairs と問い合わせキーのリスト queries を受け取り、各キーに対応する値を順に返す関数を書いてください。
見つからないキーには nil を返します。
入力: pairs = (("alice" 90) ("bob" 75) ("carol" 88))
queries = ("bob" "dave" "alice")
出力: (75 nil 90)
入力: pairs = ((1 "one") (2 "two") (3 "three"))
queries = (3 1 4)
出力: ("three" "one" nil)Code language: JavaScript (javascript)「ユーザー名からスコアを引く」「IDから名前を変換する」など、辞書引きの繰り返しに使います。assoc による線形探索はコレクションが大きくなると O(n) になります。
問題7で assoc の問題点を確認しました。
ここでは「assoc をいつ使い、いつハッシュテーブルを使うか」という判断基準を整理します。
4.1. alist（association list）— 検索 O(n)
alist は (key . value) というコンスペアのリストで、
例えば、((name . “Alice”) (age . 30) (city . “Tokyo”))など。
(defun build-and-lookup-alist (pairs queries)
(let ((alist (mapcar (lambda (p) (cons (car p) (cdr p))) pairs)))
(mapcar (lambda (q) (cdr (assoc q alist :test #'equal)))
queries)))Code language: Lisp (lisp)assocは、alist の中からキーが一致するペアを先頭から線形探索し、見つかれば (key . value) のペアを返すので、cdr で値だけ取り出します。
4.2. ハッシュテーブル — 検索 O(1)
一方、gethash は (values value found-p) の2値を返します。
(defun build-and-lookup-ht (pairs queries)
(let ((ht (make-hash-table :test #'equal :size (length pairs))))
(dolist (p pairs)
(setf (gethash (car p) ht) (cdr p)))
(mapcar (lambda (q) (gethash q ht))
queries)))
;; multiple-value-bind で2値を受け取る例。
(multiple-value-bind (value found-p)
(gethash :missing-key ht)
(if found-p
(format t "Found: ~a" value)
(format t "Not found")))Code language: Lisp (lisp)found-p は、値が nil の場合と区別するため、 nil のとき「キーが存在しない」と分かります。
通常は、ハッシュテーブルを使います。
alist を選ぶ基準は、要素数が少ない（目安 10 以下）こと。
あと、「最後に追加したものを優先して返す」セマンティクス（shadowing）が必要なときです。
同じキーで push すると、assoc は最初に見つけた（最後に追加した）ものを返すからです。
;; alist の先頭追加で「shadowing」を実現する例：
(defun extend-env (env key val)
"既存の環境を壊さずに key=val を追加した新しい環境を返す。"
(cons (cons key val) env))Code language: Lisp (lisp)あとは、「alist を丸ごとコピーして一部を変えた版を作る」関数的スタイルのときにも使います。
規模が大きくなりうる場合は、最初からハッシュテーブルを選ぶほうが安全です。
5. 問題10 2つのリストの共通要素
整数のリスト a と b を受け取り、両方に含まれる要素を a の出現順で返す関数を書いてください。
入力: a = (1 2 3 4 5)
b = (2 4 6 8)
出力: (2 4)
入力: a = (1 2 3)
b = (4 5 6)
出力: ()
入力: a = (3 1 4 1 5)
b = (1 3)
出力: (3 1 1)「2チームの共通メンバーを抽出する」「2つのログファイルに共通するエラーコードを見つける」などで使います。a の各要素について b を線形探索すると O(|a| × |b|) になります。
問題6〜9で「1つのコレクションに対する繰り返し検索」を確認しました。
問題10は2つのコレクション間の操作です。
「片方を索引化してから照合する」パターンに帰着します。
5.1. 素直な実装 — O(|A| × |B|)
member は b を先頭から線形探索するので、O(|b|)。
A の全要素に対して呼ぶので O(|A| × |B|)。
(defun intersection-naive (a b)
"A の各要素について B を線形探索する。"
(let ((result nil))
(dolist (x a (nreverse result))
(when (member x b :test #'eql)
(push x result)))))Code language: Lisp (lisp)5.2. 効く実装 — O(|A| + |B|) 期待値
(defun intersection-fast (a b)
"B をハッシュテーブルに変換してから A をフィルタする。"
(let ((table (make-hash-table :test #'eql))
(result nil))
(dolist (x b)
(setf (gethash x table) t))
;; Step 2: A の各要素を O(1) で照合。O(|A|)。
(dolist (x a (nreverse result))
(when (gethash x table)
(push x result)))))Code language: Lisp (lisp)共通要素を重複なしで返したい場合：
(defun intersection-unique (a b)
"共通要素を重複なしで返す（A に同じ値が複数あっても1回だけ）。"
(let ((b-table (make-hash-table :test #'eql))
(seen (make-hash-table :test #'eql))
(result nil))
(dolist (x b) (setf (gethash x b-table) t))
(dolist (x a (nreverse result))
(when (and (gethash x b-table)
(not (gethash x seen)))
(setf (gethash x seen) t)
(push x result)))))Code language: Lisp (lisp)「片方を索引化してから照合する」パターンは、積・差・包含判定など2コレクション間のすべての操作に適用できます。
O(nm) から O(n + m) に変える定番手法です。
6. 問題11 最初に2回目が現れる要素を見つける
整数のリスト xs を受け取り、2回以上出現した要素のうち、2回目の出現が最も左にあるものを返す関数を書いてください。
重複がなければ nil を返します。
入力: xs = (2 3 1 0 2 5 3)
出力: 2 ← インデックス 4 で 2 回目の出現
入力: xs = (1 2 3 4 5)
出力: nil
入力: xs = (1 2 3 1 2 3)
出力: 1
入力: xs = (5)
出力: nilCode language: HTTP (http)「ネットワークパケットの重複IDを検出する」「トランザクションIDの二重送信を検出する」などの応用があります。
問題10では2つのコレクション間の操作でした。
問題11は1つのコレクション内での重複検出です。
「右側に同じものがあるか」という問いを「左側で見たか」に言い換えることで、視点の反転が起きます。
6.1. 素直な実装 — O(n²)
まず、Step 1で B を索引化します。
これが O(|B|)。
(defun first-duplicate-naive (xs)
"各要素について、右側に同じものがあるかを探す。"
(loop for rest on xs
for x = (car rest)
when (member x (cdr rest) :test #'eql)
do (return x)))Code language: Lisp (lisp)loop for rest on xsで、on はリストの各「cdr 位置」を順に束縛します。
つまり、rest = (1 2 3)、(2 3)、(3) と変化します。
(cdr rest) = x の右側のリスト。member で線形探索。O(|残り|)。
合計 O(n + (n-1) + … + 1) = O(n²)。
6.2. 効く実装 — O(n) 期待値
(defun first-duplicate-fast (xs)
"「左側で見たか」をハッシュテーブルで管理する。"
(let ((seen (make-hash-table :test #'eql)))
(dolist (x xs nil)
(if (gethash x seen)
(return-from first-duplicate-fast x)
(setf (gethash x seen) t)))))Code language: Lisp (lisp)ハッシュテーブルを使うと、すでに見た → 2回目の出現 なら、即座に返します。
また、return-fromは、名前付き関数でブロックから抜けます。
(return) はループから抜けるが (return-from f v) は関数 f から抜けます。
見つからなければ nil を返す
「右側に同じものがあるか」は「左側で見たか」に言い換えられます。
この視点の反転によって、毎回の線形探索が O(1) のハッシュ引きに変わります。
問題28（2Sum）でも同じ発想が使われます。
7. 問題12 許可リストによるフィルタリング
整数のリスト xs と許可リスト allowed を受け取り、allowed に含まれる要素だけを xs の順序を保って返す関数を書いてください。
入力: xs = (1 2 3 4 5 6 7 8)
allowed = (2 4 6 8)
出力: (2 4 6 8)
入力: xs = ("apple" "banana" "cherry" "date")
allowed = ("banana" "date" "elderberry")
出力: ("banana" "date")
入力: xs = (1 2 3)
allowed = (4 5 6)
出力: ()Code language: JavaScript (javascript)「有効なコマンドリストに含まれる操作だけを処理する」「ホワイトリスト方式のフィルタリング」などで使います。xs の各要素について allowed を線形探索すると O(|xs| × |allowed|) になります。
問題11は単一コレクションの重複検出でした。
問題12は別のコレクションとの照合による選別で、問題10（共通要素）の片側バージョンです。
繰り返しの member 呼び出しが典型的なボトルネックになります。
7.1. 素直な実装 — O(|xs| × |allowed|)
(defun filter-allowed-naive (xs allowed)
"各要素ごとに allowed を線形探索する。"
(let ((result nil))
(dolist (x xs (nreverse result))
(when (member x allowed :test #'eql)
(push x result)))))Code language: Lisp (lisp)7.2. 効く実装 — O(|xs| + |allowed|) 期待値
Common Lisp 標準に「集合型」はないため、ハッシュテーブルを集合として使うのが定番です。
(defun filter-allowed-fast (xs allowed)
"allowed をハッシュテーブルに変換して O(1) 照合にする。"
(let ((table (make-hash-table :test #'eql))
(result nil))
(dolist (a allowed)
(setf (gethash a table) t))
(dolist (x xs (nreverse result))
(when (gethash x table)
(push x result)))))
(defun filter-allowed-functional (xs allowed)
(let ((table (make-hash-table :test #'eql)))
(dolist (a allowed) (setf (gethash a table) t))
(remove-if-not (lambda (x) (gethash x table)) xs)))Code language: Lisp (lisp)remove-if-notは、条件を満たさない要素を除いたリストを返します（同じ O(|xs| + |allowed|)）。
member をループ内で呼ぶコードを見たら、まずその集合をハッシュテーブルに変換できないかを考えてください。
フィルタ・包含判定・集合演算はすべてこのパターンに帰着します。
8. 問題13 ソート済みリストの重複除去（入力の保証を活かす）
昇順ソート済みの整数リスト xs を受け取り、重複を除いたリストを返す関数を書いてください。
入力: xs = (1 1 2 3 3 3 4 5 5)
出力: (1 2 3 4 5)
入力: xs = (1 2 3 4 5)
出力: (1 2 3 4 5)
入力: xs = (7 7 7 7)
出力: (7)
入力: xs = ()
出力: ()Code language: HTTP (http)マージソート後の重複排除や、ソート済みログから一意なエントリを取り出す処理で使います。
ソート済みであることを活かせば、隣接する要素を比べるだけで O(n) になります。
問題8では一般のリストに対して重複除去をハッシュテーブルで O(n) にしました。
問題13には「ソート済み」という前提があります。
この保証を使うと、ハッシュテーブルすら不要になります。
8.1. 素直な実装 — 処理系依存の効率
remove-duplicates は一般のリストに対して O(n²) になりうる。
(defun unique-sorted-naive (xs)
(remove-duplicates xs :test #'=))Code language: Lisp (lisp)8.2. 効く実装 — O(n)
ソート済みなら、「重複は必ず隣接している」と仮定できます。
そうすると、問題4 の remove-adjacent-dups と同じ発想で、直前と比較するだけでよいことになります。
(defun unique-sorted-fast (xs)
"ソート済みなら隣接比較だけで重複を除ける。"
(when xs
(let ((result (list (car xs)))
(prev (car xs)))
(dolist (x (cdr xs) (nreverse result))
(unless (= x prev)
(push x result)
(setf prev x))))))
;; (unique-sorted-fast '(1 1 2 3 3 3 4)) => (1 2 3 4)Code language: Lisp (lisp)remove-duplicates のような一般関数に任せる前に「入力に何の保証があるか」を考えてください。
「ソート済み」という保証があれば問題4（隣接重複除去）と同じコードで O(n) になります。
問題4・問題13は同じ「直前と比較する」パターンの変形です。