56397


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

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

## 用意した配列nums

[code]

    nums = [1,2,3,4]
    
[/code]

## 方法1

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

[code]

    # 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
    
[/code]

## 方法2

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

[code]

    # 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
    
[/code]

## 補足

Python3.7を使っています


CC BY-SA 4.0
2019-07-04T12:27:03.930
56391
2019-07-04T15:12:18.813
32428
question
python python3 アルゴリズム array データ構造
Pythonの配列の要素数が0かそれ以外かを判定する方法のパフォーマンス


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

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

[code]

    /* 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();
        }
    }
    
    
[/code]

`len`やら演算子やら増えれば、[抽象オブジェクトプロトコル](https://docs.python.org/ja/3/c-api/object.html)を呼び出す必要性も出てくるので、それなりに差は出るんじゃないでしょうか。


CC BY-SA 4.0
2019-07-04T14:00:51.980
56394
2019-07-04T14:08:24.423
2019-07-04T14:08:24.423
15473
15473
56391
answer


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

[code]

    >>> 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
    
[/code]

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

[code]

    >>> 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
    
[/code]

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

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

f1の中間コード

[code]

    >>> 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
    
[/code]

f2の中間コード

[code]

    >>> 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
    
[/code]

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

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

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


CC BY-SA 4.0
2019-07-04T15:12:18.813
56397
2019-07-04T15:12:18.813
806
56391
answer