（※2020/5/13 追記 リストの要素数を変更した場合について)
背景
先日のAtcoderでのABC167において、次の問題でTLEを連発しました。
・ABC167D-Teleporter
順番に町をテレポートして、ループになった時点でやめ、残り回数は
modを使って求めればいいということに気づいたのですが、
ループになる ⇔ 再び同じ町にたどりつく ⇔ 訪れた町のリストの中にすでにある
と考えればいいと思い、PythonでX in listを使って処理しようとして時間がかかっていました。
結局代わりにX in setを用いればいいことに気づき通しましたが
そんなに速度が変わるものなのか気になったので調べた結果をまとめました。
set型とは
Pythonの公式ドキュメントより引用
set オブジェクトは、固有の hashable オブジェクトの順序なしコレクションです。通常の用途には、帰属テスト、シーケンスからの重複除去、積集合、和集合、差集合、対称差 (排他的論理和) のような数学的演算の計算が含まれます。
集合は、他のコレクションと同様、 x in set, len(set), for x in set をサポートします。コレクションには順序がないので、集合は挿入の順序や要素の位置を記録しません。従って、集合はインデクシング、スライシング、その他のシーケンス的な振舞いをサポートしません。
また、こちらにもわかりやすく特徴がまとめられていました。
- 同じ要素は一つしか含まれない。
- x in set, len(set), for x in set というような、listのような操作が可能
- 要素を後から追加・削除など変更可能(tupleは変更不可、listは変更可能なのでどちらかというとlistに近い）
- 集合演算が可能（Aに含まれてBに含まれない、A・B両方に含まれるなどの計算が手軽かつ高速に可能）
- 順番が保持されないため、最初に入れたものが最初にあるとは限らない
- listに比べて「x in set」という動作が超高速
要は重複なくソートされた状態で格納されるデータ型のようです。
このため、set型の探索には二分探索が常に利用でき、高速になるようです。
測定条件
list型・set型について調べるために、以下の４つの場合の探索について調べました。
| 番号 | データ型 | データの順番 | 探索方法 |
|---|---|---|---|
| 1 | list |
ランダム | 線形探索 |
| 2 | list |
ソート済み | 線形探索 |
| 3 | list |
ソート済み | 二分探索 |
| 4 | set |
(ソート済み) | (二分探索) |
他の条件は同じにするために
- リストの要素数は$10^6$で重複はない。
- 探索する要素$t$は$1 \le t \le 10^6$を満たす。（絶対みつかる）
- $t$をランダムに$10^2$, $10^3$, $10^4$個生成しそれぞれ探索する。
として行いました。
ソースコード
import time
import random
from collections import deque
num = [i+1 for i in range(1000000)]
num_shaffle = random.sample(num, len(num))
num_set = set(num_shaffle)
#探す対象
target = [random.randint(1, 1000000) for i in range(10000)]
#list型線形探索またはset型
def search_seaquence(L):
each_time = deque([])
for i in range(10000):
#startからelapsed_timeまでの時間差を計測
start = time.time()
target[i] in L
elapsed_time = time.time() - start
each_time.append(elapsed_time)
return list(each_time)
#list型二分探索
def search_half(L):
each_time = deque([])
for i in range(10000):
low = 0
high = len(num) - 1
start = time.time()
while low <= high:
mid = int((low + high) // 2)
guess = L[mid]
if guess == target[i]:
break
elif guess > target[i]:
high = mid - 1
else:
low = mid + 1
elapsed_time = time.time() - start
each_time.append(elapsed_time)
return list(each_time)
def cal_time(LIS, mode):
print(mode)
#合計時間
sum_time = sum(LIS)
print ("sum_time:{0}".format(sum_time) + "[sec]")
return 0
#ランダムlist・線形探索
random_list = search_seaquence(num_shaffle)
cal_time(random_list, 'mode: random list')
#順列list・線形探索
seaquence_list_seq = search_seaquence(num)
cal_time(seaquence_list_seq, 'mode: seaquence list seaquence')
#順列list・二分探索
seaquence_list_half = search_half(num)
cal_time(seaquence_list_half, 'mode: seaquence list half')
#set探索
set_seek = search_seaquence(num_set)
cal_time(set_seek, 'mode: set')
結果
| 探索方法 | $10^2$個合計(sec) | $10^3$個合計(sec) | $10^4$個合計(sec) |
|---|---|---|---|
| ランダムlist・線形探索 | $5.14$ | $4.01 \times 10$ | $4.65 \times 10^2$ |
| ソート済みlist・線形探索 | $1.13$ | $8.36$ | $1.29 \times 10^2$ |
| ソート済みlist・二分探索 | $3.46 \times 10^{-3}$ | $2.03 \times 10^{-2}$ | $1.16 \times 10^{-1}$ |
| set型 | $8.44 \times 10^{-5}$ | $9.92 \times 10^{-4}$ | $5.45 \times 10^{-3}$ |
なんとなくグラフに起こしてみる。
(両対数グラフです。)
予想通りといえばそうなんですが、こんなにオーダーで違うとは。
二分探索のオーダーは$O(\log n)$だったと思うんですが結構違う感じになりました。
同じ二分探索であってもset型の方が$10^4$個では20倍ぐらい早いのは意外でした。
（自分のコードの問題かもですが）
【追記】探索先の要素数を変更した場合について
よく考えたら探索するための探索先(list/set)の要素数を変更しないとオーダーの効果は見えないなと気づいたので
追加で、探索のターゲットは$10^4$個に固定したまま、探索先のリストの要素数を$10^4, 10^5, 10^6$ と
変更した場合についても調べました。
| 探索方法\リスト要素数 | $10^4$個合計(sec) | $10^5$個合計(sec) | $10^6$個合計(sec) |
|---|---|---|---|
| ランダムlist・線形探索 | $1.68$ | $2.58 \times 10$ | $5.37 \times 10^2$ |
| ソート済みlist・線形探索 | $9.26 \times 10^{-1}$ | $1.29 \times 10$ | $1.34 \times 10^2$ |
| ソート済みlist・二分探索 | $8.93 \times 10^{-2}$ | $1.75 \times 10^{-1}$ | $1.76 \times 10^{-1}$ |
| set型 | $5.62 \times 10^{-3}$ | $4.02 \times 10^{-3}$ | $1.01 \times 10^{-2}$ |
(両対数グラフです。)
まさにオーダー通りになりました。よかったです。
二分探索でむしろ時間が減ってるのはランダムで探索先を決めてるからだと思われます。
こうしてみるとlogのオーダーの強さがわかりますね。
まとめ
重複データを探す時、 X in listは使ってはいけない（戒め）
あと、やっぱり二分探索は早い
大量のデータから特定のデータがあるかどうか探す時などにも使えそうです。
ただ、set型だとインデックス情報が消えてしまうので
その情報が欲しいときはlistは別に保持しておくなど工夫が必要だとわかりました。