【Python入門】inやnot inの実行速度の比較

このページで解説している内容は、以下の YouTube 動画の解説で見ることができます。

【Python入門】inやnot inの実行速度の比較

nやnot inの実行速度の比較

　Pythonでは、inやnot in演算子を用いて、シーケンスや集合、辞書などの要素の存在確認を行います。特に、集合（set）や辞書（dict）は内部でハッシュテーブルを利用しているため、リストやタプルと比べて、これらの演算子の実行速度が格段に速いとされています。ここでは、実際にtimeitモジュールを使用して、集合とリストに対するin演算子の実行速度を計測し、その違いを具体例や表を用いて解説します。

１．基本的な計測方法と準備処理

　要素の存在確認にかかる実行時間を正確に計測するためには、計測対象の処理以外の準備処理を除外する必要があります。ここでは、timeitモジュールを用いた基本的な計測手法と、不要な処理を省く方法について説明します。

1.1. timeitモジュールの利用方法

timeitモジュールは、コマンドラインから実行する際に以下のような形式で使用します。

python -m timeit -s "準備の処理" "計測する処理"

　たとえば、集合に対して要素の存在確認を行う場合、準備処理として集合を作成し、その後にin演算子でチェックするコードを指定します。これにより、集合の作成時間は計測対象から除外され、純粋な検索処理の速度が求められます。

1.2. 準備処理の例と計測コマンド

　以下の例では、0から149までの整数を含む集合とリストをそれぞれ作成し、123が含まれているかどうかを調べる実行時間を計測しています。

集合の場合（例）

python -m timeit -s "x = set(range(150))" "123 in x"

実行結果例

20000000 loops, best of 5: 15.5 nsec per loop

リストの場合（例）

python -m timeit -s "x = list(range(150))" "123 in x"

実行結果例

500000 loops, best of 5: 521 nsec per loop

解説

• 集合の場合、準備処理でset(range(150))を実行し、その後で123 in xにより、123の存在確認を行っています。
• リストの場合も同様に、list(range(150))でリストを作成し、123 in xで検索を実施します。
• これらの結果から、集合での検索は約15.5ナノ秒、一方リストでは約521ナノ秒となり、集合の方が約33.6倍高速であることがわかります。

２．実行速度の差とその理由

　計測結果に現れる大きな速度差は、各データ構造の内部実装に起因します。ここでは、なぜ集合や辞書が高速なのか、またリストの場合はなぜ低速になるのかについて解説します。

2.1. 集合・辞書の高速な検索の理由

　集合や辞書は、ハッシュテーブルを内部で使用しているため、要素の存在確認は理論上定数時間（O(1)）で実行されます。すなわち、要素数が増加しても、ほぼ同一の時間で検索が完了します。

主なポイント

• ハッシュ法を用いるため、検索対象の要素がすぐに見つかる。
• 1個から数億個程度の要素に対しても高速な検索が可能

2.2. リストの低速な検索の理由

　一方、リストは順次走査（線形探索）により、要素の存在を確認します。つまり、最悪の場合はリスト内のすべての要素をチェックする必要があり、平均して要素数の半分程度の探索が必要になります。

主なポイント

• 要素数に比例した探索時間が必要（O(n)）
• 大量の要素がある場合、検索速度が著しく低下する。

以下の表は、集合とリストにおけるin演算子の実行速度の比較をまとめたものです。

解説

• この表から、集合はリストに比べて約30倍以上高速にin演算子を実行できることが明確に示されています。

まとめ

inやnot in演算子の実行速度は、対象のデータ構造によって大きく異なります。

• 集合や辞書は内部でハッシュテーブルを利用しており、定数時間での検索が可能なため、非常に高速に動作します。
• リストは線形探索を行うため、要素数が増えると検索時間も増加し、平均して半数分の要素を走査する必要があるため、比較的低速になります。

　このような特性を理解し、用途に応じて適切なデータ構造を選択することで、効率的なプログラム設計が可能となります。