Python で (x == y or x == z) や x in (y, z) の速度比較
Python で a in container (多要素) とするときは container は set や dict にすると速い。
a in (1, 2, 3, 4) くらいまではどうなのか？
以下の比較コードでは次のものを生成して実行時間を測定してみます。要素数は変化します。int 同士の比較。
- a == b を or 連結
- 毎回タプルを生成して a in (b, c)
- ローカル変数に入れたタプルで a in tuple_
- 毎回setを生成して a in {b, c}
- ローカル変数に入れた set で a in set_
- 毎回dictを生成して a in {b: None, c: None}
- ローカル変数に入れた dict で a in dict_
一致した位置で判定は終了するため、一致する位置をずらして測定しています。set や dict では位置は関係なし。
from timeit import timeit import sys def print_result(j, res): m = min(res) print("%s " % j + ", ".join(["%.4f" % i for i in res])) print("%s " % " " + ", ".join(["(%.2f)" % (i/m) for i in res])) def main(n): print("N or tuple ctuple set cset dict cdict") num = 5000000 data = [] for j in range(n): values = list(map(str, range(9, 9+n))) values[j] = "1" s = "a = 1; " + "; ".join(["%s = %s" % (chr(ord("b")+v), i) for v, i in zip(range(n), values)]) s += "; q = (%s)" % ", ".join(values) s += "; p = {%s}" % ", ".join(values) s += "; r = {%s}" % ", ".join(["%s: None" % v for v in values]) a = timeit(" or ".join(["a == %s" % chr(ord("b")+v) for v in range(n)]), setup=s, number=num) b = timeit("a in (%s)" % ", ".join(values), setup=s, number=num) c = timeit("a in q", setup=s, number=num) d = timeit("a in {%s}" % ", ".join(values), setup=s, number=num) e = timeit("a in p", setup=s, number=num) f = timeit("a in {%s}" % ", ".join(["%s: None" % v for v in values]), setup=s, number=num) g = timeit("a in r", setup=s, number=num) res = (a, b, c, d, e, f, g) print_result(j, res) data.append(res) average = [sum(v)/n for v in zip(*data)] print_result("a", average) def hoge(m_): print("Python " + sys.version[0:5]) print("N: matched position") print("c prefix means cashed") for i_ in range(2, m_+2): main(i_) hoge(3)
結果
Python 2.7.6, 3.3.6, 3.4.3, 3.5.0 で実行してみた。
N: 一致する要素の位置
c から始まっている項目はローカル変数にキャッシュ
a: 平均値、検索値 a が一様に分布していると仮定
(カッコ内): 実行時間最小を 1.00 として算出した比率
Python 3.3.6 N: matched position c prefix means cashed N or tuple ctuple set cset dict cdict 0 0.1383, 0.1163, 0.1108, 0.1402, 0.1384, 0.6567, 0.1386 (1.25), (1.05), (1.00), (1.27), (1.25), (5.93), (1.25) 1 0.2490, 0.2019, 0.1993, 0.1460, 0.1404, 0.6747, 0.1472 (1.77), (1.44), (1.42), (1.04), (1.00), (4.81), (1.05) a 0.1936, 0.1591, 0.1550, 0.1431, 0.1394, 0.6657, 0.1429 (1.39), (1.14), (1.11), (1.03), (1.00), (4.78), (1.03) N or tuple ctuple set cset dict cdict 0 0.1389, 0.1157, 0.1113, 0.1415, 0.1396, 0.8662, 0.1394 (1.25), (1.04), (1.00), (1.27), (1.25), (7.78), (1.25) 1 0.2608, 0.2027, 0.1977, 0.1474, 0.1421, 0.7734, 0.1445 (1.84), (1.43), (1.39), (1.04), (1.00), (5.44), (1.02) 2 0.3624, 0.2825, 0.2774, 0.1483, 0.1374, 0.7756, 0.1446 (2.64), (2.06), (2.02), (1.08), (1.00), (5.64), (1.05) a 0.2540, 0.2003, 0.1955, 0.1457, 0.1397, 0.8051, 0.1428 (1.82), (1.43), (1.40), (1.04), (1.00), (5.76), (1.02) N or tuple ctuple set cset dict cdict 0 0.1406, 0.1160, 0.1120, 0.1379, 0.1401, 0.9427, 0.1409 (1.26), (1.04), (1.00), (1.23), (1.25), (8.42), (1.26) 1 0.2631, 0.2040, 0.1993, 0.1480, 0.1378, 0.9755, 0.1439 (1.91), (1.48), (1.45), (1.07), (1.00), (7.08), (1.04) 2 0.4637, 0.2869, 0.2828, 0.1472, 0.1415, 0.9874, 0.1483 (3.28), (2.03), (2.00), (1.04), (1.00), (6.98), (1.05) 3 0.4784, 0.3557, 0.3485, 0.1479, 0.1383, 0.8859, 0.1441 (3.46), (2.57), (2.52), (1.07), (1.00), (6.41), (1.04) a 0.3365, 0.2407, 0.2356, 0.1453, 0.1394, 0.9479, 0.1443 (2.41), (1.73), (1.69), (1.04), (1.00), (6.80), (1.04) ---- Python 3.4.3 N: matched position c prefix means cashed N or tuple ctuple set cset dict cdict 0 0.1390, 0.1177, 0.1237, 0.1491, 0.1544, 0.6684, 0.1396 (1.18), (1.00), (1.05), (1.27), (1.31), (5.68), (1.19) 1 0.2334, 0.1931, 0.1934, 0.1564, 0.1553, 0.6858, 0.1485 (1.57), (1.30), (1.30), (1.05), (1.05), (4.62), (1.00) a 0.1862, 0.1554, 0.1586, 0.1528, 0.1549, 0.6771, 0.1440 (1.29), (1.08), (1.10), (1.06), (1.08), (4.70), (1.00) N or tuple ctuple set cset dict cdict 0 0.1395, 0.1183, 0.1227, 0.1497, 0.1540, 0.8918, 0.1411 (1.18), (1.00), (1.04), (1.27), (1.30), (7.54), (1.19) 1 0.2447, 0.1941, 0.1930, 0.1575, 0.1568, 0.7925, 0.1507 (1.62), (1.29), (1.28), (1.04), (1.04), (5.26), (1.00) 2 0.3364, 0.2702, 0.2734, 0.1626, 0.1549, 0.7818, 0.1492 (2.25), (1.81), (1.83), (1.09), (1.04), (5.24), (1.00) a 0.2402, 0.1942, 0.1964, 0.1566, 0.1552, 0.8221, 0.1470 (1.63), (1.32), (1.34), (1.07), (1.06), (5.59), (1.00) N or tuple ctuple set cset dict cdict 0 0.1389, 0.1181, 0.1228, 0.1496, 0.1546, 0.9457, 0.1411 (1.18), (1.00), (1.04), (1.27), (1.31), (8.01), (1.19) 1 0.2444, 0.1926, 0.1939, 0.1570, 0.1549, 1.0003, 0.1478 (1.65), (1.30), (1.31), (1.06), (1.05), (6.77), (1.00) 2 0.3476, 0.2692, 0.2733, 0.1626, 0.1551, 1.0076, 0.1473 (2.36), (1.83), (1.86), (1.10), (1.05), (6.84), (1.00) 3 0.4357, 0.3481, 0.3518, 0.1720, 0.1543, 0.8817, 0.1479 (2.95), (2.35), (2.38), (1.16), (1.04), (5.96), (1.00) a 0.2916, 0.2320, 0.2354, 0.1603, 0.1547, 0.9588, 0.1460 (2.00), (1.59), (1.61), (1.10), (1.06), (6.57), (1.00) ---- Python 3.5.0 N: matched position c prefix means cashed N or tuple ctuple set cset dict cdict 0 0.1330, 0.1100, 0.1092, 0.1390, 0.1401, 0.7052, 0.1395 (1.22), (1.01), (1.00), (1.27), (1.28), (6.46), (1.28) 1 0.2223, 0.1827, 0.1812, 0.1480, 0.1480, 0.7759, 0.1583 (1.50), (1.23), (1.22), (1.00), (1.00), (5.24), (1.07) a 0.1776, 0.1463, 0.1452, 0.1435, 0.1440, 0.7405, 0.1489 (1.24), (1.02), (1.01), (1.00), (1.00), (5.16), (1.04) N or tuple ctuple set cset dict cdict 0 0.1439, 0.1179, 0.1187, 0.1531, 0.1408, 0.8054, 0.1395 (1.22), (1.00), (1.01), (1.30), (1.19), (6.83), (1.18) 1 0.2367, 0.1847, 0.1826, 0.1528, 0.1541, 0.8385, 0.1450 (1.63), (1.27), (1.26), (1.05), (1.06), (5.78), (1.00) 2 0.3254, 0.2487, 0.2489, 0.1509, 0.1418, 0.8282, 0.1444 (2.29), (1.75), (1.75), (1.06), (1.00), (5.84), (1.02) a 0.2353, 0.1838, 0.1834, 0.1522, 0.1456, 0.8240, 0.1430 (1.65), (1.29), (1.28), (1.06), (1.02), (5.76), (1.00) N or tuple ctuple set cset dict cdict 0 0.1382, 0.1093, 0.1090, 0.1401, 0.1409, 0.9625, 0.1391 (1.27), (1.00), (1.00), (1.29), (1.29), (8.83), (1.28) 1 0.2331, 0.1838, 0.1831, 0.1486, 0.1398, 0.9741, 0.1455 (1.67), (1.31), (1.31), (1.06), (1.00), (6.97), (1.04) 2 0.3350, 0.2513, 0.2478, 0.1489, 0.1418, 0.9747, 0.1447 (2.36), (1.77), (1.75), (1.05), (1.00), (6.87), (1.02) 3 0.4325, 0.3154, 0.3143, 0.1492, 0.1400, 0.9125, 0.1453 (3.09), (2.25), (2.25), (1.07), (1.00), (6.52), (1.04) a 0.2847, 0.2150, 0.2136, 0.1467, 0.1406, 0.9560, 0.1437 (2.02), (1.53), (1.52), (1.04), (1.00), (6.80), (1.02) ---- Python 2.7.6 N: matched position c prefix means cashed N or tuple ctuple set cset dict cdict 0 0.1176, 0.1164, 0.1139, 0.4014, 0.1471, 0.4633, 0.1349 (1.03), (1.02), (1.00), (3.52), (1.29), (4.07), (1.18) 1 0.1727, 0.1434, 0.1424, 0.4276, 0.1463, 0.4979, 0.1387 (1.24), (1.03), (1.03), (3.08), (1.05), (3.59), (1.00) a 0.1451, 0.1299, 0.1281, 0.4145, 0.1467, 0.4806, 0.1368 (1.13), (1.01), (1.00), (3.23), (1.14), (3.75), (1.07) N or tuple ctuple set cset dict cdict 0 0.1174, 0.1161, 0.1143, 0.4669, 0.1460, 0.6638, 0.1346 (1.03), (1.02), (1.00), (4.08), (1.28), (5.81), (1.18) 1 0.1850, 0.1433, 0.1423, 0.4929, 0.1461, 0.6043, 0.1373 (1.35), (1.04), (1.04), (3.59), (1.06), (4.40), (1.00) 2 0.2394, 0.1688, 0.1669, 0.4915, 0.1460, 0.5984, 0.1372 (1.74), (1.23), (1.22), (3.58), (1.06), (4.36), (1.00) a 0.1806, 0.1428, 0.1412, 0.4838, 0.1460, 0.6222, 0.1364 (1.32), (1.05), (1.04), (3.55), (1.07), (4.56), (1.00) N or tuple ctuple set cset dict cdict 0 0.1176, 0.1168, 0.1141, 0.5351, 0.1462, 0.7202, 0.1347 (1.03), (1.02), (1.00), (4.69), (1.28), (6.31), (1.18) 1 0.1841, 0.1452, 0.1447, 0.5580, 0.1467, 0.8063, 0.1374 (1.34), (1.06), (1.05), (4.06), (1.07), (5.87), (1.00) 2 0.2520, 0.1686, 0.1669, 0.5547, 0.1466, 0.8005, 0.1379 (1.83), (1.22), (1.21), (4.02), (1.06), (5.80), (1.00) 3 0.3072, 0.1941, 0.1957, 0.5554, 0.1457, 0.7106, 0.1376 (2.23), (1.41), (1.42), (4.04), (1.06), (5.17), (1.00) a 0.2152, 0.1562, 0.1554, 0.5508, 0.1463, 0.7594, 0.1369 (1.57), (1.14), (1.13), (4.02), (1.07), (5.55), (1.00)
考察
検索する値が均一に分布していると仮定。
M: 合計要素数
- dict を毎回生成するとどのバージョンでも遅い。2.7.6 では set の生成も遅い。しかし、キャッシュしておくのであればどのバージョンでも速い。
- a == b or ... は変数のルックアップのせいか遅い。3.X では一つ目で一致した場合でも遅い？
- 2.7.6, M = 2:
