LoginSignup
1
1

More than 1 year has passed since last update.

@k_sui_14

[Python]データ型ごとのO(1)の処理時間の実測

Posted at

はじめに

今までは基本的に計算量至上主義的な考え方で定数倍の計算量はあまり意識してこなかったのですが、先日のAtCoder Beginner Contest 289に参加した際に表題の影響でTLEを出してしまったため、実測してみました。
ちなみにその内容としては、一番計算量の大きいループ内での処理の中で、見つかった値を記憶しておいて最後に１つずつ取り出して処理する、という処理で、listでいいところをsetで実装した結果、TLEになりました。

測定内容

測定は全てAtCoderのコードテスト上のPyPyで行いました。
AtCoderでよく使うlist、set、deque、defaultdictを対象に、要素の追加・取り出し処理に要する時間を計測しました。
要素の追加はそれぞれ以下のような形で行っています。

test_list.append(i)  # list
test_set.add(i)      # set
test_que.append(i)   # deque
test_dict[i] += 1    # defaultdict

要素の取り出しについては、それぞれのデータ型から1つずつ値を取り出し、変数に格納する、という処理になっています。
(最後にソースコードを載せています。)

測定パターン

1ループあたりの追加回数別に、合計10^7回の追加処理を行うように以下のパターンを実施しました。

  • １ループあたり$10^2$回、$10^5$ループ
  • １ループあたり$10^3$回、$10^4$ループ
  • １ループあたり$10^4$回、$10^3$ループ
  • １ループあたり$10^5$回、$10^2$ループ
  • １ループあたり$10^6$回、$10$ループ
  • １ループあたり$10^7$回、$1$ループ

測定結果

以下、追加処理、取り出し処理、合計の測定結果をそれぞれ記載します。単位は秒です。
それぞれ、合計の処理回数を同じにした場合の時間を載せているので、たとえばデータ数10^6の場合は、表に記載の秒数の1/10が全データを扱うのにかかった時間です。

追加

データ数 / ループ回数 list set duque defaultdict
$10^2$ / $10^5$ 0.0546 0.2081 0.0592 0.3971
$10^3$ / $10^4$ 0.0826 0.2200 0.0451 0.4076
$10^4$ / $10^3$ 0.0833 0.2751 0.0502 0.5740
$10^5$ / $10^2$ 0.3921 0.3776 0.0625 0.6706
$10^6$ / $10$ 0.2569 0.4931 0.2606 1.0970
$10^7$ / $1$ 0.4787 0.9708 0.2829 1.8448

取り出し

データ数 / ループ回数 list set duque defaultdict
$10^2$ / $10^5$ 0.0181 0.0426 0.0258 0.1086
$10^3$ / $10^4$ 0.0141 0.0349 0.0211 0.1027
$10^4$ / $10^3$ 0.0128 0.0344 0.0271 0.1082
$10^5$ / $10^2$ 0.0138 0.0340 0.0295 0.1050
$10^6$ / $10$ 0.0135 0.0362 0.0383 0.1026
$10^7$ / $1$ 0.0161 0.0342 0.0412 0.1096

合計

データ数 / ループ回数 list set duque defaultdict
$10^2$ / $10^5$ 0.0726 0.2507 0.0850 0.5057
$10^3$ / $10^4$ 0.0967 0.2549 0.0662 0.5103
$10^4$ / $10^3$ 0.0961 0.3095 0.0773 0.6822
$10^5$ / $10^2$ 0.4059 0.4116 0.0920 0.7756
$10^6$ / $10$ 0.2703 0.5293 0.2990 1.1996
$10^7$ / $1$ 0.4948 1.0050 0.3241 1.9544

コメント

listとset

想定どおりsetの方が遅いです。
ただ、最大のデータ数が$10^5$程度になる場合はほぼ拮抗しており、何度か計測しても同じ結果になりました。
データ数が$10^7$に近い場合は、setを使うと危険そうです。

listとdeque

listとdequeについては基本的にはdequeの方が速そうです。特に$10^5$については顕著です。
ただ、10^6の時はlistの方が速くなっており、こちらも何度か計測しましたが同じ結果でした。
ベストを求めるのであればシーケンシャルな(もしくは順番を問わない)アクセスしか求めない場合はdequeを使った方が良さそうですが、
記述量は若干増えてしまうため、そこまでする必要はないのではないかと思います。
データ量が$10^7$に近い場合には後述するlistをあらかじめ確保しておくやり方にした方が良いと思います。

defaultdict

イメージ通りですがdefaultdictは遅いですね。
O(1)とはいえ$10^7$程度のデータを扱う場合には問題が起こる場合がありそうです。
でも$10^6$程度のデータ量であれば１ループあたり約0.12秒程度なので、ギリギリのデータ量でない場合は気にする必要はなさそうです。

データ数が小さい場合の測定結果

基本的にデータ数が多いほど所要時間が長くなっていますが、データ数が$10^2$の場合は他よりも遅い場合があります。
これについては時間の計測に使うtime.time()の処理時間がオーバーヘッドになっているのではないかと思います。

追加測定: listを初めから確保した場合。

書き終わったあたりで、listを最初から要素分確保しておけばもっと早いのではないかと思ったので追加調査した結果です。
appendで適宜追加した場合との比較です。

追加

データ数 / ループ回数 最初から確保 appendで追加
$10^2$ / $10^5$ 0.019407 0.044225
$10^3$ / $10^4$ 0.013540 0.072752
$10^4$ / $10^3$ 0.015636 0.085061
$10^5$ / $10^2$ 0.015330 0.215493
$10^6$ / $10$ 0.017440 0.234186
$10^7$ / $1$ 0.016548 0.466276

取り出し

データ数 / ループ回数 最初から確保 appendで追加
$10^2$ / $10^5$ 0.025059 0.017111
$10^3$ / $10^4$ 0.020142 0.012345
$10^4$ / $10^3$ 0.015201 0.013765
$10^5$ / $10^2$ 0.013769 0.011647
$10^6$ / $10$ 0.015067 0.011965
$10^7$ / $1$ 0.013946 0.013563

合計

データ数 / ループ回数 最初から確保 appendで追加
$10^2$ / $10^5$ 0.044467 0.061336
$10^3$ / $10^4$ 0.033682 0.085097
$10^4$ / $10^3$ 0.030837 0.098826
$10^5$ / $10^2$ 0.029099 0.227140
$10^6$ / $10$ 0.032507 0.246151
$10^7$ / $1$ 0.030494 0.479839

コメント

予想通り非常に速く、データ数によらず同程度の処理時間となっていました。
ただ、この実装の場合はコードがdequeよりもさらに煩雑になってしまうので、データ量が$10^7$に近い場合に処理が追いつかない場合の最終手段として頭に入れておくといいのかなと思います。

まとめ

  • 格納するデータ数が$10^6$程度までであれば基本的にどのデータ型でもボトルネックになることは無さそう。
  • $10^7$程度になるのであればsetは注意が必要。defaultdictは危険。
  • 計算量的には問題ないはずなのに特定のデータだけTLEする、という場合の微調整には、listを最初から確保する方法を試す価値はありそう。

計測に使用したコード

各データ型の比較

import time
from collections import deque, defaultdict

total_loop = 10**7
sizes = [10**i for i in range(8)]

add_result = []
pop_result = []
sum_result = []

# これを変えて試す
SIZE_IDX = 2
data_size = sizes[SIZE_IDX]

count = total_loop // data_size
print('data num:{}  loop count:{}'.format(data_size, count))
title = '{} / {}'.format(data_size, count)
add_result.append(title)
pop_result.append(title)
sum_result.append(title)

add_time_sum = 0
pop_time_sum = 0
for i in range(count):
    test_list = list()
    start = time.time()
    for j in range(data_size):
        test_list.append(j)
    add_time_sum += time.time()-start
    start = time.time()
    for d in test_list:
        tmp = d
    pop_time_sum += time.time()-start
add_result.append('{:.4f}'.format(add_time_sum))
pop_result.append('{:.4f}'.format(pop_time_sum))
sum_result.append('{:.4f}'.format(add_time_sum + pop_time_sum))

add_time_sum = 0
pop_time_sum = 0
for i in range(count):
    test_set = set()
    start = time.time()
    for j in range(data_size):
        test_set.add(j)
    add_time_sum += time.time()-start
    start = time.time()
    for d in test_set:
        tmp = d
    pop_time_sum += time.time()-start
add_result.append('{:.4f}'.format(add_time_sum))
pop_result.append('{:.4f}'.format(pop_time_sum))
sum_result.append('{:.4f}'.format(add_time_sum + pop_time_sum))

add_time_sum = 0
pop_time_sum = 0
for i in range(count):
    test_que = deque()
    start = time.time()
    for j in range(data_size):
        test_que.append(j)
    add_time_sum += time.time()-start
    start = time.time()
    for d in test_que:
        tmp = d
    pop_time_sum += time.time()-start
add_result.append('{:.4f}'.format(add_time_sum))
pop_result.append('{:.4f}'.format(pop_time_sum))
sum_result.append('{:.4f}'.format(add_time_sum + pop_time_sum))


add_time_sum = 0
pop_time_sum = 0
for i in range(count):
    test_dict = defaultdict(int)
    start = time.time()
    for j in range(data_size):
        test_dict[j] += 1
    add_time_sum += time.time()-start
    start = time.time()
    for key in test_dict.keys():
        tmp = test_dict[key]
    pop_time_sum += time.time()-start
add_result.append('{:.4f}'.format(add_time_sum))
pop_result.append('{:.4f}'.format(pop_time_sum))
sum_result.append('{:.4f}'.format(add_time_sum + pop_time_sum))


print(','.join(add_result))
print()
print(','.join(pop_result))
print()
print(','.join(sum_result))
print()

listを初めから確保する場合の比較

import time
from collections import deque, defaultdict

total_loop = 10**7
sizes = [10**i for i in range(8)]

add_result = []
pop_result = []
sum_result = []

# これを変えて試す
SIZE_IDX = 2
data_size = sizes[SIZE_IDX]

count = total_loop // data_size
print('data num:{}  loop count:{}'.format(data_size, count))
title = '{} / {}'.format(data_size, count)
add_result.append(title)
pop_result.append(title)
sum_result.append(title)

add_time_sum = 0
pop_time_sum = 0
for i in range(count):
    test_list = [0] * data_size
    start = time.time()
    for j in range(data_size):
        test_list[j]=j
    add_time_sum += time.time()-start
    start = time.time()
    for j in range(data_size):
        tmp = test_list[j]
    pop_time_sum += time.time()-start
add_result.append('{:.6f}'.format(add_time_sum))
pop_result.append('{:.6f}'.format(pop_time_sum))
sum_result.append('{:.6f}'.format(add_time_sum + pop_time_sum))

add_time_sum = 0
pop_time_sum = 0
for i in range(count):
    test_list = list()
    start = time.time()
    for j in range(data_size):
        test_list.append(j)
    add_time_sum += time.time()-start
    start = time.time()
    for d in test_list:
        tmp = d
    pop_time_sum += time.time()-start
add_result.append('{:.6f}'.format(add_time_sum))
pop_result.append('{:.6f}'.format(pop_time_sum))
sum_result.append('{:.6f}'.format(add_time_sum + pop_time_sum))

print(','.join(add_result))
print()
print(','.join(pop_result))
print()
print(','.join(sum_result))
print()
1
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
1