第7章 前半: 参照の共有、リストの中身、辞書の仕組み

• 名前の代入は対象に結ぶ操作で、要素への代入は入れ物の中の参照を変える。共有している物を変えれば、別名のどこからでもその変化が見える。
• list は参照を並べた領域で、添字の読み取りは定数時間、先頭への挿入は多くの参照を動かす。
• dict と set はハッシュで候補を絞って比較する。構造は、保存したい意味から選ぶ。

教材の 7.1 節から 7.2 節まで。

7.1.1 名前、参照、共有

教材の 7.1.1 の節は、Python が扱うデータを、すべてオブジェクトとして説明する。1 つのオブジェクトは、型と、いまの値と、ほかの個体と区別するための同一性を持つ。名前を対象に結ぶことが束縛、結び直すことが再束縛で、名前から対象へ伸びる矢印を参照と呼ぶ。この矢印は値の複製ではなく、機械のポインタを 1 本ずつ保存するという仕様でもない。

a = [10, 20] のあとで b = a とし、b.append(30) を実行すると、a からも 3 要素が見える。続けて b = [99] とすると、b だけが新しいリストへ結び直される。教材は「b を操作したら a も変わる」という言い方を正確でないとし、動いたのは名前ではなく、2 つの名前が指していたリストの中身だと説明する。b = [99] は名前への代入、b[0] = 99 は参照先の要素への代入で、後者は a からも見える。

整数では、y = x のあとに x = x + 1 としても y は 10 のままである。足し算の結果へ x を結び直しただけで、元の整数は書き換わらない。

== は値の等しさ、is は同じ個体かどうかを問う。同じ内容のリストを別々に作ると、等しいが同一ではない。欠損の確認だけは is None で行う。[row] * 2 は同じ行への参照を 2 つ作るので、一方を変えると両方が変わり、内包表記なら行を毎回作れる。+= は、リストでは既存のリストを広げ、整数では結果へ結び直す。記号が同じでも、動きは相手の型で決まる。

del は名前の束縛を取り除くだけで、共有先のメモリを消す命令ではない。共有にかかる仕事は、リストが長くても変わらない。外側だけを複製すれば、要素の数に応じて増える。共有は複製の時間とメモリを節約できる一方、片方の変更がもう片方に響くので、どの処理が内容を変えてよいかを先に決める必要がある。

7.1.2〜7.1.3 list と tuple の中身

CPython の list の内側には、参照が連続して並ぶ領域があり、動的配列と呼ばれる。使っている長さ n と、確保した容量 c を分けて持つ。参照 1 つの幅が p バイトなら、添字 i の参照は先頭から i × p の位置にあるので、読み取りは n に関係なく一定の時間で済む。

先頭への挿入は、参照を 1 つずつ後ろへずらす。末尾への追加は、空きがあればすぐ書けるが、空きが無いと領域を広げて参照を移すので、1 回だけを見れば最悪の時間は n に比例する。余分な容量を比例的に確保すれば、長い追加の列全体では合計が n に比例し、これを償却計算量と呼ぶ。先頭への挿入を n 回続けると、動かす参照は合計 n(n-1)/2 本になり、1,000 回の場合は 499,500 本である。

tuple が固定するのは、順番と各位置が指す対象である。中に list があれば、その中身は変えられる。1 要素の tuple はカンマで成立し、(3) は括弧付きの整数にすぎない。([1], 9) のように list を含むとハッシュを計算できず、tuple なら必ずキーになる、とは言えない。

7.2.1〜7.2.2 dict と set

ハッシュ関数はキーから整数を作り、探す候補を絞るために使われる。説明用に 4 つの枠を用意し、ハッシュ値を 4 で割った余りを最初の位置とすると、5 と 9 はともに位置 1 に集まる。これが衝突で、実際には候補の同一性や等価性を比べ、合わなければ次の候補へ進む。契約は、等しいキーならハッシュも等しいことで、逆は成り立たない。キーを登録したあとにハッシュの元の値を変えると、項目を見つけられなくなる。

CPython では dict も set もハッシュ表を使うが、中の並べ方は同じとは言えない。削除した枠は、後続のキーの探索を続けられるよう、跡を残して管理する。通常の dict は、探すための索引と、項目を並べる領域に分かれ、後者の順が挿入順の反復を支える。set の取り出し順は保証されない。検索と登録は平均すると一定の時間だが、衝突が集中する最悪の場合は n に比例する。

7.2.3 構造を選ぶ

教材は、速い型を先に選ぶのではなく、必要な情報を先に挙げる流れを示す。文を復元するなら順番と重複、既知かの確認なら所属、確率を作るなら単語と件数が要る。「猫 犬 猫」を set にすると 2 種類しか残らず、元の語順や件数は戻せない。これは性能の差ではなく、情報の喪失である。語数 n、異なり語数 v のとき、各語で count を呼ぶ書き方は n × v に比例する。1 回走査して数える dict なら平均で n に比例する。

後半は、関数、クラス、デコレータ、語彙の小さな設計へ進む。