Python 内包表記の限界: 複雑な処理と実行速度の関係

## 初めに
- 本記事は実務上で速度的優位性を得るために内包表記を使うことが合理的かどうか検証したものです。
- 文中のコードは読者層を広くするために型ヒントを省いています。

## 更新履歴
<details><summary>詳細</summary><div>

- 追記 (2023/05/24)
計測環境はPython3.12.0a6です。

- 修正 (2023/05/24)
記事中のバイトコードがPython3.7.16のものだったのでPython3.12.0a6のものに差し替えました。

- 修正 (2023/05/27)
「list(generator) 使えよ」とのご指摘があったので
単純な例の内包表記を```[i for i in range(ELEMENTS)]```から```list(range(ELEMENTS))```に修正しました。
ご指摘ありがとうございます。

- 追記 (2023/05/28)
Twitterでの反応に対しての追記を行いました。
</div></details>

## 内包表記は速い！
以下に比較対象のコードを示します。
```Python3:単純な例
ELEMENTS = 20000000  # 20,000,000


def list_comprehension():
    return list(range(ELEMENTS))


def for_loop():
    result = []

    for i in range(ELEMENTS):
        result.append(i)

    return result


list_comprehension()
for_loop()
```
そして以下にcProfileを使って計測した実行時間を示します。

 **ncalls** | **tottime** | **percall** | **cumtime** | **percall** | **filename:lineno(function)**                         
------------|-------------|-------------|-------------|-------------|-------------------------------------------------------                       
 1          | 0.286   | 0.286   | 0.286      | 0.286      | speed_test.py:4(list_comprehension)                   
 1          | 2.083       | 2.083       | 2.758       | 2.758       | speed_test.py:8(for_loop)     

内包表記を用いた方が2.758s / 0.286s ≒ 9.64倍の速度が出ています。
圧倒的な差がついていますね。

しかし、この比較はだいぶチェリーピックです。
（アルゴリズムをガリガリ書く以外の業務で上記のような単純なコードを書く機会はなかなか無いと思います…）

## 内包表記を一般的なユースケースで評価する
以下にif文での要素選択を行うコードを示します。
（personsの生成で結構な時間を食ってしまうため、要素数は前項の10分の1にしています。）

```Python3
ELEMENTS = 2000000  # 2,000,000


class Person:
    def __init__(self, age):
        self.age = age


def list_comprehension(persons):
    return [person for person in persons if person.age >= 18]


def for_loop(persons):
    adults = []

    for person in persons:
        if person.age >= 18:
            adults.append(person)

    return adults


persons = [Person(i) for i in range(ELEMENTS)]

list_comprehension(persons)
for_loop(persons)
```
だいぶありがちなコードになりました。

計測してみると
 **ncalls** | **tottime** | **percall** | **cumtime** | **percall** | **filename:lineno(function)**                         
------------|-------------|-------------|-------------|-------------|-------------------------------------------------------                           
 1          | 4.897e-06   | 4.897e-06   | 0.1095      | 0.1095      | speed_test.py:9(list_comprehension)         
 1          | 0.2714      | 0.2714      | 0.3435      | 0.3435      | speed_test.py:13(for_loop)                            
       
 
0.3435s / 0.1095s ≒ 3.1倍となりました。

## そもそも何で実行時間が違うの？
ここで先ほど計測した関数のバイトコードを見てみましょう。
```python:list_comprehension()
  9           0 RESUME                   0

 10           2 LOAD_CONST               1 (<code object <listcomp> at 0x7f37b5b57230, file "/workspaces/ext-list/test.py", line 10>)
              4 MAKE_FUNCTION            0
              6 LOAD_FAST                0 (persons)
              8 GET_ITER
             10 CALL                     0
             20 RETURN_VALUE

Disassembly of <code object <listcomp> at 0x7f37b5b57230, file "/workspaces/ext-list/test.py", line 10>:
 10           0 RESUME                   0
              2 BUILD_LIST               0
              4 LOAD_FAST                0 (.0)
        >>    6 FOR_ITER                20 (to 50)
             10 STORE_FAST               1 (person)
             12 LOAD_FAST                1 (person)
             14 LOAD_ATTR                0 (age)
             34 LOAD_CONST               0 (18)
             36 COMPARE_AND_BRANCH      92 (>=)
             40 POP_JUMP_IF_TRUE         1 (to 44)
             42 JUMP_BACKWARD           19 (to 6)
        >>   44 LOAD_FAST                1 (person)
             46 LIST_APPEND              2
             48 JUMP_BACKWARD           22 (to 6)
        >>   50 END_FOR
             52 RETURN_VALUE
```

```python:for_loop()
 13           0 RESUME                   0

 14           2 BUILD_LIST               0
              4 STORE_FAST               1 (adults)

 16           6 LOAD_FAST                0 (persons)
              8 GET_ITER
        >>   10 FOR_ITER                36 (to 86)
             14 STORE_FAST               2 (person)

 17          16 LOAD_FAST                2 (person)
             18 LOAD_ATTR                0 (age)
             38 LOAD_CONST               1 (18)
             40 COMPARE_AND_BRANCH      92 (>=)
             44 POP_JUMP_IF_TRUE         1 (to 48)
             46 JUMP_BACKWARD           19 (to 10)

 18     >>   48 LOAD_FAST                1 (adults)
             50 LOAD_ATTR                3 (NULL|self + append)
             70 LOAD_FAST                2 (person)
             72 CALL                     1
             82 POP_TOP
             84 JUMP_BACKWARD           38 (to 10)

 16     >>   86 END_FOR

 20          88 LOAD_FAST                1 (adults)
             90 RETURN_VALUE
```
実際にループを回している部分だけを抜き出してみます。
```python:list_comprehension()
        >>    6 FOR_ITER                20 (to 50)
             10 STORE_FAST               1 (person)
             12 LOAD_FAST                1 (person)
             14 LOAD_ATTR                0 (age)
             34 LOAD_CONST               0 (18)
             36 COMPARE_AND_BRANCH      92 (>=)
             40 POP_JUMP_IF_TRUE         1 (to 44)
             42 JUMP_BACKWARD           19 (to 6)
        >>   44 LOAD_FAST                1 (person)   
             46 LIST_APPEND              2
             48 JUMP_BACKWARD           22 (to 6)
        >>   50 END_FOR
```

```python:for_loop()
        >>   10 FOR_ITER                36 (to 86)
             14 STORE_FAST               2 (person)
             16 LOAD_FAST                2 (person)
             18 LOAD_ATTR                0 (age)
             38 LOAD_CONST               1 (18)
             40 COMPARE_AND_BRANCH      92 (>=)
             44 POP_JUMP_IF_TRUE         1 (to 48)
             46 JUMP_BACKWARD           19 (to 10)
        >>   48 LOAD_FAST                1 (adults)
             50 LOAD_ATTR                3 (NULL|self + append)
             70 LOAD_FAST                2 (person)
             72 CALL                     1
             82 POP_TOP
             84 JUMP_BACKWARD           38 (to 10)
        >>   86 END_FOR
```
さらに差分を取り出します。
```python:list_comprehension()
        >>   44 LOAD_FAST                1 (person)   
             46 LIST_APPEND              2
```

```python:for_loop()
        >>   48 LOAD_FAST                1 (adults)
             50 LOAD_ATTR                3 (NULL|self + append)
             70 LOAD_FAST                2 (person)
             72 CALL                     1
             82 POP_TOP
```


主な差は「LIST_APPEND」、「LOAD_FAST/LOAD_ATTR/CALL」という部分です。
（POP_TOPは比較的単純な操作なので支配的な要素とは考えにくいです。）

このバイトコードの差は

- バイトコード命令としてappendを実行
- appendメソッドを呼び出して実行

ということになります。

Pythonではオブジェクトが動的であるため、
呼び出し動作のコストがなかなか重いです。

そのためメソッド呼び出しの有無が如実に実行時間に現れます。

## 内包表記で複雑な事を愚直にやってみる
ここで条件式を複雑にしてみます。
以下のようにお店でお酒を買うときに割引を使える人を抜き出すことを考えてみましょう。

- 飲酒可能である（20歳以上）
- 年齢割引を使える（年齢が3 or 5 or 7の倍数）

```python
ELEMENTS = 2000000  # 2,000,000


class Person:
    def __init__(self, age):
        self.age = age


def list_comprehension(persons):
    return [person for person in persons if person.age >= 20 and (person.age % 3 == 0 or person.age % 5 == 0 or person.age % 7 == 0)]


def for_loop(persons):
    lucky_persons = []

    for person in persons:
        if person.age >= 20 and (person.age % 3 == 0 or person.age % 5 == 0 or person.age % 7 == 0):
            lucky_persons.append(person)

    return lucky_persons


persons = [Person(i) for i in range(ELEMENTS)]

list_comprehension(persons)
for_loop(persons)
```

では実行速度はというと…

 **ncalls** | **tottime** | **percall** | **cumtime** | **percall** | **filename:lineno(function)**                         
------------|-------------|-------------|-------------|-------------|-------------------------------------------------------
 1          | 5.916e-06   | 5.916e-06   | 0.3314      | 0.3314      | speed_test.py:9(list_comprehension)                   
 1          | 0.4162      | 0.4162      | 0.4552      | 0.4552      | speed_test.py:13(for_loop)     

0.4552s / 0.3314s ≒ 1.373倍

だいぶ速度が落ちました。

## 内包表記で複雑な事をやりつつ可読性も担保したい
さらに条件が増えていった場合、非常に読むのが難儀になり始めるので親切な感じにしてみます。
```python
ELEMENTS = 2000000  # 2,000,000


class Person:
    def __init__(self, age):
        self.age = age

    def is_drinkable(self):
        return self.age >= 20

    def is_discountable(self):
        return self.age % 3 == 0 or self.age % 5 == 0 or self.age % 7 == 0


def list_comprehension(persons):
    return [person for person in persons if person.is_drinkable() and person.is_discountable()]


def for_loop(persons):
    lucky_persons = []

    for person in persons:
        if person.is_drinkable() and person.is_discountable():
            lucky_persons.append(person)

    return lucky_persons


persons = [Person(i) for i in range(ELEMENTS)]

list_comprehension(persons)
for_loop(persons)
```
抽象化されて読みやすくなりました。
読みづらい内包表記を見つけた際に多くの人が試す対処方法だと思われます。
この調子ならさらに複雑にしても可読性に問題は出てこなさそうです（？？？？？）

このコードの実行結果を以下に示します。
 **ncalls** | **tottime** | **percall** | **cumtime** | **percall** | **filename:lineno(function)**                         
------------|-------------|-------------|-------------|-------------|-------------------------------------------------------
 1          | 3.319e-06   | 3.319e-06   | 0.8612      | 0.8612      | speed_test.py:15(list_comprehension)                  
 1          | 0.5951      | 0.5951      | 1.046       | 1.046       | speed_test.py:19(for_loop)                            

1.046s / 0.8612s ≒ 1.21倍

少し雲行きが怪しくなり始めました。

## 複雑度をさらに上げてみると？
ではPersonに性別と子供の人数、資産額を追加します。
（様々な値を持つ大量のPersonを生成するのが手間なので、コンストラクタで値を計算させています）
```python
class Person:
    def __init__(self, age, gender, children, assets):
        self.age = age
        self.gender = gender % 2
        self.children = children % 5
        self.assets = assets % 700
```
さらに条件を追加します。

- 母親である(gender == 1 and children > 0)
- 資産が200未満である(assets < 200)

```python
ELEMENTS = 2000000  # 2,000,000


class Person:
    def __init__(self, age, gender, children, assets):
        self.age = age
        self.gender = gender % 2
        self.children = children % 5
        self.assets = assets % 700

    def is_drinkable(self):
        return self.age >= 20

    def is_discountable(self):
        return self.age % 3 == 0 or self.age % 5 == 0 or self.age % 7 == 0

    def is_mother(self):
        return self.gender == 1 and self.children > 0

    def is_poor(self):
        return self.assets < 200


def list_comprehension(persons):
    return [person for person in persons if person.is_drinkable() and person.is_discountable() and person.is_mother() and person.is_poor()]


def for_loop(persons):
    lucky_persons = []

    for person in persons:
        if person.is_drinkable() and person.is_discountable() and person.is_mother() and person.is_poor():
            lucky_persons.append(person)

    return lucky_persons


persons = [Person(i, i, i, i) for i in range(ELEMENTS)]

list_comprehension(persons)
for_loop(persons)
```
そして実行結果は…
 **ncalls** | **tottime** | **percall** | **cumtime** | **percall** | **filename:lineno(function)**                         
------------|-------------|-------------|-------------|-------------|-------------------------------------------------------
 1          | 2.928e-06   | 2.928e-06   | 1.213       | 1.213       | speed_test.py:24(list_comprehension)                  
 1          | 0.7056      | 0.7056      | 1.263       | 1.263       | speed_test.py:28(for_loop)                            

1.263s / 1.213s ≒ 1.04倍


・・・・・

いや、4%速くなってるから！

## さらにコードの抽象度を上げる
前項のコードは横に長くなりすぎたため、該当するpersonをlucky_motherと定義し長ったらしいコードを隠蔽しましょう。

```python
ELEMENTS = 2000000  # 2,000,000


class Person:
    def __init__(self, age, gender, children, assets):
        self.age = age
        self.gender = gender % 2
        self.children = children % 5
        self.assets = assets % 700

    def is_drinkable(self):
        return self.age >= 20

    def is_discountable(self):
        return self.age % 3 == 0 or self.age % 5 == 0 or self.age % 7 == 0

    def is_mother(self):
        return self.gender == 1 and self.children > 0

    def is_poor(self):
        return self.assets < 200

    def is_lucky_mother(self):
        if not self.is_drinkable():
            return False

        if not self.is_discountable():
            return False

        if not self.is_mother():
            return False

        if not self.is_poor():
            return False

        return True


def list_comprehension(persons):
    return [person for person in persons if person.is_lucky_mother()]


def for_loop(persons):
    lucky_mothers = []

    for person in persons:
        if person.is_lucky_mother():
            lucky_mothers.append(person)

    return lucky_mothers


persons = [Person(i, i, i, i) for i in range(ELEMENTS)]

list_comprehension(persons)
for_loop(persons)
```

そして結果は

 **ncalls** | **tottime** | **percall** | **cumtime** | **percall** | **filename:lineno(function)**                         
------------|-------------|-------------|-------------|-------------|-------------------------------------------------------
 1          | 3.02e-06    | 3.02e-06    | 1.332       | 1.332       | speed_test.py:39(list_comprehension)                  
 1          | 0.2562      | 0.2562      | 1.347       | 1.347       | speed_test.py:43(for_loop)                            

1.347s / 1.332s ≒ 1.01倍

・・・・・・・・・・

ほぼ誤差といえる範囲にまで速度が低下してしまいました。
明らかに内包表記からis_lucky_motherを中継して条件メソッドを呼び出しているのが響いています。

## 内包表記の優位性を保ちたい
簡単に言うとメソッドの読み込み（厳密にはcallableなオブジェクトの読み込み）を減らせば、
本文で述べた優位性が薄れる現象を抑制することが可能となります。

書いてあることは単純なのですが、実際のところかなりキツイ制約であると思われます。


## 結論
以下のことが判明しました。

- for文と内包表記には毎ループごとにメソッドの読み込みが1回あるかないかの違いくらいしかない

- 内包表記により得られたメソッド読み込み1回分のアドバンテージが支配的でない場合、
内包表記の恩恵は薄れていく

- 実行速度を上げたいのであれば内包表記内でcallableなオブジェクトを呼ばない
（恩恵を受けるために呼べないとも言える）

これらから以下の事柄を述べることができます。

- 大真面目に速度最適化を複雑な処理を行う内包表記に対して行うと可読性が恐ろしいことになる

- 可読性を確保するためにある程度の粒度で処理を関数化すると呼び出しコストが積み上がってしまい優位性を失う

以上より

**「複雑な処理をわざわざ内包表記で行う意味はほぼ無い」**

と結論づけられます。

## 感想
可読性を投げ捨てた先に得られる対価が小さすぎます。
何でもかんでも速度を理由にして内包表記にするのはやめた方が良さそうです。

~~しかし対話モードでの利用は書きやすさという観点からアリだと思います。
ただし書き捨てのコードに限ります。~~（追記内容より打消し）


## 追記
ツイッターでの反応を観察したところfor文と内包表記のどちらを平易と感じるのかは、
その人物の学問的背景が関係しているような気がしています。
    
可読性に関して
- 「万人が読める」
- 「数学における内包的記法的に記述できるので簡潔」

の二方向があると考えられそうです。
    
メンバー間で数学的素養が共有できているのであれば、
可読性の確保のために内包表記を使用するという選択が考えられるのかもしれません。