Pythonのリスト型の長さが1かどうかを高速に判定する方法はありますか.
4 件の回答
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
len(s)の結果が 1 かどうかで判定すれば良いでしょう。
オブジェクトの長さ (要素の数) を返します。引数はシーケンス (文字列、バイト列、タプル、リスト、range 等) かコレクション (辞書、集合、凍結集合等) です。
むしろそれ以外の簡潔な方法があるが比較する方法があるかとか、この方法でやっているがどうも遅いように見えるといった情報があるのなら、それを追記してもらった方が話題が広がって、何かちょっとした知見が集まるかもしれません。
他の人のように、長大なリストの時にどうなるかとかは考えていませんでしたね。
@oriri さん回答のグラフを見ると、よく使うリストの長さが何かによって使い分けるというのが正解でしょうか。
こんな記事を読んだ記憶から回答していました。
Pythonはどうやってlen関数で長さを手にいれているの?
【Python入門】クラス利用時の特殊メソッド一覧(サンプルコード付き)
@oriri 氏の回答 の is_len_1()
関数を以下に変更して計測。
def is_len_1(lst):
return len(lst) == 1
>>> 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
これは直接の回答コードではなく, 別解のコードのグラフ化です。
図は 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 に相当)