Python の設計思想、データ型の内部構造、簡潔な構文、ジェネレータやデコレータ、そして時間計算量までを、ひとつの流れで学べるように整理したノートです。「なぜその挙動になるのか」「その実装はどれくらい現実的か」までつなげて理解することを目的にしています。
参考として、関連するノートも参照してください。
Pythonコーディングの基本91点：実務で使える概念とコード例
導読
- この文は、Python の設計思想を確認する -> データ型の内部構造を理解する -> コードを簡潔に書く構文を学ぶ -> ジェネレータ、イテラブル、イテレータ、デコレータを押さえる -> 時間計算量で実装の良し悪しを判断する、という流れで構成しています。
- 読み始めるときは、まず
import this、copy()とdeepcopy()、可変と不変、内包表記、yield、iter()/next()、@decorator、O(n)とO(n log n)の違いを押さえると全体がつながりやすくなります。
この文の章立ては、次のようになっています。
- Python の設計思想
-
import this: Python の禅を通して、コードの書き方の軸を確認します。 - 重要なフレーズの読み解き: 単純さ、読みやすさ、説明しやすさ、拙速とのバランスを整理します。
- 実務での優先順位: 現場で何を重視すると判断しやすいかをまとめます。
-
- データ型の内部構造
- リストの浅いコピーと深いコピー: ネストした要素がどこまで共有されるかを見ます。
- リストの内部イメージ: 参照の共有がなぜ起きるのかを確認します。
- 辞書のしくみ: ハッシュ値と高速検索の関係を整理します。
- 文字列の保持方法: 文字列が効率よく扱える理由を確認します。
- 可変と不変:
id()と+=の挙動から違いを理解します。 - リスト操作の落とし穴: 要素削除と多次元リスト生成で起こりやすいミスを扱います。
- より簡潔な構文
- 内包表記: 基本形、複数変数、入れ子、辞書内包表記、集合内包表記、ジェネレータ式をまとめます。
- 条件式:
expr1 if condition else expr2の使いどころを確認します。
- ジェネレータ・イテラブル・イテレータ・デコレータ
- ジェネレータ: 惰性評価、ジェネレータ式、
yieldを使ったジェネレータ関数を確認します。 - イテラブルとイテレータ:
iter()、next()、zip()、enumerate()、range()の位置付けを整理します。 - デコレータ: 関数オブジェクト、高階関数、クロージャ、
wraps()を含めて段階的に理解します。
- ジェネレータ: 惰性評価、ジェネレータ式、
- 時間計算量の考え方
- 成長の速さをグラフで見る: 定数、対数、線形、
n log n、二乗、指数を比較します。 - 具体例で比べる: 共通要素判定、一意性判定、フィボナッチ、最大盛水コンテナを通して違いを確認します。
- 計算量だけでは決まらないこと: 定数倍、入力サイズ、実行環境の影響も考えます。
- 成長の速さをグラフで見る: 定数、対数、線形、
Python の設計思想
Python は「何が書けるか」だけでなく、「どう書くのが望ましいか」までかなり強く意識された言語です。その考え方を短い言葉でまとめたものが Python の禅です。
import this で読む
Python の対話環境や Notebook で import this を実行すると、Python の禅が表示されます。細部を暗記する必要はありませんが、設計判断で迷ったときの基準として非常に役立ちます。
import this
重要なフレーズを読み解く
特に重要なフレーズを、日本語で自然に理解できる形に言い換えると次のようになります。
Beautiful is better than ugly.
見た目が整っていて、読みやすい実装は、後から直すときにも強いです。単に飾りとしてきれいという意味ではなく、命名、整形、構造が整理されていることを指します。
- 解釈: 整っていて読みやすい実装は、雑然として追いにくい実装より価値がある。
Simple is better than complex.
同じ問題を解決できるなら、まずは単純な案を選ぶべきです。単純であるほど、説明コストもバグの混入も減らしやすくなります。
- 解釈: まずは最小限の構成で解ける案を優先する。
Complex is better than complicated.
必要に応じて複雑な構造になることはありますが、「複雑」と「ごちゃごちゃして説明不能」は別です。筋の通った複雑さは許容されても、追跡不能な絡まり方は避けるべきです。
- 解釈: 複雑さが必要でも、説明不能な絡まり方にはしない。
Flat is better than nested.
ネストが深くなるほど、条件分岐や例外系を追う負担が増えます。早めに return する、関数へ切り出す、といった工夫で平坦に保つ方が読みやすくなります。
- 解釈: 深い入れ子を避け、なるべく見通しのよい構造にする。
Now is better than never.
Although never is often better than right now.
まず動くものを作る姿勢は重要ですが、考えなしに急いで壊れやすいものを作るのは逆効果です。「とりあえず出す」と「拙速」の線引きを意識する必要があります。
- 解釈 1: 完璧を待ちすぎず、まず動くものを作って前へ進む。
- 解釈 2: ただし、雑な実装を急いで出すくらいなら、一度立ち止まって考えた方がよいことも多い。
If the implementation is hard to explain, it's a bad idea.
If the implementation is easy to explain, it may be a good idea.
自分や他人に説明できない実装は、だいたい保守も難しいです。逆に、実装意図を短く説明できるなら、構造が整理されている可能性が高いです。
- 解釈: 実装の良し悪しは、説明しやすさを基準にすると判断しやすい。
実務で意識したい優先順位
設計思想を実務向けにまとめると、次の 5 点が特に重要です。
- まずは動くものを作り、前へ進める。
- 複数の案で解けるなら、より単純で説明しやすい方を選ぶ。
- 読みやすさ、保守しやすさ、拡張しやすさを意識する。
- 壊れにくさ、例外処理、入力の揺れへの強さを確保する。
- 実行速度とメモリ使用量も無視しない。
これらは同時に最大化できないこともあります。現実の制約に合わせて、どこを優先するかを判断することが大切です。
データ型の内部構造
この章では、リスト、辞書、文字列などの「見た目は単純でも、内部ではどう保持されているか」を確認します。ここを理解すると、コピー時の混乱や検索速度の差、+= の意外な挙動がかなり納得しやすくなります。
不思議なリストから始める
まずは、ネストしたリストをコピーしたときに何が共有され、何が独立するのかを確認します。
浅いコピーで起こること
copy()、スライス、list() などの浅いコピーは、外側のリストだけを新しく作り、内側の可変オブジェクトは共有したままになります。そのため、ネストしたリストや辞書を更新すると、コピー元にも影響が出ます。
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
# 代入だけではコピーではなく、同じオブジェクトを別名で参照するだけ
# list_2 = list_1
# copy() / スライス / list() はいずれも浅いコピー
list_2 = list_1.copy()
# 内側のリストは共有されているので、ここを更新すると両方へ影響する
list_2[1].append(55)
print("list_1:", list_1)
print("list_2:", list_2)
リストの内部イメージを意識する
リストは「要素そのもの」を連続して並べるのではなく、「各要素への参照」を連続して保持する構造として理解すると挙動が追いやすくなります。外側の入れ物が別でも、内側の参照先が同じなら同時に変わります。
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
list_2 = list(list_1) # list_1.copy() と同じ浅いコピー
# 外側のリストに新要素を追加する操作は、それぞれ独立している
list_1.append(100)
list_2.append("n")
print("list_1:", list_1)
print("list_2:", list_2)
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
list_2 = list(list_1)
# 数値のような不変オブジェクトを再代入すると、各リストで独立に差し替わる
list_1[0] = 10
list_2[0] = 20
print("list_1:", list_1)
print("list_2:", list_2)
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
list_2 = list(list_1)
# 内側のリストは共有されているので、片方の更新がもう片方にも見える
list_1[1].remove(44)
list_2[1] += [55, 66]
print("list_1:", list_1)
print("list_2:", list_2)
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
list_2 = list(list_1)
# タプルは不変なので、+= はその場更新ではなく新しいタプルを作る
list_2[2] += (8, 9)
print("list_1:", list_1)
print("list_2:", list_2)
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
list_2 = list(list_1)
# 最後の要素は辞書なので、ここも浅いコピーでは共有される
list_1[-1]["age"] = 18
print("list_1:", list_1)
print("list_2:", list_2)
深いコピーを使う場面
ネストした要素まで完全に分離したいときは copy.deepcopy() を使います。多段のリストや辞書を安全に複製したい場面では、浅いコピーではなくこちらが必要です。
import copy
list_1 = [1, [22, 33, 44], (5, 6, 7), {"name": "Sakura"}]
list_2 = copy.deepcopy(list_1)
# 深いコピーでは内側の辞書やリストも別物として複製される
list_1[-1]["age"] = 18
list_2[1].append(55)
print("list_1:", list_1)
print("list_2:", list_2)
辞書のしくみ
辞書が高速に検索できる理由は、「順番に総当たりする」のではなく、ハッシュ値から保存位置を絞り込めるためです。まずはリスト探索との速度差を体感し、その後で内部イメージを整理します。
リスト検索と辞書検索の違い
リストでは in 判定のために先頭から順に比較していく必要があります。一方で辞書はキーのハッシュ値を利用して位置を特定するため、大量データでもかなり速くなります。
import time
large_list = list(range(1_000_000))
queries = list(range(500)) + [-10] * 500
start = time.time()
count = 0
for query in queries:
if query in large_list: # リストは先頭から順に探す
count += 1
end = time.time()
print("検索件数:", len(queries))
print("リスト内で見つかった件数:", count)
print("所要時間(秒):", round(end - start, 2))
import time
lookup_dict = {i: i for i in range(100_000)}
queries = list(range(500)) + [-10] * 500
start = time.time()
count = 0
for query in queries:
if query in lookup_dict: # 辞書はキー検索が高速
count += 1
end = time.time()
print("検索件数:", len(queries))
print("辞書内で見つかった件数:", count)
print("所要時間(秒):", round(end - start, 2))
辞書の内部イメージ
辞書は「疎な配列を利用した高速検索構造」として理解すると分かりやすいです。キーからハッシュ値を計算し、その結果をもとに保存位置を決める、という流れになります。
d = {}
# まずはキーに対するハッシュ値を計算できることを確認する
print(hash("python"))
print(hash(1024))
print(hash((1, 2)))
# キーを追加するときも、まずはキーのハッシュ値が利用される
d["age"] = 18
print(hash("age"))
# 登録したキーに対して値を取り出せる
print(d["age"])
ハッシュ値が完全に衝突しないとは限らないため、実装側では衝突解決の仕組みも持っています。学習段階では、「辞書はキーのハッシュ値を入口に位置を絞り込むから速い」と理解しておけば十分です。
辞書についての補足
- 辞書は空間を多めに使う代わりに、検索時間を短くする構造です。
- 古い解説では「辞書は無順序」と説明されることがありますが、現在の Python では挿入順序が保持されます。
- それでも高速検索の中心にある考え方は、ハッシュテーブルである点に変わりありません。
緊密に保持される文字列
文字列はリストのように「参照の並び」ではなく、連続したメモリ上へ効率よく格納されると考えると理解しやすくなります。文字列が不変であることも、このような効率的な保持方法と相性がよいポイントです。
- 文字列はデータが連続して並ぶため、比較的効率よく扱えます。
- 同じシーケンス型でも、可変なリストと不変な文字列では内部設計の考え方が異なります。
可変か不変か
Python のオブジェクトは、「内容をその場で変えられるかどうか」で大きく 2 つに分けて理解できます。id() を見ると、再代入なのか、その場更新なのかが追いやすくなります。
不変オブジェクト
数値、文字列、タプルは基本的に不変です。+= をしているように見えても、実際には新しいオブジェクトが作られ、変数がそれを指し直します。
x = 1
y = "Python"
print("x id:", id(x))
print("y id:", id(y))
x += 2
y += " 3.7"
print("x id:", id(x))
print("y id:", id(y))
タプル自体は不変ですが、中に可変オブジェクトを含んでいる場合、その内側は更新できます。この点は初学者が混乱しやすいポイントです。
pair = (1, [2])
pair[1].append(3)
print(pair)
可変オブジェクト
リスト、辞書、集合は可変です。内容をその場で変更できるため、id() はそのままで中身だけ変わることがあります。
items = [1, 2, 3]
profile = {"name": "Sakura", "age": 18}
print("items id:", id(items))
print("profile id:", id(profile))
items += [4, 5]
profile.update({"city": "Tokyo"})
print("items id:", id(items))
print("profile id:", id(profile))
リスト操作の小さな落とし穴
ここでは、実務でも教材でもよく引っかかる 2 つの例を扱います。どちらも「一見正しそうに見えるが、内部挙動を考えると落とし穴がある」例です。
特定の要素を削除する
remove() を何度も呼ぶ書き方は動きますが、毎回先頭から検索するため効率がよくありません。
items = ["d", "d", "d", "2", "2", "d", "d", "4"]
target = "d"
while True:
if target in items:
items.remove(target)
else:
break
print(items)
リストを前から走査しながら remove() すると、要素が左へ詰まるため、意図せず見逃しが起きることがあります。
items = ["d", "d", "d", "2", "2", "d", "d", "4"]
for value in items:
if value == "d":
items.remove(value) # 先頭側から詰め直されるので注意が必要
print(items)
逆方向のインデックスを使う例もあります。
items = ["d", "d", "d", "2", "2", "d", "d", "4"]
for index in range(-len(items), 0):
if items[index] == "d":
items.remove(items[index])
print(items)
多次元リストの生成
[[0] * 10] * 5 のような書き方は、各行が独立したリストになるのではなく、同じリストへの参照を複数回並べた状態になります。
grid = [[0] * 10] * 5
print(grid)
# 1 か所を書き換えると、同じ参照を持つすべての行が変わってしまう
grid[0][0] = 1
print(grid)
この問題は、後で見る内包表記で自然に解決できます。
より簡潔な構文
この章では、「同じ処理をもっと短く、読みやすく書く」ための構文をまとめます。短く書くこと自体が目的ではなく、意図が一目で分かる形へ整理することが狙いです。
内包表記
リスト内包表記を軸に見ていくと、辞書内包表記や集合内包表記、ジェネレータ式も理解しやすくなります。
基本形
リスト内包表記の基本形は次のとおりです。
[expression for value in iterable if condition]
要素は次の 3 つです。
-
expression: 生成したい値の式 -
iterable: 順番に取り出す元データ -
if condition: 必要なものだけを残す条件式。不要なら省略できます。
通常の for 文で書くと、次のような形に対応します。
result = []
for value in iterable:
if condition:
result.append(expression)
20 以内の奇数の平方を求める
まずは通常の for 文で書くと、条件分岐と append() が必要になります。
squares = []
for value in range(1, 21):
if value % 2 == 1:
squares.append(value**2)
print(squares)
同じ処理を内包表記で書くと、意図が 1 行でまとまります。
squares = [value**2 for value in range(1, 21) if value % 2 == 1]
print(squares)
複数の変数を同時に扱う
zip() と組み合わせると、複数の列を同時に処理できます。
left_values = [1, 2, 3]
right_values = [1, 2, 3]
# zip() で同じ位置の要素どうしをまとめて取り出す
results = [left * right for left, right in zip(left_values, right_values)]
print(results)
ループを入れ子にする
内包表記では、複数の for を続けて書くこともできます。順番は通常の入れ子ループと同じです。
colors = ["black", "white"]
sizes = ["S", "M", "L"]
# 先に色を回し、その内側でサイズを回して組み合わせを作る
tshirts = ["{} {}".format(color, size) for color in colors for size in sizes]
print(tshirts)
辞書内包表記、集合内包表記、ジェネレータ式
考え方は同じまま、返す入れ物だけを変えることもできます。
# 辞書内包表記
squares = {value: value**2 for value in range(10)}
for key, value in squares.items():
print(key, ":", value)
# 集合内包表記
squares = {value**2 for value in range(10)}
print(squares)
# ジェネレータ式
squares = (value**2 for value in range(10))
print(squares)
colors = ["black", "white"]
sizes = ["S", "M", "L"]
# ジェネレータ式は一度にすべてを保持せず、必要になったときだけ取り出す
tshirts = ("{} {}".format(color, size) for color in colors for size in sizes)
for tshirt in tshirts:
print(tshirt)
条件式
if と else を 1 行でまとめたいときは条件式を使います。単純な代入処理では特に読みやすくなります。
expr1 if condition else expr2
たとえば、数値の絶対値を求める処理は通常の if 文でも書けます。
n = -10
if n >= 0:
x = n
else:
x = -n
print(x)
条件式で書くと、代入したい値の分岐だけがはっきり残ります。
n = -10
x = n if n >= 0 else -n
print(x)
短く書けるだけでなく、「条件によってどちらの値を採るか」という意図が見やすくなるのが利点です。
ジェネレータ・イテラブル・イテレータ・デコレータ
この章では、Pythonic な書き方を支える重要な道具をまとめて確認します。とくにデータ処理のコードでは頻出で、実務でも学習でも何度も出会う概念です。
ジェネレータ
ジェネレータは、必要な値を必要になったタイミングで 1 つずつ返す仕組みです。大量データをまとめて保持しないため、メモリ効率がよいという大きな利点があります。
先に全部作る書き方の弱点
リスト内包表記で 100 万個の平方を先に全部作ると、後で順に使うだけでも大きなメモリを使います。
square_list = [value**2 for value in range(1, 1_000_001)]
for item in square_list:
pass
この書き方は分かりやすい一方で、値をすべて先に保持してしまうのが弱点です。
ジェネレータ式
ジェネレータ式は、丸括弧で書くことで「必要になるまで計算しない」オブジェクトを作れます。
squares = (value**2 for value in range(1_000_000))
for item in squares:
pass
# 0 から 100 までの合計も、途中のリストを明示的に作らずに求められる
print(sum(value for value in range(101)))
yield を使ったジェネレータ関数
ジェネレータは式だけでなく、関数として定義することもできます。まずは通常の関数でフィボナッチ数列を返す書き方です。
def fib(limit):
result = []
n, a, b = 0, 1, 1
while n < limit:
result.append(a)
a, b = b, a + b
n += 1
return result
print(fib(10))
次に、途中で print() するだけの実験です。値は見えますが、for 文から再利用しやすい形にはなっていません。
def fib(limit):
n, a, b = 0, 1, 1
while n < limit:
print(a)
a, b = b, a + b
n += 1
fib(10)
yield を使うと、値を 1 つ返して処理を一時停止し、次の next() あるいは for ループで再開できるようになります。
def fib(limit):
n, a, b = 0, 1, 1
while n < limit:
yield a
a, b = b, a + b
n += 1
print(fib(10))
for item in fib(10):
print(item)
イテラブルとイテレータ
for 文で回せることと、next() で次の値を直接取り出せることは、似ているようで少し違います。この違いを押さえると、ジェネレータや zip() などの振る舞いが理解しやすくなります。
イテラブル
イテラブルは、for 文へ直接渡せるオブジェクトです。現行 Python では collections.abc から Iterable を import するのが自然です。
from collections.abc import Iterable
print(isinstance([1, 2, 3], Iterable))
print(isinstance({"name": "Sakura"}, Iterable))
print(isinstance("Python", Iterable))
ジェネレータも for 文に直接渡せるので、イテラブルに含まれます。
from collections.abc import Iterable
squares = (value**2 for value in range(5))
print(isinstance(squares, Iterable))
ジェネレータは next() でも進められる
ジェネレータは for 文だけでなく、next() で 1 つずつ取り出すこともできます。
squares = (value**2 for value in range(5))
print(next(squares))
print(next(squares))
print(next(squares))
print(next(squares))
print(next(squares))
値が尽きると StopIteration が送出されます。
squares = (value**2 for value in range(1))
print(next(squares))
try:
print(next(squares))
except StopIteration:
print("これ以上取り出せる値はありません。")
イテレータ
イテレータは、next() で次の値を返せるオブジェクトです。ジェネレータはイテレータでもあります。
from collections.abc import Iterator
squares = (value**2 for value in range(5))
print(isinstance(squares, Iterator))
一方で、リスト、タプル、文字列、辞書、集合はイテラブルではあっても、そのままではイテレータではありません。
from collections.abc import Iterator
print(isinstance([1, 2, 3], Iterator))
print(isinstance((1, 2, 3), Iterator))
print(isinstance("Python", Iterator))
必要なら iter() でイテレータを作れます。
from collections.abc import Iterator
print(isinstance(iter([1, 2, 3]), Iterator))
for item in iterable は、内部ではおおよそ次の流れになっていると考えると分かりやすいです。
-
iter(iterable)でイテレータを取り出す -
next()を繰り返して値を受け取る -
StopIterationが来たらループを終了する
zip()、enumerate()、ファイルオブジェクト
zip() や enumerate() が返すものはイテレータです。必要になったときだけ次の組や番号付き要素を返します。
from collections.abc import Iterator
x_values = [1, 2]
y_values = ["a", "b"]
for item in zip(x_values, y_values):
print(item)
print(isinstance(zip(x_values, y_values), Iterator))
from collections.abc import Iterator
numbers = [1, 2, 3, 4, 5]
for item in enumerate(numbers):
print(item)
print(isinstance(enumerate(numbers), Iterator))
ファイルオブジェクトもイテレータです。大きなファイルを 1 行ずつ扱う場面では、この性質が役立ちます。
from collections.abc import Iterator
with open("sample_iterator.txt", "w", encoding="utf-8") as file_obj:
file_obj.write("1行目\n2行目\n")
with open("sample_iterator.txt", "r", encoding="utf-8") as file_obj:
print(isinstance(file_obj, Iterator))
イテレータは使い切ると空になる
イテレータは一方向にしか進まないので、1 回使い切った後にもう一度同じものを回しても何も出ません。
squares = (value**2 for value in range(5))
for square in squares:
print(square)
print("--- 再度ループ ---")
for square in squares:
print(square)
range() はイテレータではなく、遅延的なシーケンス
range() は next() で直接進めるイテレータではありませんが、長さ、インデックスアクセス、存在判定ができる特殊なシーケンスです。
from collections.abc import Iterator
numbers = range(10)
print(isinstance(numbers, Iterator))
print(len(numbers))
print(numbers[0])
print(9 in numbers)
try:
print(next(numbers))
except TypeError as error:
print(error)
range() は使い切られないので、何度でも for 文に渡せます。
numbers = range(5)
for number in numbers:
print(number)
print("--- もう一度 ---")
for number in numbers:
print(number)
デコレータ
デコレータは、「関数そのものの中身を書き換えずに、前後へ処理を追加したい」という場面で役立つ仕組みです。関数オブジェクト、高階関数、クロージャを順に押さえると、自然に理解できます。
まずは要件を整理する
典型的な要件は次のようなものです。
- すでに作った関数へ機能を追加したい。
- 元の関数本体はできるだけ変更したくない。
- 呼び出し方も変えたくない。
たとえば「関数の実行時間を測りたい」という要求は、デコレータの代表例です。
def f1():
pass
def f2():
pass
def f3():
pass
f1()
f2()
f3()
関数はオブジェクト
Python では関数もオブジェクトなので、変数へ代入したり、引数として渡したりできます。
def square(value):
return value**2
print(type(square))
pow_2 = square # 関数へ別名を付けているのと同じ
print(pow_2(5))
print(square(5))
高階関数
関数を引数として受け取る、または関数を返す関数を高階関数と呼びます。デコレータはこの考え方を使います。
def square(value):
return value**2
def keep_function(func):
return func
func = keep_function(square)
print(func(8))
print(func == square)
ネストした関数
関数の中で別の関数を定義できます。これがデコレータの土台になります。
def outer():
print("outer is running")
def inner():
print("inner is running")
inner()
outer()
クロージャ
内側の関数が外側の変数を参照したまま返されると、その関数は外側の環境ごと保持します。これがクロージャです。
def outer():
x = 1
z = 10
def inner():
y = x + 100
return y, z
return inner
func = outer() # 関数本体と、外側スコープの情報を一緒に保持する
print(func)
print(func.__closure__)
for cell in func.__closure__:
print(cell.cell_contents)
result = func()
print(result)
内側で同名変数を再定義すると、Python はそれをローカル変数とみなします。このため、外側の変数をそのまま更新しようとするとエラーになります。
def outer():
x = 1
def inner():
x = x + 100
return x
return inner
func = outer()
func()
外側の変数を書き換えたいときは nonlocal を使います。
def outer():
x = 1
def inner():
nonlocal x
x = x + 100
return x
return inner
func = outer()
print(func())
まずはシンプルなデコレータ
関数を受け取り、その前後で追加処理を行う関数を返せば、デコレータの基本形になります。
import time
def timer(func):
def inner():
print("inner run")
start = time.time()
func()
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
return inner
def f1():
print("f1 run")
time.sleep(1)
f1 = timer(f1)
f1()
@ を使う書き方
@timer は、f1 = timer(f1) を関数定義の直前で書くための糖衣構文です。
import time
def timer(func):
def inner():
print("inner run")
start = time.time()
func()
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
return inner
@timer
def f1():
print("f1 run")
time.sleep(1)
f1()
引数を取る関数を装飾する
装飾対象の関数が引数を持つなら、内側の関数でも *args と **kwargs を受ける必要があります。
import time
def timer(func):
def inner(*args, **kwargs):
print("inner run")
start = time.time()
func(*args, **kwargs)
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
return inner
@timer
def f1(seconds):
print("f1 run")
time.sleep(seconds)
f1(2)
戻り値が必要なら、それも返すようにします。
import time
def timer(func):
def inner(*args, **kwargs):
print("inner run")
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
return result
return inner
@timer
def f1(seconds):
print("f1 run")
time.sleep(seconds)
return "wake up"
result = f1(2)
print(result)
デコレータ自身に引数を渡す
「普通の計測」と「2 倍にして表示する計測」を切り替えたい、といったように、デコレータ自体へ追加の設定を渡したいこともあります。その場合は 3 重の関数になります。
import time
def timer(method):
def outer(func):
def inner(*args, **kwargs):
print("inner run")
if method == "origin":
print("origin_inner run")
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
elif method == "double":
print("double_inner run")
start = time.time()
result = func(*args, **kwargs)
end = time.time()
print("{} 関数の 2 倍換算時間: {:.2f} 秒".format(func.__name__, 2 * (end - start)))
return result
return inner
return outer
@timer(method="origin")
def f1():
print("f1 run")
time.sleep(1)
@timer(method="double")
def f2():
print("f2 run")
time.sleep(1)
f1()
print()
f2()
ここでは「外側の関数が設定を受け取り、その中で本当のデコレータを返す」という形になっており、クロージャの理解が特に重要です。
デコレータはいつ実行されるか
デコレータは関数が呼ばれた瞬間ではなく、「関数定義が評価された時点」で適用されます。その挙動は、関数一覧の収集で確認すると分かりやすいです。
func_names = []
def find_function(func):
print("run")
func_names.append(func)
return func
@find_function
def f1():
print("f1 run")
@find_function
def f2():
print("f2 run")
@find_function
def f3():
print("f3 run")
for func in func_names:
print(func.__name__)
func()
print()
元の関数情報を保つには wraps() を使う
普通にデコレータをかけると、装飾後の関数は inner の情報を持つようになります。これでは __name__ やドキュメント文字列が隠れてしまいます。
import time
def timer(func):
def inner():
print("inner run")
start = time.time()
func()
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
return inner
@timer
def f1():
time.sleep(1)
print("f1 run")
print(f1.__name__)
functools.wraps() を付けると、元の関数情報を引き継げます。
import time
from functools import wraps
def timer(func):
@wraps(func)
def inner():
print("inner run")
start = time.time()
func()
end = time.time()
print("{} 関数の実行時間: {:.2f} 秒".format(func.__name__, end - start))
return inner
@timer
def f1():
time.sleep(1)
print("f1 run")
print(f1.__name__)
f1()
時間計算量の考え方
この章では、「入力サイズが大きくなったとき、そのアルゴリズムの処理時間がどう増えるか」を見ていきます。厳密な実測値は環境で変わりますが、増え方の傾向をつかむことで、どの実装が現実的かを判断しやすくなります。
成長の速さをざっくり見る
まずは「最大値探索は O(n)」「選択ソートは O(n^2)」といった代表例を確認します。
import numpy as np
values = np.random.randint(100, size=10)
print(values)
# 最大値探索は要素を一度ずつ見るので O(n)
# 選択ソートは比較が増えるので O(n^2)
次に、代表的な関数の伸び方をグラフで比較します。
import numpy as np
def constant_curve(x_values):
"""定数関数"""
return np.ones(len(x_values))
def log_curve(x_values):
"""対数関数"""
return np.log(x_values)
def linear_curve(x_values):
"""線形関数"""
return x_values
def n_log_n_curve(x_values):
"""n log n 関数"""
return x_values * np.log(x_values)
def square_curve(x_values):
"""二乗関数"""
return x_values**2
def exponential_curve(x_values):
"""指数関数"""
return 2**x_values
import matplotlib.pyplot as plt
plt.style.use("seaborn-whitegrid")
x_values = np.linspace(1, 20, 100)
methods = [
constant_curve,
log_curve,
linear_curve,
n_log_n_curve,
square_curve,
exponential_curve,
]
labels = [
"$y = 1$",
"$y = log(x)$",
"$y = x$",
"$y = xlog(x)$",
"$y = x^2$",
"$y = 2^x$",
]
plt.figure(figsize=(12, 6))
for method, label in zip(methods, labels):
plt.plot(x_values, method(x_values), label=label, lw=3)
plt.xlim(1, 20)
plt.ylim(0, 40)
plt.legend()
この比較から、次のように整理できます。
- 特に望ましい: 定数時間、対数時間
- 現実的に受け入れやすい: 線形時間、
n log n - 大きな入力では厳しい: 二乗時間、指数時間
3 つの列の共通要素が空かを判定する
重複のない 3 つの列 A、B、C があり、3 列の共通要素が存在するかどうかを調べる問題を考えます。
データを作る
import random
def create_sequences(size):
a_values = random.sample(range(1, 1000), k=size)
b_values = random.sample(range(1000, 2000), k=size)
c_values = random.sample(range(2000, 3000), k=size)
return a_values, b_values, c_values
総当たりで調べる方法
3 重ループで全組み合わせを調べると、計算量は O(n^3) になります。
A, B, C = create_sequences(100)
def no_intersection_1(a_values, b_values, c_values):
for a_value in a_values:
for b_value in b_values:
for c_value in c_values:
if a_value == b_value == c_value:
return False
return True
%timeit no_intersection_1(A, B, C)
print(no_intersection_1(A, B, C))
先に一致を減らしてから見る方法
a == b の候補だけを先に絞れば、3 本目のループへ入る回数を減らせます。考え方としては O(n^2) に改善できます。
def no_intersection_2(a_values, b_values, c_values):
for a_value in a_values:
for b_value in b_values:
if a_value == b_value:
for c_value in c_values:
if a_value == c_value:
return False
return True
%timeit no_intersection_2(A, B, C)
実測で比べる
import time
results_n3 = []
results_n2 = []
for size in [10, 20, 100]:
A, B, C = create_sequences(size)
start_1 = time.time()
for _ in range(100):
no_intersection_1(A, B, C)
end_1 = time.time()
for _ in range(100):
no_intersection_2(A, B, C)
end_2 = time.time()
results_n3.append(str(round((end_1 - start_1) * 1000)) + "ms")
results_n2.append(str(round((end_2 - end_1) * 1000)) + "ms")
print("{0:<23}{1:<15}{2:<15}{3:<15}".format("方法", "n=10", "n=20", "n=100"))
print("{0:<25}{1:<15}{2:<15}{3:<15}".format("no_intersection_1", *results_n3))
print("{0:<25}{1:<15}{2:<15}{3:<15}".format("no_intersection_2", *results_n2))
要素が一意かどうかを調べる
「リスト内に重複があるかどうか」も、時間計算量の違いを学ぶのにちょうどよい題材です。
2 重ループで直接比較する
def unique_1(values):
for i in range(len(values)):
for j in range(i + 1, len(values)):
if values[i] == values[j]:
return False
return True
この方法はすべての組み合わせを比較するため、計算量は O(n^2) になります。
先にソートして隣同士を比べる
ソート後は、同じ値があれば隣り合う形になります。そのため、全組み合わせ比較ではなく、隣接要素だけを見れば済みます。
def unique_2(values):
sorted_values = sorted(values)
for index in range(len(sorted_values) - 1):
if sorted_values[index] == sorted_values[index + 1]:
return False
return True
ソートのコストが支配的なので、全体としては O(n log n) です。
実測で比べる
import random
import time
results_n2 = []
results_n_log_n = []
for size in [100, 1000]:
values = list(range(size))
random.shuffle(values)
start_1 = time.time()
for _ in range(100):
unique_1(values)
end_1 = time.time()
for _ in range(100):
unique_2(values)
end_2 = time.time()
results_n2.append(str(round((end_1 - start_1) * 1000)) + "ms")
results_n_log_n.append(str(round((end_2 - end_1) * 1000)) + "ms")
print("{0:<13}{1:<15}{2:<15}".format("方法", "n=100", "n=1000"))
print("{0:<15}{1:<15}{2:<15}".format("unique_1", *results_n2))
print("{0:<15}{1:<15}{2:<15}".format("unique_2", *results_n_log_n))
n 番目のフィボナッチ数を求める
フィボナッチ数列は、再帰の書きやすさと計算量の悪さを同時に学べる代表例です。
def bad_fibonacci(n):
if n <= 1:
return n
return bad_fibonacci(n - 2) + bad_fibonacci(n - 1)
この再帰は同じ値を何度も計算し直すため、計算量はおおよそ O(2^n) になります。
def good_fibonacci(n):
index, a_value, b_value = 0, 0, 1
while index < n:
a_value, b_value = b_value, a_value + b_value
index += 1
return a_value
こちらは前から順に更新していくだけなので O(n) です。
%timeit bad_fibonacci(10)
%timeit good_fibonacci(10)
最大盛水コンテナ
LeetCode の代表問題の 1 つで、総当たりと双方向ポインタの差が非常に分かりやすく出る例です。
総当たり
左右の壁の全組み合わせを試せば答えは見つかりますが、計算量は O(n^2) になります。
import numpy as np
def max_area_double_cycle(height):
"""総当たりで最大面積を探す"""
left_index, right_index, max_area = 0, 0, 0
for i in range(len(height) - 1):
for j in range(i + 1, len(height)):
area = (j - i) * min(height[j], height[i])
if area > max_area:
left_index, right_index, max_area = i, j, area
return left_index, right_index, max_area
height = np.random.randint(1, 50, size=10)
print(height)
print(max_area_double_cycle(height))
import matplotlib.pyplot as plt
# 棒グラフにすると、どの 2 本の線を選ぶかをイメージしやすい
plt.bar(range(10), height, width=0.5)
plt.xticks(range(0, 10, 1))
双方向ポインタ
両端から始めて、低い方の壁だけを内側へ動かすと、より効率よく探索できます。これで計算量は O(n) まで下がります。
def max_area_bothway_points(height):
"""双方向ポインタ法"""
i = 0
j = len(height) - 1
left_index, right_index, max_area = 0, 0, 0
while i < j:
area = (j - i) * min(height[i], height[j])
if area > max_area:
left_index, right_index, max_area = i, j, area
# 面積を広げるには、低い側を動かすしかない
if height[i] == min(height[i], height[j]):
i += 1
else:
j -= 1
return left_index, right_index, max_area
print(max_area_bothway_points(height))
実測で比べる
import time
double_cycle = []
bothway_points = []
for size in [5, 50, 500]:
height = np.random.randint(1, 50, size=size)
start_1 = time.time()
for _ in range(100):
max_area_double_cycle(height)
end_1 = time.time()
for _ in range(100):
max_area_bothway_points(height)
end_2 = time.time()
double_cycle.append(str(round((end_1 - start_1) * 1000)) + "ms")
bothway_points.append(str(round((end_2 - end_1) * 1000)) + "ms")
print("{0:<15}{1:<15}{2:<15}{3:<15}".format("方法", "n=5", "n=50", "n=500"))
print("{0:<13}{1:<15}{2:<15}{3:<15}".format("総当たり", *double_cycle))
print("{0:<13}{1:<15}{2:<15}{3:<15}".format("双方向ポインタ", *bothway_points))
計算量が小さければ常に正しいとは限らない
100000n と 0.00001n^2 を比べると分かるように、次数だけでは実行時間のすべてを決められません。
- 理論上は
nの方がn^2より有利でも、定数倍が極端に大きいと小規模入力では不利になることがあります。 - 入力サイズがどれくらいか、1 回しか実行しないのか、何千回も回すのかで評価は変わります。
- そのため、漸近的な計算量と、現実の定数倍や実測時間の両方を見ることが大切です。
実行速度に影響する要因
速度を左右する要因として、次の 3 つを意識しておくと整理しやすくなります。
- ハードウェア: CPU、メモリ、ストレージなどの性能差。
- ソフトウェア: 実行環境、ライブラリ、インタプリタやコンパイラの違い。
- アルゴリズム: 入力が大きくなったときの伸び方を決める本質的な要因。
この中で、普段の実装者が最も直接コントロールしやすいのはアルゴリズムです。だからこそ、時間計算量の考え方を早い段階で押さえておく価値があります。
まとめ
この文の内容は一見ばらばらに見えますが、実際にはかなり強くつながっています。
- Python の設計思想は、「読みやすく、説明しやすく、筋の通った実装を選ぶ」という判断軸を与えてくれます。
- データ型の内部構造を理解すると、コピー、検索、可変・不変の挙動が自分の言葉で説明できるようになります。
- 内包表記、ジェネレータ、イテレータ、デコレータを理解すると、コードを簡潔にしつつ、必要な処理を無理なく拡張できるようになります。
- 時間計算量を押さえると、その実装が大きな入力に耐えられるかどうかを判断しやすくなります。
特に、Simple is better than complex. と If the implementation is easy to explain, it may be a good idea. は、アルゴリズム選択にもそのまま効いてきます。まずは正しく、次に分かりやすく、そのうえで必要なら速くする、という順序で考えると、無理のない改善につながります。