Python の組み込み関数の計算コストについて

Question

Pythonに組み込まれている関数
例えばsum、やmaxなどの計算コストはどのくらいなのでしょうか？
Sumやmaxなどはリストの全ての箇所を見に行かなければいけないので、例えばリストが1000要素持っていたら動的計画法の問題を解くときなどに、1000回最大値を求める必要があったとしたらそれだけで100万回の計算をしているのでしょうか？
また、reverseについても教えて欲しいです。
普通のソートならともかくリバースは座標を反転させるだけなので計算コストは1と考えてよろしいですか？

その他にも色々な計算コストについてあれば教えて欲しいです。
よろしくお願いします。

[追記]
リストの生成についても教えて下さい。
単純に0が1億個あるリストを生成するコストなどを他の計算コストと対比で教えて欲しいです。
また、多次元リストと普通のリストで違いはあるでしょうか？

Answer 1

maxやsumは概ね対象となるIterableの要素数のオーダーであろうと考えるのが妥当です。

実際にどうかを詳しく調べるならソースコードを見るのが確実です。PythonはOSSなのでソースが公開されてます。CPython(いわゆる標準的なPythonインタープリタ)であればgithubにソースコードがありmaxの実装コードを探すとbuiltin_max(主な処理はmin_max)というCの関数になっているようで

https://github.com/python/cpython/blob/master/Python/bltinmodule.c

に含まれてるようです。min_maxを見ると実際Iterableの要素数文だけループしながら比較している様子がうかがえます。

リバースは座標を反転させるだけなので計算コストは1

いいえ。計算コストが1ならばどれほど要素数の多いリストでも反転にかかる時間が同じということになりますがそんなことはありません。要素数が多ければ多いほど「場所を入れ替える回数」は多くなるはずです。Pythonのlistインスタンスはメモリー上では

+-------------------+
|control information|
|...                |
+-------------------+
|N = element count  |
+-------------------+
|ref of element 0   |
+-------------------+
|ref of element 1   |
+-------------------+
...
+-------------------+
|ref of element N-1 |
+-------------------+

のようになっており、reverse()は上記のelement 0～element N-1を入れ替える機能ですので少なくともN // 2回程度の入れ替え操作が必要ということになります。(reverseの実装を見てはいないですが、それ以下で結果が得られるとは思えません。)

---

その他にも色々な計算コストについてあれば教えて欲しいです。
単純に0が1億個あるリストを生成するコストなどを他の計算コストと対比で

Pythonのビルトイン関数はたくさんありますしリストを生成する方法も複数あります。そのような事項について無作為にあるいは盛沢山な内容の知識を「気軽に一つの質問で」人から知識を得ようとするのは質問側のスタンスとして間違っている気がします。

例えばリストを生成する方法であなたは次の方法をご存じでしょうか？またそれぞれについてどんな性能特性があると思われますか？

l1 = [0] * 100000000

l2 = []
for i in range(100000000):
    l2.append(i)

l3 = [0, 0, 0, 0, ...]   # 実際に書く気になりませんね...

l4 = [0 for _ in range(100000000)]

あなたの後半の質問にまともに答えようとするといくらでも書けてしまいます。あなたが具体的に知りたいことだけに絞ってください。そうすれば回答側が無駄なこと(あなたが知りたいと思う以上のことや、あなたが消化しきれないかも知れないこと)を書かずに済みます。

もし後半部分の質問をしたいなら本質問とは別に「一つの内容に絞って」質問すべきと思います。

Answer 2

数値演算の基本アルゴリズムやそのコスト(計算量、資源(必要メモリ)量など）について詳しく知りたいのであれば、アルゴリズムの大家、ドナルド・E・クヌースの著書『The Art of Computer Programming』シリーズをお読みになることをお勧めします。

第1巻「基本アルゴリズム」と、第3巻「ソートと探索」を基礎知識として最初に読み、更に残りの巻から自分が興味のあるものを読んでいくのが良いと思います。

英語に堪能なら原著を、そうでないなら日本語訳を

Answer 3

組み込み関数計算コストは組み込み関数の実装によるとしか言えません。

ですので、実際に計測してみるか、組み込み関数のソースコードを読んでみるしかないと思います。

参考：
Python のソースを読んでみる

Sumやmaxなどはリストの全ての箇所を見に行かなければいけないので、例えばリストが1000要素持っていたら動的計画法の問題を解くときなどに、1000回最大値を求める必要があったとしたらそれだけで100万回の計算をしているのでしょうか

おそらく勘違いだと思いますが、sum 関数や max 関数の引数に 1000 要素を持つリストを渡す場合の計算回数は「1000 - 1 = 999 回」ではないでしょうか？（総当たりで計算する必要ありませんので）

Comments

[babbleman]

いえ、例えば１０００回の動作で見に行くリストの対象が変わるとします（インデックスが2:20であったり5:15であったり）。その都度その都度最大値を求めるとしたら１０００回×リストの要素数分の計算が必要になるのでしょうか、という事です。

[nskydiving]

そうですね、その都度その計算量が必要になります。

[babbleman]

ありがとうございます。
dp[][]で作ったんですけれど、例えばdp[1]の更新を一通り終えた後にその時点での最大値を
maxvaluelist[1]などに格納してもっと先、例えばdp[100][]などでmaxvaluelist[1]を確認しに行くというのはどうでしょうか？

[nskydiving]

最初の回答に戻りますが、Python の実装によるので何とも答えようがありません。
実際のにコードを書いて、ご自身で計測していただくのが一番早いと思います。