otsunekoの日常

AtCoder Beginner Contest 217 受験記

AtCoder Beginner Contest 217

ABC217

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

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

A - Lexicographic Order

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

B - AtCoder Quiz

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

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

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

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

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

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:要素へのアクセス(10810^8回)

sum_list_vs_array.py
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のコードテスト環境だと10910^9回以上のループはMemory Errorで怒られたため、ローカル環境で10910^9回ループを回したところArrayの方が速くなりました。このぐらいのループ回数を境にArrayが有利になるようですね。

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

array:0.17729425430297852
list:0.14959955215454102

実験2:空配列へのAppend(10810^8回)

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

append_list_vs_array.py
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

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

array:2.7162699699401855
list:5.267286062240601

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

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

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

insort_list_vs_array.py
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になったのかな?

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

array:0.18128204345703125
list:0.3389091491699219

余談

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

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

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

以上です。