当たり前なんだけど

Pythonについて理解が深まる程,テクニックにばかり思考が偏って,当たり前の事を忘れてしまう.

当たり前の事を失念しない様に.

How to add numbers in a range – StackOverflow

[0, 999]で3と5の倍数を足し算.

3と5の倍数のリストを作ってサメンション.

%%timeit
place = []
for x in range(1000):
    if x % 3 == 0 or x % 5 == 0:
        place.append(x)
sum(place)

252 µs ± 11 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

欲しいのは和なので,いちいちリストを作って足すのは非効率.
順に足し合わせていけばいい.

%%timeit
result = 0
for x in range(1000):
    if x % 3 == 0 or x % 5 == 0:
        result += x
result

221 µs ± 8.95 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

処理時間の9割はループ処理+if文に掛かっているので大差はない.
generatorを使えば,

%%timeit
sum(x for x in range(1000) if x % 3 == 0 or x % 5 == 0)

217 µs ± 10.4 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)

ちなみに,

%timeit sum([x for x in range(1000)])

106 µs ± 634 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit sum(x for x in range(1000))

94.7 µs ± 986 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)

%timeit sum(range(1000))

25.1 µs ± 1.34 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)

ifが如何に律速か.ifを無くしてやれば,

%timeit sum(range(0, 1000, 3)) + sum(range(0, 1000, 5)) - sum(range(0, 1000, 15))

16.1 µs ± 349 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

数列の足し算と云えば,[0, 10]の足し算は,(0 + 10) / 2.
この当たり前の話を考えれば,

%%timeit
def func(n, c):
    return c * (n//c) * (n//c + 1) // 2

func(999, 3) + func(999, 5) - func(999, 15)

1.95 µs ± 78.5 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

O(n)がO(1)に.

定数化できるは定数化して,定式化できるは定式化して.当たり前の話を再確認.

広告
カテゴリー: 未分類 パーマリンク

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中