スライスは参照だと思ってた
PythonでもNode.jsでも配列は参照渡しなので、以下のような挙動をする。1
>>> mc = ["百田", "玉井", "佐々木", "高城", "有安", "早見"]
>>> mc2 = mc
>>> mc[0] = "俺"
>>> mc
['俺', '玉井', '佐々木', '高城', '有安', '早見']
>>> mc2
['俺', '玉井', '佐々木', '高城', '有安', '早見']
上記のコードにおいて mc2 は「 mc が参照しているメモリアドレス」しか持っておらず具体的な値は共用しているため、どちらかの配列要素に対する操作は両方に適用される。これがいわゆる「参照渡し」であり、この操作の計算量はO(1)である (=計算量が配列長などの影響を受けない)。
ところで、Pythonは配列に [start:end] という形式で添え字アクセスすることで、元配列のスライス (部分配列) を取得することができる。以下のような感じである。
>>> mc = ["百田", "玉井", "佐々木", "高城", "有安", "早見"]
>>> mc[0:5]
['百田', '玉井', '佐々木', '高城', '有安']
普通に mc[0] のような添え字アクセス (これもO(1)である) と記法が近いこともあり、僕は上記のようなスライス取得も参照渡しだと思い込んで5年間ぐらい生きてきた。
が、結論から言うとこれは間違いである。ちゃんとコードを書いている人なら皆知っていることなのだと思うけど、積極的に恥を晒していくスタンスを貫くためにも唇を嚙みながら書いていくッ。
スライスは部分コピーである
調べたら CPythonの配列操作の計算量一覧が載っているページ に辿り着いた。ここでGet Sliceの計算量はO(k)であると説明されている。ここでいうkは取得するスライスの配列長を指すので、扱うスライスの長さに比例してコストが上がる処理ということになる。つまるところ List[start:end] というのは「配列の途中に対する参照を渡す」などという生易しい処理ではなく、ガッツリ元配列への走査を行って要素ひとつひとつをコピーしていたのだった。
これはコード上の挙動からも確認できる。冒頭に示した配列の参照渡しと異なり、元配列の値を変更してもスライスは影響を受けない。
>>> mc = ["百田", "玉井", "佐々木", "高城", "有安", "早見"]
>>> mcz = mc[0:5]
>>> mc[0] = "俺"
>>> mc
['俺', '玉井', '佐々木', '高城', '有安', '早見']
>>> mcz
['百田', '玉井', '佐々木', '高城', '有安']
結局、僕の勘違いは「オブジェクトからオブジェクト引っ張るんだから参照渡しでしょ」みたいな仕組みに対する謎の断定と、簡易な文法を鵜呑みにした結果だったように思う。2
アルゴリズムそれぞれ
なんというか、あらためてオブジェクト (=プリミティブでないもの) をポインタとして考えておくことというか、インタープリタ (コンパイラ) の気持ちになることというか、そういうプログラマ一年生の心掛け的な基礎の欠落を痛感した出来事だった。
自分がコードを書いたりレビューしたりするとき、割と自覚的にパフォーマンスと可読性のトレードオフにおいて許される限り後者を選択するようにしていて、for文を使えばループを減らせるところもmap/reduceで宣言的に書くとか、空間計算量の増大を許容してでも適切な説明変数を使うとか、そういうことを心がけている。実際に業務でカリカリに計算量を削る必要に駆られる場面は少ないのだけど、こういうことが分からないと「許される限り」の線引きも分からないのだ…と感じた。
前に出来心で プログラミング言語C を読んだらJavaScriptのオブジェクトに関する挙動について閃きがあった (なにが閃いたかは忘れた) ので、GW中に読み返してみたいと思う。
追伸
「言語の実装も含めてアルゴリズムなんだなあ」という詩をどこかに挟もうと思っていたんだけど、「雑司ヶ谷」を「○○を」というフォーマットに落とし込めなかったので諦めてここに供養する。