3

次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、
実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。

もし可能であればそれらの判定方法の計算量も教えてもらいたいです。
おそらくO(1)であって、O(N)まではいかないにしてもわずかながら差があるのだろうなと思っています。

用意した配列nums

nums = [1,2,3,4]

方法1

純粋にlen()を使って判定した場合

# 9.7 ms ± 399 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit
n = 10**5
for i in range(n):
    if len(nums) > 0:
        pass

方法2

if numsとした場合。方法1の3倍くらい速い

# 3.75 ms ± 23.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
%%timeit
n = 10**5
for i in range(n):
    if nums:
        pass

補足

Python3.7を使っています

2
  • これら listが空かどうか判定する方法2つ, How do I check if a list is empty? が参考になりそうです。
    – kunif
    Commented 2019年7月4日 12:40
  • 過去の質問もそうですが解決した場合は回答横のチェックマークを選択して承認してください。解決していない場合は回答を受けて試してみた結果どうなり、何が解決しなかったのか質問文に追記してください。
    – Sieg
    Commented 2019年7月5日 1:08

2 件の回答 2

4

計測のために関数を用意しました。
グローバル変数アクセスコストの影響を避けるために、必要な値は引数で渡します。

>>> def f1(n, nums):
...     for i in range(n):
...         if len(nums) > 0:
...             pass
... 
>>> def f2(n, nums):
...     for i in range(n):
...         if nums:
...             pass

これを測定すると以下のような結果になりました。

>>> import timeit
>>> _nums = [1,2,3,4,5]
>>> timeit.timeit(lambda: f1(n**2, _nums))
6.453588549000187
>>> timeit.timeit(lambda: f2(10**2, _nums))
1.932719354000028

ここまでは元の質問にある通りの結果といえます。

そこで、内部でどのような中間コードが実行されるのかをdisモジュールで確認します。

f1の中間コード

>>> import dis
>>> dis.dis(f1)
  2           0 SETUP_LOOP              28 (to 30)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                16 (to 28)
             12 STORE_FAST               2 (i)

  3          14 LOAD_GLOBAL              1 (len)
             16 LOAD_FAST                1 (nums)
             18 CALL_FUNCTION            1
             20 LOAD_CONST               1 (0)
             22 COMPARE_OP               4 (>)
             24 POP_JUMP_IF_FALSE       10

  4          26 JUMP_ABSOLUTE           10
        >>   28 POP_BLOCK
        >>   30 LOAD_CONST               0 (None)
             32 RETURN_VALUE

f2の中間コード

>>> dis.dis(f2)
  2           0 SETUP_LOOP              20 (to 22)
              2 LOAD_GLOBAL              0 (range)
              4 LOAD_FAST                0 (n)
              6 CALL_FUNCTION            1
              8 GET_ITER
        >>   10 FOR_ITER                 8 (to 20)
             12 STORE_FAST               2 (i)

  3          14 LOAD_FAST                1 (nums)
             16 POP_JUMP_IF_FALSE       10

  4          18 JUMP_ABSOLUTE           10
        >>   20 POP_BLOCK
        >>   22 LOAD_CONST               0 (None)
             24 RETURN_VALUE

f2は中間コード量がだいぶ短いことがわかります。
最も差が出ている箇所だと思われるのが、f1にある 18 CALL_FUNCTION 前後の処理がf2にはないことです。
これを読み解くと、以下のことが分かります。

  1. if len(nums) > 0: とした場合、len関数の呼び出しを行い、結果をPythonインタプリタに返し、Pythonインタプリタ上で0と比較する処理が行われている(中間コード 14~24)。
  2. if nums: とした場合、numsが空かどうかをPythonインタプリタ上ではなく内部実装側で判定している(中間コード 14~16)。

これだけステップ数が異なると、処理時間も大きく変わることが想像できます。

3

次のような配列numsがあったときに、配列の要素数が0かそれ以外かを判定する方法で、
実装方法によってパフォーマンスに後述のような差がありました。どういう理由でこのような差が生まれてくるのかを教えてほしいです。

こちらだけ。
cpython限定ですが、試しにCでループ内処理を書いてみました。

/* Py_DECREF忘れてるよっ!というのはご愛嬌 */

void exec1(PyObject *obj)
{
    if (PyObject_IsTrue(PyObject_RichCompare(PyObject_Size(obj), PyLong_FromLong(0l), Py_GT))) {
        exec();
    }
}

void exec2(PyObject *obj)
{
    if (PyObject_IsTrue(obj)) {
        exec();
    }
}

lenやら演算子やら増えれば、抽象オブジェクトプロトコルを呼び出す必要性も出てくるので、それなりに差は出るんじゃないでしょうか。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。