- 物理機リージョン/AZ
- ハイパーバイザVM exit で捕まえる
- VMゲストOS
- コンテナnamespace / cgroup
- プロセスアプリ / DB今ここ
前回、速さではなく増え方で測る理由を見ました。今回はその増え方が、データの置き方そのもので決まる例を見ます。
まず結論
同じ「並び」に見えても、要素の番地が連続しているか飛んでいるかで別物になります。連続していれば、第7週で見た「64バイトまとめ読み」がそのまま効きます。
そして「連結リストは挿入が O(1)」という言い方は、その位置に既に辿り着いている前提の話です。位置を探すところから数えると、話が変わります。
Python で list の末尾への追加(append)と deque の先頭への追加(appendleft)を100万回ずつ測りました。どちらが速かったでしょうか。
当てることが目的ではありません。外した予測ほど記憶に残るので、直感で選んでください。
並びの作り方は、大きく2つしかない
前回、速さではなく増え方で測る理由を見ました。今回は、その増え方がデータの置き方で決まる例を扱います。
10個の数を順に持つ方法は、大きく2つあります。
番地を連続させる — 隙間なく並べる。k 番目の場所は、先頭の番地に k 個ぶんを足せば求まります。探さずに計算で出ます。これが配列です。
番地を連続させない — 要素をばらばらの場所に置き、各要素に「次はここ」を持たせて繋ぐ。これが連結リストです。
この違いが2つの帰結を生みます。1つは、配列が速いのは第7週『キャッシュと記憶階層 — なぜ何段も重ねるのか』で見たまとめ読みが、そのまま効くからだということ。番地が隣り合っていれば、運ばれてきた分がそのまま次の要素です。飛んでいればこの効果は得られません。
もう1つは、配列は途中に入れると後ろを動かさなければならないことです。隙間なく並ぶ以上、隙間を作るには押しのけるしかありません。
公式は、その費用の理由まで書いている
Python の公式文書は、list の先頭操作について次のように書いています。
Though list objects support similar operations, they areoptimized for fast fixed-length operations and incur O(n)memory movement costs for pop(0) and insert(0, v) operationswhich change both the size and position of the underlyingdata representation.
注目したいのは最後です。which change both the size and position of the underlying data representation — 大きさと位置の両方が変わるから、と理由まで書かれています。アーカイブ処理中の Python Wiki は、同じ移動を pop(k) の側から memmove と名指ししています。
同じ節の直前には、deque 側がこう書かれています。
Deques support thread-safe, memory efficient appends and popsfrom either side of the deque with approximately the same O(1)performance in either direction.
approximately the same O(1) performance — およそという語が付いています。公式が断定を避けた箇所を、読む側が断定しないことです。
Python 公式は list の pop(0) と insert(0, v) が O(n) になる理由を何と説明していますか。
「挿入が O(1)」は、どこから数えているのか
ここで、よく並べて語られる2行を見ます。C++ の標準ライブラリの記述です。
std::list::insert 1,2) Constant.std::vector::insert 1,2) Constant plus linear in thedistance between pos and end ofthe container.
片方が Constant で、もう片方は距離に比例する。ここだけ見れば「連結リストの挿入は速い」と読めます。しかし両方の insert が、第1引数に pos(位置)を取ります。 どちらも「その位置が既に手元にある」状態から数えた値です。list が Constant なのは、位置を探す費用が計算量に含まれていないからで、その費用が無いからではありません。
- ・記述されているのは下から2段目だけ。上の段は読む側が補う
- ・位置を持ち歩く処理(順に辿りながら消す等)なら Constant がそのまま活きる
同じ「先頭に入れる」でも、増え方が違う
実測です。Python 3.12.14(Linux コンテナ / Apple Silicon、複数回の最良値)で n 回の操作の合計時間を測り、n を10倍にしたときの倍率を並べました。
== 1. list.insert(0, v) を n 回 ==n 最良時間(ms) 前のnからの倍率1000 0.142 -10000 12.034 85.0x100000 1221.778 101.5x== 2. list.append(v) を n 回 ==n 最良時間(ms) 前のnからの倍率1000 0.015 -10000 0.217 14.9x100000 1.689 7.8x1000000 17.891 10.6x== 3. deque.appendleft(v) を n 回 ==n 最良時間(ms) 前のnからの倍率1000 0.015 -10000 0.166 11.0x100000 1.983 11.9x1000000 21.547 10.9x
1 と 3 は、どちらも「先頭に入れる」という同じ操作です。 それでも増え方が違います。1 は n を10倍にすると約100倍、3 は約10倍。1回あたり O(n) の操作を n 回繰り返せば合計は n² に比例するので、10倍の入力は100倍の時間になります。
倍率がちょうど100や10にならない(85.0倍など)のは、繰り返し自体の費用が測定に含まれているからです。見ているのは増え方の傾向であって、係数ではありません。 絶対値は測定環境のものです。
そして表をもう一度見てください。n=1000000 で、list.append が 17.891ms、deque.appendleft が 21.547ms。 得意な側どうしの比較で、deque のほうが遅くなっています。
std::list::insert が `Constant.` なのに「連結リストの挿入は速い」と言い切れないのはなぜですか。
得意な側に追加する — list が勝つ
n=1000000 で、list の末尾追加 17.891ms に対し deque の先頭追加 21.547ms。増え方は同じ約10倍で、list がわずかに速くなりました(deque.append は未測定)。
n list.append deque.appendleft1000000 17.891 ms 21.547 ms倍率(n×10) 10.6x 10.9x増え方は同じ。定数倍で list が上回った
先頭に挿入する — deque が勝つ
先頭では list の合計が n² に比例します。n=100000 で 1221.778ms。deque は n=1000000 でも 21.547ms で、桁が違います。
n list.insert(0,v) deque.appendleft100000 1221.778 ms 1.983 ms1000000 (未測定) 21.547 ms倍率(n×10) 101.5x 10.9x増え方そのものが違う
同じ2つの構造を同じ環境で測って、得意な側への追加では list が、先頭挿入どうしでは deque が勝ちました。この2つの結果から言えることは何でしょうか。
「どちらの構造が優れているか」という問いの立て方そのものを疑ってみてください。
この章のまとめ
- 並びの作り方は「番地を連続させるか、させないか」で分かれる。この一点から性質の違いが導かれる。
- 配列が順読みで速いのは、第7週で見たまとめ読みの単位がそのまま活きるから。飛べばこの効果は無い。
- 配列の途中への挿入・削除は後ろを動かす費用がかかる。Python 公式はその理由を「大きさと位置の両方が変わるから」と書いている。
- 「連結リストは挿入が O(1)」は、位置が既に手元にある前提の話。 C++ の
insertはどちらも第1引数に位置を取る。探す費用は計算量の外側。 - deque が list より速いわけではない。 桁で勝つのは list の先頭挿入に対してで、得意な側どうしでは list がわずかに上回った。
- CPython の deque は純粋な連結リストではない。Python Wiki 自身が
a list of arrays rather than objectsと自己訂正している。
自分の現場で確かめる
読んだだけでは身につきません。手元の環境で実際に見てみてください。
理解度チェック
読んだ直後は「分かった」と感じやすいものです。実際に解いて確かめてください。
配列を順に読むと速いのはなぜですか。
用語集(4語)
- 配列
- 要素を番地の連続した領域に並べたもの。k 番目の場所は先頭からの計算で直ちに求まる。途中に入れると後ろを動かす必要がある。
- 連結リスト
- 各要素が次の要素の居場所を持つことで繋がった並び。番地は連続していなくてよい。添字での直接アクセスが無く、位置を探すには辿る必要がある。
- 両端キュー (deque)
- 両端への追加・取り出しを扱う並び。CPython の実装は純粋な連結リストではなく、Python Wiki が `a list of arrays` と述べている形。
- memmove
- 記憶上のある範囲を別の位置へまとめて移す操作。配列の途中を抜いたとき、後続をずらすのに使われる。