python3でAtCoderに取り組んだ時に得た実装上のtips

2021/10/17以降AtCoderのコンテストに参加しています。言語はpython3で挑んでいるのですが、その時に得た「こう実装すれば速度を落とさずに実装できる」というTipsを紹介します。

ちなみにAtCoderとは日本発祥の競技プログラミングサイトです。
https://atcoder.jp/home

以下に3つまとめていますが、また気づきがあったら追加します。

1. ベタなキューを使うときは配列[]やqueue.Queue でなく collections.deque を使うこと。

AtCoderでは(というより競技プログラミングの問題全般で)キューを使って解く問題が結構頻出するのですが、これは確実に collections.deque を使った方がいいです。

理由は

• 配列[] は先頭pop に配列の長さ分の計算量がかかる。
• queue.Queueの先頭pop は $O(1)$ で配列[]より速そうだが、同期のためのlockが効いているのか?dequeよりも遅い
  　- https://docs.python.org/ja/3/library/queue.html

です。

計測用コード

import time
from queue import Queue
from collections import deque

# array
start_time = time.time()
array = [i for i in range(100000)]
for _ in range(50000):
    array.pop(0)
elapsed_time = time.time() - start_time
print(f"array.pop(0)  の実行時間 {elapsed_time}sec")

# Queue
queue = Queue()
for i in range(100000):
    queue.put(i)
start_time = time.time()
for _ in range(50000):
    queue.get()
elapsed_time = time.time() - start_time
print(f"Queue.get()   の実行時間 {elapsed_time}sec")

# deque
deq = deque()
for i in range(100000):
    deq.append(i)
start_time = time.time()
for _ in range(50000):
    deq.popleft()
elapsed_time = time.time() - start_time
print(f"deq.popleft() の実行時間 {elapsed_time}sec")

array.pop(0)  の実行時間 0.6488490104675293sec
Queue.get()   の実行時間 0.07807302474975586sec
deq.popleft() の実行時間 0.00417017936706543sec

2. pow(a, b, M)で a = 0 (mod M), b = 0 のときは、0が返ってこない！

pow関数には第3引数にMを設定すると $a^{b} \ mod \ M$ を計算してくれます。
https://docs.python.org/ja/3/library/functions.html#pow

ですが、$a = 0 \ mod \ M, b = 0$ の時には1が返ってきます。期待としては0が返ってきて欲しいのですが。具体例に示していますが、$b = 1$ のときは想定通り0を返します。

具体例

>>> pow(7, 0, 7)
1
>>> pow(7, 1, 7)
0

エッジケースとしてはまるパターンだと思われるので、回避策としては $a = 0 \ mod \ M$ のときは必ず0を返す、といった分岐をかけた方がいいでしょう。$a \ne 0 \ mod \ M$ならばpowが問題なく使えるので。以下の回避策のようにスニペットを用意しておくと便利かもしれません。

回避策(案)

def my_mod_pow(a, b, mod):
   if a % mod == 0:
       return 0
   else:
       return pow(a, b, mod)

3. 整数の切り捨ての割り算は int(b / 2) より b // 2 の方が高速かつ安定する

二分探索などを実装する時に見出しのようなコードを書くと思うのですが、b // 2の方が高速です。そおらく、int(b / 2)だとb / 2の段階でfloatになってから、intへのキャストが入るのでその部分のオーバーヘッドが効いて遅くなっているのかなと考えられます。

計測用のコード

import time

b = 19489741

start_time = time.time()
for _ in range(100000):
    c = int(b / 2)
elapsed_time = time.time() - start_time
print(f"int(b / 2) の実行時間 {elapsed_time}sec")

start_time = time.time()
for _ in range(100000):
    c = b // 2
elapsed_time = time.time() - start_time
print(f"b // 2 の実行時間     {elapsed_time}sec")

int(b / 2) の実行時間 0.017735004425048828sec
b // 2 の実行時間     0.008094310760498047sec

また、これは経験則なのですが、int(b / 2) だとbの値が大きくなった時( $b= 10^{18}$ オーダーだとそれが出てきやすいかも)に値の出方が想定しないものになることがあります。

>>> a = 184763977392749242
>>> int(a / 2)
92381988696374624
>>> a // 2
92381988696374621   # こちらの方が正しい
>>> 

なので、bの二進表現に着想するアルゴリズムを実装する時には b // 2を実装する方がよいです。