88689


Pythonのリスト型の長さが1かどうかを高速に判定する方法はありますか．


CC BY-SA 4.0
2022-05-07T09:35:53.930
88687
2022-05-08T09:41:35.120
51374
question
python python3
シーケンスの長さが1かどうかの判定


[len(s)](https://docs.python.org/ja/3.10/library/functions.html#len)の結果が 1
かどうかで判定すれば良いでしょう。

> オブジェクトの長さ (要素の数) を返します。引数はシーケンス (文字列、バイト列、タプル、リスト、range 等) かコレクション
> (辞書、集合、凍結集合等) です。

むしろそれ以外の簡潔な方法があるが比較する方法があるかとか、この方法でやっているがどうも遅いように見えるといった情報があるのなら、それを追記してもらった方が話題が広がって、何かちょっとした知見が集まるかもしれません。

* * *

他の人のように、長大なリストの時にどうなるかとかは考えていませんでしたね。  
@oriri さん回答のグラフを見ると、よく使うリストの長さが何かによって使い分けるというのが正解でしょうか。

こんな記事を読んだ記憶から回答していました。  
[Pythonはどうやってlen関数で長さを手にいれているの？](https://www.slideshare.net/shimizukawa/how-
does-python-get-the-length-with-the-len-function)  
[【Python入門】クラス利用時の特殊メソッド一覧（サンプルコード付き）](https://blog.codecamp.jp/python-class-
code)


CC BY-SA 4.0
2022-05-07T10:12:24.890
88688
2022-05-07T14:29:52.180
2022-05-07T14:29:52.180
26370
26370
88687
answer


len()がリストの要素を最後まで数え上げているのであれば、要素数が多いリストの場合、もっと速い方法があるのではないかと考え、次の３つの方法で実測してみました。

  * len()を使う方法
  * インデックスの範囲外の例外で判定する方法(要素数0、1，2で判定）
  * 素直に数える方法(要素数0、1，2で判定）

リストの長さは

  * 1000000000
  * 1000

それぞれの方法を10000000回実行した時間を10回計測

ばらつきはありますがlen()は十分速かったです。  
len()はリストの要素を最後まで数え上げているわけではなさそうです。

* * *

**len()を使う方法**

[code]

    def is_len_1(lst):
        if len(lst) == 1:
            return True
        return False
    
[/code]

**インデックスの範囲外の例外で判定する方法**

[code]

        try:
            lst[0]
            try:
                lst[1]
                return False
            except:
                return True
        except:
            return False
    
[/code]

**素直に数える方法**

[code]

        count = 0
        for d in lst:
            count += 1
            if count >= 2:
                return False
        if count == 1:
            return True
        return False
    
[/code]

* * *

**計測に使用したコード**

[code]

    def is_len_1(lst):
        if len(lst) == 1:
            return True
        return False
    
    def is_len_2(lst):
        try:
            lst[0]
            try:
                lst[1]
                return False
            except:
                return True
        except:
            return False
    
    def is_len_3(lst):
        count = 0
        for d in lst:
            count += 1
            if count >= 2:
                return False
        if count == 1:
            return True
        return False
    
    def nop(ldt):
        return True
    
    def stop_watch(title, loop_num, func, lst):
        import time
        print(title, end=" ")
        start = time.time()
        for i in range(loop_num):
            func(lst)
            end = time.time()
        print(end-start)
    
    print(is_len_1([1,2]))
    print(is_len_1([1]))
    print(is_len_1([]))
    print("========================")
    print(is_len_2([1,2]))
    print(is_len_2([1]))
    print(is_len_2([]))
    print("========================")
    print(is_len_3([1,2]))
    print(is_len_3([1]))
    print(is_len_3([]))
    print("========================")
    
    loop_num = 10000000
    for element_num in [1000, 1000000000]:
        data = [0]*element_num
        print("len = ", len(data))
        print("loop_num = ", loop_num)
    
        print("========================")
    
        for i in range(10):
            print("element_num = ", element_num)
            stop_watch(str(i) + ":is_len_1", loop_num, is_len_1, data)
            stop_watch(str(i) + ":is_len_2", loop_num, is_len_2, data)
            stop_watch(str(i) + ":is_len_3", loop_num, is_len_3, data)
            stop_watch(str(i) + ":nop     ", loop_num, nop, data)
    
[/code]

**実行結果**

[code]

    Python 3.10.4 (tags/v3.10.4:9d38120, Mar 23 2022, 23:13:41) [MSC v.1929 64 bit (AMD64)] on win32
    Type "help", "copyright", "credits" or "license()" for more information.
    
    ========================= RESTART: D:/PytonIdle/p016.py ========================
    False
    True
    False
    ========================
    False
    True
    False
    ========================
    False
    True
    False
    ========================
    len =  1000
    loop_num =  10000000
    ========================
    element_num =  1000
    0:is_len_1 3.1604654788970947
    0:is_len_2 3.9410452842712402
    0:is_len_3 4.230916500091553
    0:nop      2.1160919666290283
    element_num =  1000
    1:is_len_1 3.1215078830718994
    1:is_len_2 4.397623538970947
    1:is_len_3 4.885829210281372
    1:nop      2.1927695274353027
    element_num =  1000
    2:is_len_1 3.5610873699188232
    2:is_len_2 3.391345262527466
    2:is_len_3 4.507924795150757
    2:nop      2.164076805114746
    element_num =  1000
    3:is_len_1 3.3902783393859863
    3:is_len_2 3.3306689262390137
    3:is_len_3 4.700424909591675
    3:nop      2.1587724685668945
    element_num =  1000
    4:is_len_1 3.697195529937744
    4:is_len_2 3.238907814025879
    4:is_len_3 4.419464111328125
    4:nop      2.1661248207092285
    element_num =  1000
    5:is_len_1 3.6382806301116943
    5:is_len_2 3.216294765472412
    5:is_len_3 4.436988115310669
    5:nop      2.112088441848755
    element_num =  1000
    6:is_len_1 3.682610511779785
    6:is_len_2 3.2686824798583984
    6:is_len_3 4.43172812461853
    6:nop      2.1496691703796387
    element_num =  1000
    7:is_len_1 3.5153136253356934
    7:is_len_2 3.1987204551696777
    7:is_len_3 4.494958400726318
    7:nop      2.177074670791626
    element_num =  1000
    8:is_len_1 3.7260661125183105
    8:is_len_2 3.210592031478882
    8:is_len_3 4.66589617729187
    8:nop      2.1760706901550293
    element_num =  1000
    9:is_len_1 3.565033197402954
    9:is_len_2 3.2537665367126465
    9:is_len_3 4.366029977798462
    9:nop      2.5824732780456543
    len =  1000000000
    loop_num =  10000000
    ========================
    element_num =  1000000000
    0:is_len_1 4.4968390464782715
    0:is_len_2 3.2307748794555664
    0:is_len_3 5.194000244140625
    0:nop      2.3175928592681885
    element_num =  1000000000
    1:is_len_1 3.1254608631134033
    1:is_len_2 3.3514931201934814
    1:is_len_3 5.682132959365845
    1:nop      2.3058834075927734
    element_num =  1000000000
    2:is_len_1 3.0752758979797363
    2:is_len_2 3.4806466102600098
    2:is_len_3 4.925281763076782
    2:nop      2.1791114807128906
    element_num =  1000000000
    3:is_len_1 3.2901103496551514
    3:is_len_2 3.339263439178467
    3:is_len_3 5.119615077972412
    3:nop      2.1325082778930664
    element_num =  1000000000
    4:is_len_1 3.010546922683716
    4:is_len_2 3.2905783653259277
    4:is_len_3 5.1084935665130615
    4:nop      2.1824588775634766
    element_num =  1000000000
    5:is_len_1 2.983994722366333
    5:is_len_2 3.3312129974365234
    5:is_len_3 5.220165491104126
    5:nop      3.7988028526306152
    element_num =  1000000000
    6:is_len_1 3.1995973587036133
    6:is_len_2 4.501703500747681
    6:is_len_3 4.627080202102661
    6:nop      2.1670310497283936
    element_num =  1000000000
    7:is_len_1 4.038714170455933
    7:is_len_2 3.7357866764068604
    7:is_len_3 5.944887638092041
    7:nop      3.014718532562256
    element_num =  1000000000
    8:is_len_1 3.656972646713257
    8:is_len_2 3.2459990978240967
    8:is_len_3 4.4823832511901855
    8:nop      2.2680044174194336
    element_num =  1000000000
    9:is_len_1 3.6379356384277344
    9:is_len_2 3.1247572898864746
    9:is_len_3 5.247612476348877
    9:nop      2.6033103466033936
    
[/code]


CC BY-SA 4.0
2022-05-07T12:24:00.867
88689
2022-05-07T12:24:00.867
35558
88687
answer


これは直接の回答コードではなく, 別解のコードのグラフ化です。  
図は colabでの結果であり, Pythonのバージョンによっては多少変動があるかも。

**更新** (`is_len_1b` 追加)

[code]

    def is_len_1(lst):
        if len(lst) == 1:
            return True
        return False
    
    def is_len_1b(lst):
        return len(lst) == 1
    
    def try_except(lst):
        try:
            lst[0]
            try:
                lst[1]
                return False
            except:
                return True
        except:
            return False
    
    def countup(lst):
        count = 0
        for d in lst:
            count += 1
            if count >= 2:
                return False
        if count == 1:
            return True
        return False
    
    
    !pip install perfplot
    import perfplot
    
    out = perfplot.bench(
        setup=lambda n: [0] *n,
        n_range=[2**k for k in range(24)],
        kernels=[
            is_len_1,
            is_len_1b,
            try_except,
            countup,
        ],
        equality_check=lambda r1, r2: r1 == r2,
        xlabel="len(x)",
    )
    out.show()
    out.save("perf.png", transparent=True, bbox_inches="tight")
    
[/code]

[![パフォーマンス図](https://i.stack.imgur.com/mSEw4.png)](https://i.stack.imgur.com/mSEw4.png)

* * *

Pythonの listは, "dynamic array" と呼ばれる 動的にサイズが変動する arrayです。  
(確保する時に多少の余裕を見て生成されていて, その限界が来たら再配置)  
(CPythonだけなのか, Python系すべてなのかは分からない)

なので listの最後に項目追加・削除するのは高速だけど, listの先頭に項目追加・先頭から削除すると遅いというデメリットがあります。  
その点も含め, 普通に配列として考えてよいかも。

(ちなみに, 関数型言語等で言う list (linked list) は Pythonでは
[deque](https://docs.python.org/ja/3/library/collections.html#deque-objects)
に相当)


CC BY-SA 4.0
2022-05-07T14:17:38.737
88691
2022-05-08T09:41:35.120
2022-05-08T09:41:35.120
43025
43025
88687
answer


[@oriri 氏の回答](https://ja.stackoverflow.com/a/88691/47127) の `is_len_1()`
関数を以下に変更して計測。

[code]

    def is_len_1(lst):
        return len(lst) == 1
    
[/code]

[![perf](https://i.stack.imgur.com/rj5MY.png)](https://i.stack.imgur.com/rj5MY.png)  
以下、disassemble の結果

[code]

    >>> from dis import dis
    >>> def is_len_1(lst):
            if len(lst) == 1:
                return True
            return False
    
    >>> dis(is_len_1)
      2           0 LOAD_GLOBAL              0 (len)
                  2 LOAD_FAST                0 (lst)
                  4 CALL_FUNCTION            1
                  6 LOAD_CONST               1 (1)
                  8 COMPARE_OP               2 (==)
                 10 POP_JUMP_IF_FALSE        8 (to 16)
    
      3          12 LOAD_CONST               2 (True)
                 14 RETURN_VALUE
    
      4     >>   16 LOAD_CONST               3 (False)
                 18 RETURN_VALUE
    
    >>> def is_len_1b(lst):
            return len(lst) == 1
    
    >>> dis(is_len_1b)
      2           0 LOAD_GLOBAL              0 (len)
                  2 LOAD_FAST                0 (lst)
                  4 CALL_FUNCTION            1
                  6 LOAD_CONST               1 (1)
                  8 COMPARE_OP               2 (==)
                 10 RETURN_VALUE
    
[/code]


CC BY-SA 4.0
2022-05-08T01:19:12.130
88694
2022-05-08T01:19:12.130
47127
88687
answer