はじめに

Twitterで一時期流行していた 100 Days Of Code なるものを先日知りました。本記事は、初学者である私が100日の学習を通してどの程度成長できるか記録を残すこと、アウトプットすることを目的とします。誤っている点、読みにくい点多々あると思います。ご指摘いただけると幸いです！

今回学習する教材

Effective Python
- 8章構成
- 本章216ページ
第6章：組み込みモジュール

ローカルクロックにはtimeではなくdatetimeを使う

Pythonは、組み込みモジュールのtimeとdatetimeという2種類の方法で、タイムゾーンの変換を行うことができます。
しかし、timeを使う方法ではひどいエラーが起きる危険性があります。
具体的には、timeで複数のローカルタイムを見ようとすると、プログラムが動作しません。
そのため、基本的にはdatetimeを使うべきで、どうしてもtimeを使わなければならない場合は、UTCとホストコンピュータのローカル時間との間の変換にのみ使うべきなようです。
また、datetimeでUTCの他のタイムゾーンを見たい場合は、pytzモジュールを使うことで解決できるようです。

組み込みアルゴリズムとデータ構造を使う

対象課題に最適なアルゴリズムとデータ構造を使うことで、高速化しましょうというお話です。
Python標準ライブラリには多くのアルゴリズムとデータ構造が組み込まれているので、その一部を見ていきます。

両端キュー (Double-ended Queue)

collectionsモジュールのdequeクラスは、両端キューです。
先頭または、末尾への要素追加を定数時間で実行するため、先入れ先だし（FIFO）キューに理想的です。
listで同様の実装する場合、リストの終端に要素を追加したり削除するのは定数時間ですが、先頭に要素を追加したり削除するのは線形時間（要素数が多くなるほど時間がかかる）です。
そのため、listよりcollectionsモジュールのdequeの方が高速です。

from collections import deque

fifo = deque()
fifo.append(1)
print('Before:', fifo)
# Before: deque([1])
x = fifo.popleft()
print('After:', fifo)
# After: deque([])

順序つき辞書 (Ordered Dictionary)

標準辞書は、順序の保証をしていません。つまり、同じキーと値とがdictで順に調べていくと異なる順番で出てくることがあるということです。
CollectionsモジュールのOrderedDictクラスは、キーの挿入順を記録する辞書です。
OrderedDictのキーについて順に反復処理をするときには、振る舞いを予想できるため、テストとデバッグを大幅に単純化することができるようです。

デフォルト辞書 (Default Dictionary)

標準の辞書では、キーの出現回数を数えるという単純な作業でも、面倒な処理を書く必要があります。

stats = {}
keys = [
    'a',
    'a',
    'b',
    'c',
    'a'
]
print(keys)
for key in keys:
    if key not in stats:
        stats[key] = 0
    stats[key] += 1
print(stats)
# {'a': 3, 'b': 1, 'c': 1}

collectionsモジュールのdefaultdictクラスは、キーが存在しないときにデフォルト値を自動的に格納することによって、この処理を単純化します。

from collections import defaultdict

stats = defaultdict(int)
for key in keys:
    stats[key] += 1
print(stats)
# defaultdict(<class 'int'>, {'a': 3, 'b': 1, 'c': 1})

ヒープキュー (Heap Queue)

ヒープは、優先度つきキューを保持するのに役立つデータ構造です。
heapqモジュールは、heappush, heappop, nsmallestのような関数で、標準list型にヒープを作成します。

要素は常に最小数から削除されます。

from heapq import heappush, heappop, nsmallest

a = []
heappush(a, 15)
heappush(a, 3)
heappush(a, 3)
heappush(a, 4)
print('最小値：',a[0])      # ヒープの0番目の要素は常に最小値
print(heappop(a), heappop(a), heappop(a), heappop(a))

実行結果

最小値： 3
3 3 4 15     # 要素の小さいものからpopされる

二分法 (Bisection)

listの要素を探すために、indexメソッドを呼び出すと、リストの長さに比例して時間がかかります。
これに対して、bisectモジュールのbisect_leftのような関数は、ソートされた要素のシーケンスに対して、効率的な二分探索をします。

from bisect import bisect_left
from time import time

start = time()
x = list(range(10**7))
i = x.index(9999999)
end = time()
print('listの実行時間:', end - start)

start = time()
i = bisect_left(x, 9999999)
end = time()
print('bisect_leftの実行時間', end - start)