keisukeのブログ

***乱雑です!自分用のメモです!*** 統計や機械学習の勉強と、読み物を書く練習と、備忘録用のブログ

【Python】sliceの速度

listのsliceの速度がどれくらいかと思って実験してみました.

問題

長さlのlistがあるとします.その連続したr要素の和の最大値を求めます:

x = [1,2,3,10,11,2]  # l = 6: 長さ6のlist
# sum([1,2,3])  # r = 3: 連続した3要素の和
# sum([2,3,10])
# sum([3,10,11])
# sum([10,11,2])
# 一番大きな値はどれ?

方法1 (sliceと呼ぶことにします)

まず,r要素のsliceをとってsumを取る方法:

def slice_sum_max(x, r):
    max_val = -np.inf
    for i in range(len(x)-r+1):
        sum_val = sum(x[i:i+r])
        if sum_val > max_val:
            max_val = sum_val 
    return max_val

方法2 (squeezeと呼ぶことにします)

先頭を押し出して,新しい要素を足していく方法:

def squeeze_sum_max(x, r):
    max_val = sum(x[:r])
    sum_val = max_val
    last_ele = x[0]
    for i in range(len(x)-r+1):
        sum_val -= last_ele
        last_ele = x[i+r]
        sum_val += last_ele
        if sum_val > max_val:
            max_val = sum_val
    return max_val

結果

長さ10000の場合:

f:id:kaisk:20150125021320p:plain

長さ100000の場合:

f:id:kaisk:20150125021328p:plain

どっちも変わらない結果になりました. なお,listのまま関数に渡すか,np.ndarrayに変換してから関数に渡すかを変えていますが,やはりndarrayに要素アクセスすると遅くなるようです.