Dev Study
← データ構造とアルゴリズムの土台
レッスン 13 / 13·約 9 分·第11期 データ構造とアルゴリズムの土台

選ぶとは、捨てること

アプリと DB の下に何が積まれているか(左が下、右が上)
  1. 物理機リージョン/AZ
  2. ハイパーバイザVM exit で捕まえる
  3. VMゲストOS
  4. コンテナnamespace / cgroup
  5. プロセスアプリ / DB今ここ

本コースの最終回です。ここまでで測り方・構造・見積もりを見てきました。今回はそれらを使って「選ぶ」ところまで進みます。

まず結論

全部が速いデータ構造はありません。何かが速い構造は、別の何かが遅いか、別の何かを余分に使います。

だから「どれが速いか」には答えがなく、「自分がする操作は何で、何を捨ててよいか」だけが答えられる問いです。PostgreSQL の公式文書は、索引について同じことを trade-off という語で書いています。

? 読む前に予測

同じ10万件のデータを Python の list と deque に入れ、同じ機械で測りました。どちらが速いでしょうか。

当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。

抽象原理

速くする先を選ぶことは、遅くする先を選ぶこと

ここまでで、増え方の測り方、構造ごとの計算量、走らせる前の桁の見積もりを見ました。最後に残るのは選ぶ作業です。

全部が速い構造はありません。 ある操作を速くする設計は、必ず何かを差し出しています。差し出すものは3種類です。

  1. 別の操作の速さ — 検索を速くすると、別の操作が遅くなる
  2. 記憶領域 — 余分な表や索引を持つぶん、場所を食う
  3. 性質そのもの — 順序、重複、誤りの検査

公式文書はこれを隠していません。cppreference の std::list は、2つの性質を同じ段落に並べています。

std::list is a container that supports constant time insertion and removal of elements from anywhere in the container. Fast random access is not supported.

「どこでも定数時間で挿入できる」と「高速なランダムアクセスは提供しない」が並んでいます。片方だけを引くと、この構造の姿が変わります。

「速い構造を選ぶ」ではなく「捨てるものを選ぶ」
自分がする操作検索か、両端の出し入れか、添字か
していない操作 = 捨ててよいもの
別の操作の速さ使わないなら遅くてよい
記憶領域余分に持てるか
性質順序・検査を手放せるか
捨てられるものが決まると候補が絞れる
選べる構造残った候補から選ぶ
  • ・出発点は構造の一覧ではなく、自分がする操作の一覧
具体実物

実測 — 最速が行ごとに入れ替わる

同じ10万件を Python の list / set / dict / deque に入れて測りました。timeit.repeat(repeat=5) の中央値、Docker 上の python:3.12-alpine(Apple Silicon 機、2026-09-18)での1回の測定です。絶対値を一般則にしないでください。

n=100,000 / 1操作あたりの所要時間 ns(検証環境での実測)コマンド出力
操作                     list          set        dict        deque
検索(末尾の値) x in c   486,339.6      12.5 ★      14.2    517,452.1
検索(先頭の値) 0 in c         6.7 ★     8.2         9.0          6.8
先頭 push+pop            48,847.2    該当なし    該当なし         12.8 ★
添字(まん中) c[50000]        7.0 ★   該当なし       14.8      3,413.4
容器の大きさ bytes       800,056   4,194,520   5,242,960      825,496
 
★ = その行での最速

★が行ごとに動いています。 検索は set、先頭の出し入れは deque、まん中の添字は list。1つの構造が全部を取ることはありませんでした。特に deque と list は2回逆転します。 先頭の出し入れで 3,807倍、まん中の添字で 490倍。片方だけ見れば「deque が速い」とも「list が速い」とも言えてしまいます。

✓ ここまでの確認

Python の公式文書(collections)は、deque の添字アクセスについて何と書いていますか。まん中の添字で deque が list に 490倍負けた実測と合わせて選んでください。

抽象原理

この差は、公式文書が理由まで書いている

490倍という差は偶然出た数字ではありません。Python の公式文書(collections)は、deque の代価を名指しで書いています。

Indexed access is O(1) at both ends but slows to O(n) in the middle. For fast random access, use lists instead.

CPython 3.12 の deque は、要素64個(BLOCKLEN 64)ずつのブロックをリンクでつないだ構造です。添字を引く deque_item は、両端以外では近い端からブロックを1つずつたどり、10万件のまん中なら約780回です。両端の出し入れを安くした代価が、まん中の O(n) です。

C++ の std::deque は設計が違い、cppreference は添字が two pointer dereferences で済むと書きます。同じ名前でも言語が違えば代価の払い方が違うので、別の言語の文書で実測を説明しないでください。

具体実物

同じ交換を、データベースの公式文書が書いている

これは Python や C++ に限った話ではありません。PostgreSQL の公式文書は、索引について同じ構造を3段重ねで書いています。

まず読みが速くなる側(11.1 Introduction)。索引が無ければ scan the entire test1 table, row by row だが、あれば it might only have to walk a few levels deep into a search tree で済む、と述べます。木を数段たどるだけになる話は、本コースで木の高さを扱った回の通りです。

次にその代価。

After an index is created, the system has to keep it synchronized with the table. This adds overhead to data manipulation operations. Indexes can also prevent the creation of heap-only tuples. Therefore indexes that are seldom or never used in queries should be removed.

読みを速くした代価としてデータ操作に overhead が加わる。だから使われていない索引は消せ、と結論まで書いてあります。

そして 14.4 Populating a Database は、捨てる判断が状況で変わることを書いています。既存の表への大量投入なら索引を落とすほうが有利かもしれない、としつつ Of course, the database performance for other users might suffer during the time the indexes are missing. と添え、一意索引については the error checking afforded by the unique constraint will be lost while the index is missing と警告します。外部キー制約の節では、この交換に公式が名前を付けています。

Again, there is a trade-off between data load speed and loss of error checking while the constraint is missing.

投入の速さと、誤り検査を失うこと。その間に trade-off がある——このレッスンの題そのものを一次ソースが使っています。 しかも交換の相手は速さではなく正しさの検査です。捨てられるものは時間と空間だけではありません。

✓ ここまでの確認

検証環境の実測で、同じ `x in list`(list に対する `in`)が先頭の値では 6.7 ns、末尾の値では 486,339 ns になりました。ここから言えることはどれですか。

⇄ 2つを見比べる
具体例 A

まん中の添字アクセス c[50000]

10万件のまん中を1つ引く操作です。list は連続した領域なので位置を計算して1回で届き、7.0 ns。deque はブロックを近い端から1つずつたどるので、3,413.4 ns。検証環境では list が 490倍速くなりました。

具体例 B

先頭への挿入と削除

先頭に入れ、すぐ取り出して長さを保つ操作です。list は連続した領域なので後続の全要素の位置がずれ、48,847.2 ns。deque は両端の出し入れに向いた構造で 12.8 ns。検証環境では deque が 3,807倍速くなりました。

同じ list と deque が、2つの操作で逆の結果を出しました。ここから引き出せる原理は何でしょうか。

「どちらの構造が優れているか」ではなく、「何が2つの結果を分けたのか」を考えてみてください。

この章のまとめ

  • 全部が速い構造はない。 検証環境の実測では、検索は set、先頭の出し入れは deque、まん中の添字は list と、最速が行ごとに入れ替わった。
  • deque と list は2回逆転する。 先頭の出し入れで 3,807倍、まん中の添字で 490倍。どちらの向きにも差がつくので、操作を言わない順位づけは成立しない。
  • Python の公式文書は deque の添字について、両端は O(1) だがまん中では O(n) に落ちると書く。代価の形を公式が説明している。(C++ の std::deque は設計が違う)
  • 差し出すものは3種類。別の操作の速さ・記憶領域・性質そのもの(順序や誤りの検査)。PostgreSQL は投入の速さと検査の喪失について there is a trade-off between data load speed and loss of error checking と明記している。
  • 同じ in でも探す値の位置で 約72,000倍変わった。構造だけでなく「どこを探すか」でも変わるが、当たりの位置に賭けられないので最悪側で扱う。
  • 第11期では、増え方で測り、その測り方で構造を選び、走らせる前に桁を見積もる道具を積み上げました。最後に残るのは、速くする先ではなく捨ててよいものを自分で決めることで、その判断だけは計算量にも実測にも代わりに答えてもらえません。

自分の現場で確かめる

読んだだけでは身につきません。手元の環境で実際に見てみてください。

環境:

理解度チェック

読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。

問題 1 / 3正解: 0

「検索が速いので list を set に置き換えました」という変更を受け取ったとき、最初に確認すべきことはどれですか。

用語集(3語)
トレードオフ (trade-off)
一方を良くすると他方が悪くなる関係。PostgreSQL の文書は there is a trade-off between data load speed and loss of error checking と書いている。
deque
両端の出し入れに向いた列。Python の公式文書は、添字アクセスは両端で O(1)、まん中では O(n) に落ちると記述している。
容器自身の大きさ
Python の sys.getsizeof が返す値。そのオブジェクトに直接帰属する分だけで、参照している要素オブジェクト本体は含まない。

出典(一次ソース)