Pythonのlistで速度が出なかった時の話

ABCの過去問埋めをしていて、Listかそうでないかで速度が変わるケースがいくつか発生したのでメモとして残しておく。
結論から言うと、Listへの追加・削除は非常に遅いため、他の方法があるならばなるべく回避すべきである。

①heapq

値を追加して最小値を取り出す、という処理を繰り返す場合において、リストへの追加＋bisectなどによる処理を行うよりも遥かに高速である。
実際にはリストの追加・削除自体がかなり遅いらしい。

ABC 062 D問題 3N Numbers
https://atcoder.jp/contests/abc062/tasks/arc074_b

この問題は部分点アリなので非常にわかりやすい。

試しにn=100,000で、3n個のランダムデータを内蔵したテキストを入力とし、比較を行った。
なお、ソースコードはそれぞれの入力部分をテキストファイルからに変更し、実行時間計測のためのtime.time()を追加したものを使用している。

heapqで実装したもの
https://atcoder.jp/contests/abc062/submissions/4502768
0.4147450923919678秒

list+bisectで実装したもの
https://atcoder.jp/contests/abc062/submissions/4502582
7.703240633010864秒

このサンプルケースは制約の上限値に近いものだが、問題の設定は2秒であることから、heapqで実装した場合はAC、list+bisectで実装した場合はTLEとなった結果と合致する

動作的には1個消して1個挿入するという動きを繰り返しているのだが、どうやらリストの場合はこの処理が重くなるらしい。

bisectなどの部分も関係ある可能性があるため、追加削除を繰り返すスクリプトを作成してみた。

heapq_test.py

import heapq
import time

start = time.time()
f = open('test.txt', 'r')
n = f.readline()
hoge = list(map(int, f.readline().split()))
f.close()

print(time.time() - start)
start = time.time()

for _ in range(10 ** 5):
hoge.append(999999)
del hoge[0]

print(time.time() - start)

f = open('test.txt', 'r')
n = f.readline()
hoge = list(map(int, f.readline().split()))
f.close()

start = time.time()
fuga =
for x in hoge:
heapq.heappush(fuga, x)

print(time.time() - start)

start = time.time()
for _ in range(10 ** 5):
heapq.heappush(fuga, 999999)
heapq.heappop(fuga)

print(time.time() - start)

出力：

0.12592029571533203
12.666174411773682

0.06795763969421387
0.07295346260070801

偶数行目が実行時間だが、この内容だとheapqのほうが圧倒的に早い。
なお、空のリストに1個の要素を追加・削除することを繰り返した場合は、heapqのほうがむしろ遅かった。
bisectとは異なり、末尾に追加・先頭を削除を繰り返しただけなのに、である。
ちなみに、追加する数は適当に999999にしているが、1にした場合でもほぼ同じである。
追加場所は固定なので、listのパターンにおけるソートの有無は関係ないといえる。

なお、奇数行目は読み込みにかかった時間だが、3行目のheapqは実際には1行目のリストのものを足しただけの時間がかかっている。

さて、さらに問題になりうるソートの時間をみてみる。

import heapq
import time

f = open('test.txt', 'r')
n = f.readline()
input_list = list(map(int, f.readline().split()))
f.close()

list_test = + input_list

start = time.time()

list_test.sort()

print(time.time() - start)

start = time.time()

heap_test = []

for x in input_list:
heapq.heappush(heap_test, x)

print(time.time() - start)

結果：

0.13991212844848633
0.06795597076416016

準備段階ではそれほど差は出ていない。やはり追加・削除の部分で大きな差が出るようだ。

②set
追加・検索を繰り返す場合、setのほうがlistより早い。

これは、1つのlistをsetに変えただけだが、それだけでTLEからACになっている。

https://atcoder.jp/contests/abc116/tasks/abc116_d

https://atcoder.jp/contests/abc116/submissions/4417704
https://atcoder.jp/contests/abc116/submissions/4417808

②collections

該当するものをリストから削除する形でカウントしていく構成でTLEになったパターン。collectionsのCounterを用いてそれぞれの要素数をカウントすると、追加・削除ではなく値の変更処理になるため、高速になる。

https://atcoder.jp/contests/agc029/tasks/agc029_b

from collections import Counter

n = int(input())
a = list(map(int, input().split()))

a.sort(reverse=True)
c = Counter(a)

ans = 0
for x in a:
if c[x] == 0:
continue
temp = (1 << x.bit_length()) - x
c[x] -= 1
if temp in c.keys():
if c[temp] > 0:
c[temp] -= 1
ans += 1

print(ans)

ここまであげたものはほとんどの場合制約があるため、他のパターンで利用したい場合はまた考える必要がある。

ちょっとしたCSVファイルの処理で使うなど、大した量の計算を行わないならばリストで書いてしまってもいいだろし、そちらのほうがシンプルに書けるなら多分そうする。