きっかけ

最近プログラムを書く機会を増やす＋Pythonに慣れるためにAtCoderに参加しています。
が、AtCoder Beginner Contest 197 CのORXORが通りませんでした。

通るまで検証していたらちょっとした学びが得られたので書き残します。

問題のコードと、その原因

書いたけど通らなかったコードはこちら。

N = int(input())
A = list(map(int, input().split()))

def search(list, n):
    xor_result = 0
    or_result = 0
    for i in range(N):
        or_result |= list[i]
        if n & (2 ** i):
            xor_result ^= or_result
            or_result = 0
    xor_result ^= or_result
    return xor_result

min = 2 ** 30
for i in range(2**(N-1)):
    result = search(A, i)
    if result < min:
        min = result

print(min)

問題としては解けているようですが、結果はTLE(時間内に処理が完了しない)でした。

この中の9行目にn & (2 ** i)がありますが、ここが原因ですね。
これをn & (1 << i)に置き換えると2秒以内に処理が完了するため、正解として受理されます。

実行時間を測ってみる

検証に使用したのはPython 3.7.2です。またAtCoderの実行環境はPython 3.8.2ですが、同様に実行時間に違いがみられます。

以下のように実行時間差を測ってみました。

import time

N = int(input())
A = list(map(int, input().split()))

def search(list, n):
    xor_result = 0
    or_result = 0
    for i in range(N):
        or_result |= list[i]
        if n & (2 ** i):
            xor_result ^= or_result
            or_result = 0
    xor_result ^= or_result
    return xor_result

startTime = time.time()

min = 2 ** 30
for i in range(2**(N-1)):
    result = search(A, i)
    if result < min:
        min = result

endTime = time.time()
runTime = endTime - startTime

print(min)
print(runTime)

この実行結果は以下。（上2行が入力、下2行が出力）

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0
5.442998647689819

5.44秒ほどかかっています。

一方、n & (2 ** i)をn & (1 << i)に置き換えた場合は以下。

20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
0
3.6530091762542725

こちらは3.65秒ほど。というわけで、ビットシフト演算にしたら1.8秒ほど短縮されたのでした。
（これを検証した実行環境ではそれでも2秒を超えていますが、AtCoderで実行すると1.72秒ほどなので通過します。）

学び

今回得た学びはパフォーマンスが求められる場合、インタプリタ言語では2のべき乗（整数乗）の代わりにビットシフト演算を使う方がよいということ。
指数が整数ではない場合はビットシフト演算は使えませんが、整数乗であればビットシフト演算を使ったほうが高速になる可能性があります。

CとかJavaのようなコンパイルを行う言語だとまた事情は異なるはずです。
実際、検索するとこんなページが見つかるように、当然のようにコンパイラの最適化で高速化されています。
CやJavaを使い慣れていたので、「別にべき乗で書いてもビットシフト演算で書いても変わらないでしょ…」と、あまり気にしていませんでした。

が、インタプリタ言語の場合は別問題だと実感しました。
最近のインタプリタ言語は全く最適化していないわけではないでしょうが、実行時にできる最適化は限定的だと思われます。
将来的に解決されるのかどうかは分かりませんが、少なくともPython3.7.2～3.8.2の時点では2のべき乗などはビットシフトによる演算を行ったほうがよさそうです。

所感

ビットシフト演算と乗算では計算量が大きく異なることは理解していましたが、きっと整数乗なら高速に処理されるだろうし、それなくてもこの程度なら大丈夫だろう…と思ったことが失敗でした。
今回はビット演算の考え方で全探索を行っていたので、素直にビットシフト演算で記述すればよかったなーと思いました。

AtCoderの問題を解いていると、実時間でかかる処理時間を少しずつ見極められるようになってきている実感はあります。
この経験もその一つだと捉えて、AtCoderを継続していければと思います。