Pythonの処理速度について

Question

処理速度に関して、Pythonの処理が並んでいるのを発見しました。
https://wiki.python.org/moin/TimeComplexity

多くはO(1)の処理速度ですが、Copyが常にO(n)の処理スピードを要する理由はなぜか、ご存じの方はいらっしゃるでしょうか。Get ItemやSet ItemがO(1)なので、なんとなくCopyもO(1)なのかなという印象なのですが・・。

Answer 1

この表でのCopyはマニュアルに書かれているlist.copy()の事だと思われます。

list.copy()は浅いコピーです。全体のコピーですので、listの要素全てを一つ一つ取り出してコピーしていく必要があります。つまり、一つの取り出し(Get Item)と一つの書き込み(Set Item)は要素の数だけ繰り返します。もし、Get ItemとSet Itemで実装したとしても、それぞれがO(1)であっても、そのO(1)の処理が要素数であるn回繰り返されるため、O(n)になります。実際の実装はもっと工夫して高速になっていると思いますが、要素数と処理時間が比例するという意味であるO(n)を越えて処理時間を短くすることはできません。

なお、他の処理は下記のようなコードの対比になっていると思われます。(Iterationだけこれでいいのか自信がありませんが)

a = [1, 2, 3, 4, 5]
# Copy
a_copy = a.copy()
# Append[1]
a.append(1)
# Insert
a.insert(2, -2)
# Get Item
a_item = a[3]
# Set Item
a[4] = 5
# Delete Item
del a[1]
# Iteration
it = iter(a)
a_it = [x * 2 for x in it]
# Get Slice
a_slice = a[2:4]
# Del Slice
del a[2:4]
# Set Slice
a[2:4] = [-4, -5]
# Extend
a.extend([6, 7])
# Sort
a.sort()
# Multiply
a_multi = a * 3
# x in s
a_in = [x * x for x in a]
# min(s), max(s)
a_min = min(a)
a_max = max(a)
# Get Length
a_len = len(a)

print("a", a)
print("copy", a_copy)
print("item", a_item)
print("it", a_it)
print("slice", a_slice)
print("multi", a_multi)
print("in", a_in)
print("min", a_min)
print("max", a_max)
print("len", a_len)

なお、O(n)はO(1)よりも時間がかかるという意味ではありません。処理時間が、O(1)は要素数に関係無く常に一定だが、O(n)は要素数に比例して長くなると言う意味です。処理の内容次第ですが、要素数が十分少ない場合、O(n)の処理がO(1)の処理より速い場合もあり得ます。

Comments

[arare000]

いつも大変詳細な回答、深く感謝申し上げます。

直感的にはDeep Copyの方が時間がかかりそうな印象があったのですが、これは、shallow copyがわざわざ参照元をいちいちO(n)の要素数分、チェックする必要があるということでしょうかね。逆にdeep copyは要素を丸ごとコピーするので、時間がO(1)かそれに近い反復回数で済む、というイメージで合っているでしょうか？

[raccy]

Deep Copyは今回の話とは全く関係ありません。

listはCレベルではPyListObjectという構造体なのですが、その中の`PyObject **ob_item`というメンバーで`PyObject *`の配列として補完されています(配列の領域自体はmalloc等で確保します)。浅いコピーをする場合、ob_itemの値そのものだけをコピーするのではなく、ob_item配列の要素を一つ一つコピーするという処理になっており、一つ一つのコピーはO(1)ですが、要素の数(nは要素の数のことです)だけ繰り返すからO(n)なのです。なお、参照カウンタがあるため、一つの要素をコピーをするO(1)には参照カウンタの処理`Py_INCREF()`が含まれており、これもn回呼び出されます。

もし、参照カウンタがなければ、Cの`memcpy()`で一度にコピーするという実装も可能でしょう。実際、参照カウンタがないRubyのArray#dupでは`memcpy()`を使っています(メモリバリアの処理があるから、一概にPythonより有利というわけではありません)。しかし、`memcpy()`も計算量はO(n)になると思います。copy-on-writeな`memcpy()`であればそのときだけのO(1)はできそうですが、そうではなさそうです。リスト自体をcopy-on-writeな実装にすれば、O(1)でコピーも夢ではないんですが、コピーされた方は変更時にものすごく遅くなりそうな気もしますので、誰もやっていないんじゃ無いかなと思います。

[teamikl]

オフトピになりますが、気付いた細かい点補足させて頂きます

> Iterationだけこれでいいのか自信がありませんが
Iterator は for in の部分に相当します。(iter()はイテレータを返すだけで O(1), for in で O(n))
後、set の x in s が O(1) なので、x in s は bool 値を返す方の in だと思います。

>`memcpy()`も計算量はO(n)になると思います。
この視点が抜けていた。私の下のコメント array のcopyで O(1) と言ってるのも O(n) ですね。
詳しい解説感謝！

[arare000]

大変ありがとうございます。まだまだ勉強不足ですみません。

少しずれますが、Pythonを使っていると、よく辞書型に遭遇するのですが、こちらはsetの集合体に参照用のkeyと変数が同時に割り当てられているということで、これをコピーする場合も基本的には同じ考え方(O(n)回処理)でお考えでしょうか。
http://docs.python.jp/3/tutorial/datastructures.html#dictionaries

あるいは、CPythonとPythonは根本的に異なりますでしょうか。こんがらがってしまいすみません。

[raccy]

setとdictの関係はちょっと調べないとわかりません。言語によってはdict相当のものでset相当のものを実装している場合もあるからです。改めて質問していただければと思います。

Pythonは言語名です。CPythonはPythonという言語の実装(環境)の一つである実装名です。CPython以外にもJythonやIronPython等といったPythonの実装が存在し、質問のサイトの表が他の実装全てに必ず当てはまるとは限りません。しかし、CPythonはPythonの実装で最も代表するものであるため、単にPythonと呼ぶ場合もあります。言語名ではなく、実装名(つまり、実際にインタプリンタとしてインストールする何か)としてPythonと言った場合は、CPythonの事を指します。

例文「Pythonを動かすために、Pythonを入れる」(前者のPythonは言語としてPythonであり、後者のPythonは実装としてのCPython、つまり、https://www.python.org/からダウンロードできるPythonなるものをインストールしている)

[arare000]

すみません、細かく教えて頂き大変ありがとうございました。心より感謝申し上げます。

Answer 2

Raccyさんのご回答で申し分ないのですが、一点だけ不思議なことに気づいたので補足。

リスト型には基本的なメソッドとして「Copy」というものが存在していないです。少なくともCPythonの実装ではそうです。そもそも基底となるシーケンス型にない。いっぽうで例えば辞書型には、基本メソッドとして「Copy」があります。

ので、いったい何の実行時間をくらべているのかよくわからないのですが、「Slice」はあるので「list[:]」でくらべてると考えるしかないでしょうか。Raccyさんの挙げたlist.copy()は内部的にこれと等価な実装です (ていうか私は今日の今日まで、list.copy()なんて知らなんだ! スライスでやってました)。

なお、資料では計算時間の指標が「コンテナの要素数n」とされていますから、shallow copyのみを考えています。deep copyではありえません。

Comments

[raccy]

あの資料はCPythonのCのAPIに関する資料ではなくて、CPython実装におけるPythonという言語に関する資料なのではないでしょうか？私はそう捉えました…。

というか、list.copy()の事じゃない！というのであれば、Copyとは具体的にどんなコードを指すことになるのでしょうか…。copy.copy()かな？

って、調べたらlist.copy()は別途定義じゃなくて、listなどを含めたシーケンシャル型の共通メソッドにしているのですね。わかりにくい。
http://docs.python.jp/3.5/library/stdtypes.html#mutable-sequence-types

[ikedas]

私が深読みしすぎたのかな。普通にマニュアル読んでれば気にならないことですね。

> CPython実装におけるPythonという言語に関する資料
ん? そうだとおもいますよ。拡張モジュールを書くときなんかにCopyがないということは、メソッドテーブルの該当スロットがNULLのままということですから。この点は標準オブジェクトも同じです。
ほかの操作とくらべ、Copyというのはそれほど普遍的な操作とはみなされていないのかと思います。(←この文、なn言ってるかわからないのではしょりました)

[arare000]

要素数nが必要な理由は、単純にそのリストの丸写しn(1)ではダメなのは、各要素に番号が割り振られるため、それを構成するkeyの割り振り振りをコピー時にする必要があるから、ですかね。

Answer 3

'https://wiki.python.org/moin/TimeComplexity'について、私も疑問です。
これ'copy'ではなくて'deepcopy'の時間では？
'copy'ならば浅いコピーでリストを作ってリスト要素のコピーだけだからそんなに処理時間を要さないと思うのですが。'deepcopy'であれば元をコピーするので納得しますが。

Comments

[teamikl]

(CPythonでの実装では) list の実装は C言語での array なので、メモリ自体の確保は O(1) で済みますが、
GCの参照カウントのインクリメントが各要素にコピー時に必要だからだと思います。
list (リスト)でなく array (配列) モジュールの配列オブジェクトなら copy は O(1) です

[arare000]

>MasahikoHirataさん、deepcopyとは何でしょうか。

[MasahikoHirata]

teamiklさん、私もそれが引っかかって。少し納得。まあチリも積もれば処理時間ですので。参考になります。

[arare000]

> teamiklさん
コメントありがとうございます。GCとは何でしょうか。つまり、一つ一つの要素に、番号を振り分けているため、そのままコピーはできない、ということでしょうか。

[MasahikoHirata]

’deepcopyとは何でしょうか。’。
'Copy'にはPythonに限らず’浅いコピー’と’深いコピー’とあります。’浅いコピー’では要素そのものではなくて、既に格納されている内容を参照できれば良い程度の情報だけをコピーする（時間がかからない。格納先と格納データの諸元だけコピー）するのに対し’深いコピー’では（実体）をコピーします（つまりｎの処理）。この違いで処理速度（する仕事の多さ）が違います。

[arare000]

>MasahikoHirata
deep copy to shallow copyの違いを表す処理速度に関するドキュメントは具体的にどちらを参照すればいいでしょうか。

[MasahikoHirata]

あれ？他の質問で回答しないでとおっしゃってますが？また解決している質問も放置ですよね？ググってご自分でお探しになる事を勧めます。

[arare000]

はい、今後はどうか自分のポイント稼ぎのために回答しないでいただければと思います。

[MasahikoHirata]

別に？ポイント集めると何か利点でも？

[teamikl]

ガベージコレクタの略です。メモリ管理
どこからも参照されなくなったオブジェクトを自動的に破棄する仕組みがあり、
PythonのGCの実装では、参照されている回数をカウントしています。

リストをコピーした場合、2つのリストから参照されることになるので
リストの各要素は、この参照カウントを増やしていく必要があり
これがあるために単純にまとめてメモリのコピーができないのだと思います。

一応、ソースコード確認しました。
listcopy内部ではsliceを呼んでいて、該当部分のコードは for の辺りです。
https://github.com/python/cpython/blob/1d0d35423dd0c13cd8306f3351e86873e6af5c5f/Objects/listobject.c#L431

[arare000]

>teamiklさん
大変ありがとうございます。貴重な参考とさせて頂きます。

[arare000]

>MasahikoHirata
喧嘩はあまり好きではないので、お互い平和に行きましょう。

[raccy]

deep copyであればO(n)とは比べものにもならないほど計算量が増えますし、そもそもlistの要素数nだけでは計算量が決まりません。コメントを見る限り、shallow copyとdeep copyの違いについても全く理解していないようですので、評価を下げされていただきます。

Answer 4

Pythonは、内部的にはオブジェクトで構成されているので、内部的に長さなどの情報は既に持っているので
処理時間が短い。(内部的にはポインタを入れ替えているだけ)
しかし、オブジェクト要素内部の文字列などのデータは移動する処理を数分繰り返す必要があるのでｎ回の時間がかかる。
と想像します。（詳しくはソースを読んでねってことになるんでしょうけど。）

Comments

[arare000]

ありがとうございます。ちょっとソース確認してみます。