3

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

4 件の回答 4

3

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

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

リストの長さは

  • 1000000000
  • 1000

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

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


len()を使う方法

def is_len_1(lst):
    if len(lst) == 1:
        return True
    return False

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

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

素直に数える方法

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

計測に使用したコード

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)

実行結果

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
2

len(s)の結果が 1 かどうかで判定すれば良いでしょう。

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

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


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

こんな記事を読んだ記憶から回答していました。
Pythonはどうやってlen関数で長さを手にいれているの?
【Python入門】クラス利用時の特殊メソッド一覧(サンプルコード付き)

2

@oriri 氏の回答is_len_1() 関数を以下に変更して計測。

def is_len_1(lst):
    return len(lst) == 1

perf
以下、disassemble の結果

>>> 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
1
  • is_len_1 が速いと思えるのになぜ 2番手なんだろうと考えてましたが放置してました。disassembleという手段がありましたね
    – oriri
    Commented 2022年5月8日 2:56
2

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

更新 (is_len_1b 追加)

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")

パフォーマンス図


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

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

(ちなみに, 関数型言語等で言う list (linked list) は Pythonでは deque に相当)

1
  • is_len_1b 追加してみて, 確かに is_len_1 より速いものの, colab(の Python)では順位変わらず
    – oriri
    Commented 2022年5月8日 9:43

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

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