AtCoder Beginner Contest 217 受験記

AtCoder Beginner Contest 217

ABC217では面白い収穫があったので、久々に記事を書いてます。結果はABCの3完で平常運転なのですが、PyPy3でTLEが取れなかったD問題でListの代わりにArrayを使うとACできる、という裏技的なTipsです。

Arrayはこれまで使ったことがなく、またListとの速度比較記事も見当たらなかったので、今回メモとして簡単に実験してみました。

A - Lexicographic Order

$S\lt T$の真偽で判定しました。文字列も不等号だけで辞書順大小比較できるのほんとありがたい。感謝感謝。

B - AtCoder Quiz

よく見るタイプの問題ですね。if文で条件分岐してもいいんですが、僕はいつもPythonのset使って判定しちゃってます。

S1 = input()
S2 = input()
S3 = input()
 
total = set(["ABC", "ARC", "AGC", "AHC"])
print(list(total - set([S1,S2,S3]))[0])

C - Inverse of Permutation

本当にC問題か？って疑うぐらい最近のC問題と比較して簡単でしたね…問題文の通り、Pの各要素をQの各要素にマッピングしていけば終わりですね。

D - Cutting Woods

こっから本題です。D問題で僕が試してTLEになった解法は以下です。

• $C=1$の時には切断地点の座標$x$を、昇順を保ちつつ座標管理用のListに追加する(bisect.insort()を使用)
• $C=2$の時には、bisect.bisectを使って$x$を超えない最小の座標のインデックスを上記Listから検索し、その座標と1個左の切断地点の座標との差を長さとして出力(インデックスが左端と右端の時だけ注意)

無情にも同じ解法でTLEになり苦しむPythonistaの声がTwitterのタイムラインに木霊していたのですが、そんな中Listの代わりにArrayを使うとACするというツイートを見かけ、試してみたら実際ACしました(コード)。
※ちなみに平衡二分木(AVL木)を使うのが想定解法のようで、ArrayでのACは例外事象のようです。

Pythonでの平衡二分木の実装に関する参考サイト

このArrayとは一体何者なのか。公式ドキュメントを見て、静的型付けのされたListというイメージは掴めたのですが、Listとの実行速度の比較については言及無し。その他のサイトも漁ってみましたが、僕が探した範囲でパフォーマンスについての考察があったのは以下ツイートにもあるサイトのみ。てかNumPyのArrayに関する記事ばっかや。

PythonのListとArray(int)で簡単な速度比較しました。10^9回ループ回してAppendし続けた結果、Arrayが9.62秒、Listが18.05秒。
以下サイトによれば、Arrayは型指定なのでメモリ効率が良く、参照の局所性の観点で高速動作すんじゃね？と。要素が少ない時はListのが高速とか。https://t.co/UzxcjdHBqf pic.twitter.com/UVEA5u4GLQ

— otsuneko@競プロ (@otsuneko_kyopro) September 4, 2021

List vs Array

というわけで以下では、こちらのツイートの補足として自分なりに簡単なListとArrayの比較実験をしてみました。測定結果は細かく記録していませんが、実験ごとに10回程度は試行して同様の傾向になることを確かめています。なお、実行環境はAtCoderのコードテスト環境で、PyPy3(7.3.0)を使って比較しました。
※自分のローカルマシン(Core i7-8850H CPU @ 2.60GHz(12 CPUs))でPyPy3(7.3.2)を使って検証すると、AtCoder環境と比べてList-Array間の計測時間の開きが大きくなったので、よりコンテスト時に有用な情報とするためにAtCoderのコードテスト環境を選びました。

もし詳細について補足頂けたり、有用なリンクをご存知の方はコメント頂ければありがたいです。

実験1：要素へのアクセス($10^8$回)

import time
from array import array

# Create an int array, and a list.
lst = list(range(10**8))
arr = array("i", lst)

start_array = time.time()
# Version 1: loop over array.
s = 0
for n in arr:
    s += n

end_array = start_list = time.time()
# Version 2: loop over list.
s = 0
for n in lst:
    s += n

end_list = time.time()

print("array:" + str(end_array-start_array))
print("list:" + str(end_list-start_list))

結果は以下です。微妙な差ですがListの方が速いですね。ちなみにAtCoderのコードテスト環境だと$10^9$回以上のループはMemory Errorで怒られたため、ローカル環境で$10^9$回ループを回したところArrayの方が速くなりました。このぐらいのループ回数を境にArrayが有利になるようですね。

しかし競プロにおいて$10^9$回もループ回すことあんのか…？AHCならワンチャン…？

array:0.17729425430297852
list:0.14959955215454102

実験2：空配列へのAppend($10^8$回)

次は空のListとArrayに対してAppend操作を行う実験です。

import time
from array import array

# Create an int array, and a list.
lst = []
arr = array("i", [])

start_array = time.time()
# Version 1: loop over array.
for i in range(10**8):
    arr.append(i)

end_array = start_list = time.time()
# Version 2: loop over list.
for i in range(10**8):
    lst.append(i)

end_list = time.time()

print("array:" + str(end_array-start_array))
print("list:" + str(end_list-start_list))

結果は以下です。Arrayの方が速いですね！しかし競プロにおいて(ry

ちなみにループ回数を減らしてみると僕が試した限りでは$10^3$回のループ回数を境に、より少ない場合はListの方が高速、多い場合はArrayの方が高速という結果になりました。

array:2.7162699699401855
list:5.267286062240601

実験3：空配列への順序を保ったAppend(bisect.insort())($10^5$回)

次は今回のD問題で使用した、順序を保って要素をAppendする場合の速度比較です。どのような結果になるでしょうか。

※$10^6$回以上は実行時間制限に引っかかったので、$10^5$回で比較してます。

import time
import random
import bisect
from array import array

# Create an int array, and a list.
lst = []
arr = array("i", [])

rand = [i for i in range(10**5)]
random.shuffle(rand)

start_array = time.time()
# Version 1: loop over array.
for n in rand:
    bisect.insort(arr,n)

end_array = start_list = time.time()
# Version 2: loop over list.
for n in rand:
    bisect.insort(lst,n)

end_list = time.time()

print("array:" + str(end_array-start_array))
print("list:" + str(end_list-start_list))

ArrayがListより概ね2倍弱速いという結果になりました。この高速化のおかげでDがACになったのかな？

ちなみにループ回数が$10^4$回を下回ると明らかにListの方が速くなりましたが、そのオーダーなら競プロにおいてはTLEに引っかかることはないのかな？と思います。

array:0.18128204345703125
list:0.3389091491699219

余談

remove()とかindex()はどうなるかなーと、$10^5$回ぐらいループ回したらListの方が高速でした。それより多いループ数は、かなり実行時間がかかりそうで試せていませんが、Arrayの方が本当に速くなるんだろうか…？

もしかしたら後でもうちょい実験するかもしれません。

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜が僕を待っているので今日はここまでです。

以上です。