組み込み関数関係

再帰上限（★★★）

関数の再帰呼び出しが深くなるとエラーとなります。上限回数は環境により異なりますが、AtCoder では約1000回となっています。

def dfs(n):
    if n==0:
        return 0
    else:
        return dfs(n-1)

# dfs(10000)  # RecursionError

sys.setrecursionlimit により上限回数を変更することができます。¹

import sys
sys.setrecursionlimit(10**5)

def dfs(n):
    if n==0:
        return 0
    else:
        return dfs(n-1)

dfs(10000)  # エラーにならない

リストに対する操作（★★）

組み込み関数の処理は必ずしも O(1) とは限りません。リストの長さが N のとき sort メソッドが \Theta(N\log N) 時間であることは 2.06.計算量 で説明しました。この他にも、リストに対する操作には O(1) ではない操作が多く存在するため注意が必要です。

以下は長さ N のリスト a に対する O(1) でない操作の一例です。

pop 及び del は削除する要素が末尾から遠いほど時間がかかります。特に、末尾要素を削除する a.pop() は O(1) です。

絶対値が2^63より大きな整数を扱うと遅い（★）

桁が大きな数を扱うと計算に時間がかかるのは直感的には当たり前ですが、実際には 2^{63} の前後で急激に変化します。ただし、よほど巨大な数に対する演算でない限り 10^6 回の演算で数十ミリ秒程度の差であるため、ほとんどの場面で気にする必要はありません。

速度検証1(足し算)

start = 10**12  # ここの値を変えて検証
sum(range(start, start + 10**6))

実行速度(ミリ秒)

速度検証2(掛け算)

start = 10**6  # ここの値を変えて検証
s = 0
for i in range(start, start + 10**6):
    s = i*i

実行速度(ミリ秒)

int と str の変換（★）

10^{4300} 以上の整数を print したり文字列に変換しようとした場合や、10^{4300} 以上の整数を表す文字列を int に変換しようとした場合、エラーとなります。

N = 10**5000
# print(N)  # ValueError
# N_str = str(N)  # ValueError

S = "1" * 5000
# S_int = int(S)  # ValueError
S_bin = int(S, 2)  # 10^1500程度の値になるためエラーにならない

sys.set_int_max_str_digits により上限桁数(4300)を変更することができます。

import sys
sys.set_int_max_str_digits(10000)  # 0 を指定すると上限を撤廃する

# 全てエラーにならない
N = 10**5000
print(N)
N_str = str(N)

S = "1" * 5000
S_int = int(S)
S_bin = int(S, 2)

AtCoder 上では実行時引数により上限が撤廃されているため、プログラム中で sys.set_int_max_str_digits を行わなくてもエラーになりませんが、自身のパソコンなどで動かす場合には注意してください。

リストの結合をsumで行うと遅い（★）

N = 10**4  # ここの値を変えて検証
a=[[1] for _ in range(N)]
sum(a, [])  # この行だけ計測

実行速度(ミリ秒)

for 文を使って実装するとこの問題は起こりません。

N = 10**4  # ここの値を変えて検証
a=[[1] for _ in range(N)]
s = []
# ここから下だけ計測
for l in a:
    s += l

実行速度(ミリ秒)

class が遅い（★）

C++ で実装されたAtCoder Library(ACL)では modint クラスがありますが、python の class は遅いため、ACL のような modint クラスを作ることは残念ながら現実的ではありません。

import random
import time
random.seed(777)

class modint1000000007:
    def __init__(self, n=0):
        self.n = n
    def __iadd__(self, other):
        self.n = (self.n + other.n) % 1000000007
        return self

# int
A=[random.randint(0,10**9) for _ in range(10**7)]
def f(A):
    s=0
    for a in A:
        s=(s+a)%1000000007

# modint
B=[modint1000000007(a) for a in A]
def g(B):
    s=modint(0)
    for a in B:
        s+=a

MOD をグローバルに書くと速い（★）

関数の内部でしか使わない変数であっても、グローバルで宣言することでいくらか高速になります。ただし、10^6 回の関数呼び出しで数十ミリ秒程度であるため、ほとんどの場面で気にする必要はありません。

import random

random.seed(777)
A=[random.randint(0, 10**9) for _ in range(10**7)]

# local
def f(A):
    MOD = 10**9+7
    s = 0
    for a in A:
        s = (s+a)%MOD
    return s

# global
MOD = 10**9+7
s = 0
for a in A:
    s = (s+a)%MOD

実行速度(ミリ秒)

標準ライブラリ関係

Queue が遅い（★）

queue のデータ構造を使う場合、queue.Queue ではなく collections.deque を使いましょう。
詳細は 4.02 を参照してください。

deque のランダムアクセスが遅い（★）

deque の要素に添え字を使ってアクセスする処理 d[100] などは遅い(O(N))ため、可能な限り使用は控えましょう。
詳細は 4.02を参照してください。

itertools のオーダーが悪い（★）

「選ばれる要素のindexのリストをin-placeに更新する」などであれば実装方法によっては O(ループ数) とすることができますが、itertools の関数は「選ばれた要素からなるタプルを返す」と、毎回タプルを生成しているためその分の計算量がかかり O(タプルの長さ\times ループ数) となっています。
詳細は 4.01 を参照してください。

サードパーティライブラリ

list と numpy 配列でスライスの挙動が違う（★）

list に対するスライスは新たなリストを生成しますが、numpy 配列に対するスライスはその配列に対するビューを返すため、変更が元のオブジェクトに反映されます。

x1 = [1, 2, 3]
x2 = x1[:]
x2[0] = 100
print(x1)  # [1, 2, 3]

import numpy as np
y1 = np.array([1, 2, 3])
y2 = y1[:]
y2[0] = 100
print(y1) # [100   2   3]

PyPy 関係

タプルの大小比較が遅い（★★★）

タプルの大小関係を比較する操作を多く行うケースでは、タプル (x, y) を整数 x \times 10^9 + y や x \times 2^{20} + y などに置き換えることで数倍の高速化が見込めます。

import random
random.seed(777)

def f(A):
    return sorted(A)

def g(A):
    B=[x<<20|y for x,y in A]
    B.sort()
    return [(x>>20, x&0xfffff) for x in B]

N = 10**5
A = [(random.randint(0, 10**5), random.randint(0, 10**5)) for _ in range(N)]
f(A)
g(A)

実行速度(ミリ秒)

また、第1要素の大小のみを考慮すればよいケースでは sort メソッドのキー関数を指定する次の実装でも、CPython においては高速になります。

import random
random.seed(777)

def g2(A):
    return sorted(A, key=lambda x: x[0])

N = 10**5
A = [(random.randint(0, 10**5), random.randint(0, 10**5)) for _ in range(N)]
g2(A)

再帰関数が遅い（★★）

基本的には CPython より PyPy の方が高速です。しかし、再帰呼び出しは PyPy の方が CPython に比べ数倍遅くなります。

import sys
sys.setrecursionlimit(10**7)

def f(n):
    if n==0:
        return 0
    else:
        return f(n-1)

実行速度(ミリ秒)

問題

リンク先の問題を解いてください。

EX24.再帰関数2

前のページ | 次のページ