【python】listに対する*演算子の実装
はじめに
某SNSで、以下のpythonコードが回ってきました :eye:
In [1]: li = [[0] * 5] * 5
In [2]: li
Out[2]:
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]
In [3]: li[0][1] = 10
In [4]: li
Out[4]:
[[0, 10, 0, 0, 0],
[0, 10, 0, 0, 0],
[0, 10, 0, 0, 0],
[0, 10, 0, 0, 0],
[0, 10, 0, 0, 0]]
このコードを見た時に、「listに定義されている*演算子の特殊メソッド(__mul__)の振る舞いが、shallowCopyをする実装がされている為」だと思ったのですが、果たして本当にlist君が想定通りの実装をしているか、定かではなかったです。
なので、今回本当にlistの__mul__はshallowCopyの実装をしているのか否かを追ってみました。
のメモ
オブジェクトについて
上記を追う前に、少しpythonのお話を。
pythonでは、扱うものすべてがオブジェクトです。1、2、'str'等も全てオブジェクトとして管理されます。
In [59]: print(type(1))
<class 'int'>
In [60]: print(type('aa'))
<class 'str'>
In [61]: help(int)
Help on class int in module builtins:
class int(object)
...
そして、全てのオブジェクトは、このPyObjectが元になっています
PyObjectにはざっくりと、ポインタの情報とオブジェクトの型の情報がある認識です。
そしてpythonで上記のポインタに当たるものを確認する上で一番簡単な方法として、id関数があります
上記は、ポインタに対して一意の値ではありますが、正確にはポインタとしての値ではなく、C側で管理しているメモリアドレスに対しての一意IDが返されています。
(ここら辺も追ってみたいですね！)
ちなみに冒頭のコードをidで表示すると、shallowCopyになっていることがわかります
In [78]: li = [[0] * 5] * 5
In [79]: li
Out[79]:
[[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0],
[0, 0, 0, 0, 0]]
In [80]: print(list(map(id, li)))
[3010697900288, 3010697900288, 3010697900288, 3010697900288, 3010697900288]
全ての配列のidが同じ、つまり同じメモリアドレスを指していました。このため、配列の要素どれかに変更を行った際、同じidを参照している先も変更されていました。
ちなみに上記idは、あくまでオブジェクトが生存している間の一意性を保証してくれるみたいです。
参照がなくなりメモリ開放された後は、idが同じでも別オブジェクトということはあるようです。
ここまでで、予想していた通りのshallowCopyになっていることは確認したので、目的のlistで何をしているのか。を見ていきたいと思います！
listの*演算子の実装
(ここからほぼドキュメントとコードを追っていくだけ...になります...)
なぜlistに対して、*演算子で要素を増やした際にshallowcopyになるのか。
これは、冒頭に記載した通りlistの*演算子時の振る舞いとして、shallowCopyを行うように__mul__に定義されているからです。それを追っていきます
まず、listはリストオブジェクトとしてpythonから扱われています。
そして、上記のリストオブジェクトはPyTypeObjectのインスタンスのようです。
この PyTypeObject のインスタンスは Python のリスト型を表現します。これは Python レイヤにおける list と同じオブジェクトです。
そしてリストオブジェクトの__mul__の振る舞いは、PyTypeObjectにあります。
(以下のsub-slotの下らへんに定義があります)
Slotsとしてsq_repeatが指定されている為、__mul__の振る舞いはこの関数が担っているようです。
上記説明に、この関数は PySequence_Repeat() で利用されと記述があるので、今度はPySequence_Repeatの定義を見に行きます。
Python の式
o * countと同じです。
おおお、いましたね。お目当ての関数はこの子のようです。ではここから実際にこの関数の実装がどのようになっているか見ていきます。
C実装内部
では上記関数の実装がどうなっているか、githubにコードがありますので覗いてみようと思います。
上記を雰囲気構文読解してみると、PyObjectの→sq_repeatが存在していれば呼ばれるみたいですね
listの実態はlistobject.cに定義があるため、そこにsq_repeatがあるか見ます
どうもこれ見たいです。なのでリストオブジェクトではlist_repeatが呼ばれるみたいです。
そのlist_repeatの関数は、ここに定義があります
retがreturnされているので、このretの代入元のlist_repeat_lock_held関数が要素を作成しているみたいですね
見た限り、お目当ての実際の処理部分のようですね！
関係ないですが、上記を読んでいて驚いたのは、この部分
見る限りサイズがない、もしくはa側に0以下を入力された際に新規listを返すようになっているみたいですねぇ。ふむふむ
実際にやってみました
In [119]: li = [0] * 5
In [120]: li
Out[120]: [0, 0, 0, 0, 0]
In [121]: li * -1
Out[121]: []
ほえー、これは知らなかったです。思わぬ収穫！(ところで、これどこで使うのだ、というツッコミはおいておいて)
本題に戻り、コードを見る限り、配列のコピー(要素が1つの場合)はこれが呼ばれているみたいですね
雰囲気C言語理解で行くとPyObject *elem = a->ob_item[0];で配列内の0インデックスのポインターをelemに代入していて、
それをdist_endになるまでdestに追加している(ポインターの参照先)って読み取りました。
このような実装になっている為、listの*演算子の処理では結果的にshallowCopyになる。と理解しました。
結論
listの__mul__はshallowCopyの実装をしているか否か
結論: していました！(shallowCopyの値が返ってきているのでそれはそうなのですが)
所感
後半ほぼコードを追うだけ + その記録した記事になってしまった...
pythonは利用者に上記のようなことを意識させずとも使える為、とても便利な反面、思わぬ落とし穴に嵌ることもある(自分も過去何回もやりました…)ので、元のC実装まで…とは言わずともpythonの実装部分までは知っておいて損はないなと思いました。
おまけ
In [60]: class DeepCopyList(list):
...: def __mul__(self, value):
...: return [copy.deepcopy(item) for _ in range(value) for item in self]
...:
In [61]: li = DeepCopyList([[0] * 5])
In [62]: print(list(map(id, li * 5)))
[2414688537280, 2414688655168, 2414687698432, 2414711176128, 2414687987264]
Discussion