累積和を高速で求める方法を教えて下さい。

Question

Pythonにて累積和を求める問題を解いています。
Nが数列の要素の数。EX）0 1 2 3 4 5 6 7 8 9
lineが与えられる数列。
数列のsからgまでの和をquestionの数だけ回答する内容になっています。

発生している問題・エラーメッセージ

Nが100000,questionが100000になるとタイムアウトになってしまいます。
時間短縮できる箇所や工夫を教えて下さい。

該当のソースコード

N = int(input())
line = tuple(map(int,input().split(' ')))
S = [0]
for i in range(0, N):
    S.append(S[i] + line[i])
question = int(input())
for i in range(question):
    s, g = list(map(int,input().split(' ')))
    print(S[g+1] - S[s])

Comments

[8524ba23]

その問題はAOJなどのオンラインジャッジ系で出題されているものでしょうか？
であれば、問題へのURLを記載ください。

[kei.a]

https://paiza.jp/works/mondai/a_rank_level_up_problems/a_rank_twopointers_step2?language_uid=python3
よろしくおねがいします。

[aokikenichi]

プログラミング能力を向上させたいならば細かなところに気を使った方がいいです。
質問の「該当のソースコード」が乱れています バッククォートが一つ足りないようです。

「タイムアウト」とは何でしょうか。
「EX）0 1 2 3 4 5 6 7 8 9」となってますが数列は整数の連番なのでしょうか

[8524ba23]

paizaの利用規約に違反するかと思われます。
ブログ・SNS等の各種媒体（インターネット媒体に限られず、不特定多数が閲覧可能なものを全て含む。）上において、当社がpaizaで出題した問題の内容、当該問題に対する解答、解答へのヒント等の示唆およびカンニング等の不正を助長する内容等を掲載する行為。

[kei.a]

連番ではありません。入力例です。
バッククォートは必要ありませんので削除します。

[kei.a]

スキルチェックではないので良いかと思いました。失礼いたしました。

[kei.a]

このコーナー内の問題については、ユーザー同士で解答を教え合ったり、コードを公開したりするのは自由としています。
上記の記載がありますが・・・

[8524ba23]

提示されたURLには上記のような記載は見当たらないようですが…

[8524ba23]

https://paiza.jp/works/mondai ですかね。

[aokikenichi]

問題集のページを見るとたしかに問題なさそうですよね。でも利用規約との関連が分からないので事務局に問い合わせました。まだ質問が閉じておらずPaizaからもOKが出ましたら回答致します。

ただ、Paizaがソースならば最初からリンクを張っておいて欲しいです。私もPaizaユーザなので危うく地雷を踏むところでした。
「該当のソースコード」ですがインデントが消えています。バッククォートの削除が必要なのではなりません。きちんとルール通りになさってください。
質問を投げた後、どういう表記になっているか確認なさってますか？

[kei.a]

can110さん　そのとおりです。
aokikenichiさん　わたしの表示ではインデントがはいっているのですが・・・
ごめんなさい。

[tiitoi]

どの問題ですか？試せないと実際にどの程度の速度がないとタイムアウトになるのか確認できないのですが、、

[kei.a]

Aランクレベルアップセットー区間の積ー区間和の計算です。よろしくおねがいします。

Answer 1

以下のコードで AC しました。

from itertools import accumulate

N = int(input())
lst = tuple(map(int, input().strip().split(" ")))  # N = 10000 の入力の末尾になぜか空白が入ってるので strip() で除いた
M = int(input())

S = [0] + list(accumulate(lst))
for i in range(M):
    s, e = list(map(int, input().split(" ")))
    print(S[e + 1] - S[s])

修正点

累積和の計算に itertools.accumulate を使うことで4倍程度高速化できました。
Python の標準ライブラリの関数は C で実装されている場合があり、その場合は Python のコードを書くより高速となるため、標準ライブラリの関数でできる処理は積極的に使うようにしましょう。

lst = list(range(100000))

%%timeit
S = [0]
for i in range(0, N):
    S.append(S[i] + lst[i])

19.1 ms ± 11.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

%%timeit
S = [0] + list(accumulate(lst))

3.82 ms ± 28.3 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

速度計測方法

Python - コードの実行時間を計測する方法

Comments

[kei.a]

クリアできました！
itertools.accumulateが必要だったんですね。
これから標準ライブラリも勉強します。ありがとうございました。
他の方も　作法を教えてくださりありがとうございました。