概要
この記事では、Pythonの辞書キーのデータ構造の違いに起因する、計算時間の違いについて述べます。ここで挙げる辞書キーのデータ構造は、タプル（tuple）、整数（int）、文字列（string）、そして比較対象としての二重の辞書構造（dict[][]）です。
試算では二次元グリッドを想定し、そのインデックスのiとjからキーを作ります。本記事では値の追加と参照の計算時間を調べました。二次元グリッドのサイズを調整して、全体的な計算量を$10^5$、$10^6$、$10^7$としました。
結論として、キーとなるタプル、整数、文字列の生成を含めない場合（事前にforループで生成しておく場合）、値の追加についての$10^7$の計算量では、タプルをキーとした計算時間は3.5秒、整数は1.3秒、文字列は4.9秒、二重の辞書構造では1.4秒となりました。一方でキーの生成を計算時間に含めた場合、タプルをキーとした計算時間は4.9秒、整数は1.5秒、文字列は8.5秒、二重の辞書構造では1.1秒となりました。（値の参照の計算時間については以下の表に載せています）
今回の解析では計算環境にgoogle colaboratoryを使用しており、計算時間が0.1秒単位で変動します。上記の「二重の辞書構造では1.1秒」は誤りではありません。ただそれを加味しても、タプルと文字列をキーとした場合の計算時間の長さは際立ちます。結論としての計算時間の長短は次のとおりです。
- 整数キー ～ 二重辞書 ＜ タプルキー ＜ 文字列キー
Pythonでは、辞書のキーにタプルも使えます。こちらの記事をご覧下さい。
私が調べた限りでは、Pythonのキーのデータ構造に依存する計算時間の違いについて、他の記事はありませんでした。C#についてはこちらの記事がありました。
計算環境
- 計算機: Google Colaboratory
- Python: 3.10.12
- 時間計測: time.perf_counter()
四種類のキー
以下は、四種類のキーについての、値の追加コードの部分例です。キーの生成を計算時間に含める場合のコードです。インデックスiとjの二重のforループを回しています。
for i in range(n):
for j in range(n):
d[(i,j)] = 1
e=10**(len(str(n))+1)
for i in range(n):
for j in range(n):
d[i*e + j] = 1
for i in range(n):
for j in range(n):
d[str(i)+"_"+str(j)] = 1
for i in range(n):
d[i]=dict()
for j in range(n):
d[i][j] = 1
整数のキーをiとjから作る場合（k=i*e+j）、eを適切な値にとることによってxとyの値を保存できます。例えば1000x1000の二次元座標であれば、e$=10^4$とします。この場合、"i, j = divmod(k, e)"によって、キーからiとjを復元できます。
計算時間
四種類のキーの値の追加について、ループの長さnをn=316, 1000, 3162として計算しました。二重ループなので、計算量としては$10^5$、$10^6$、$10^7$となります。これらの計算を各10回試行して、計算時間の平均値と標準偏差を求めました。最初に、キーの生成を計算時間に含めない場合の表です。
| キー＼計算量 | $10^5$ | $10^6$ | $10^7$ |
|---|---|---|---|
| ( i, j ) | 0.0259 $\pm$ 0.0039 [s] | 0.2905 $\pm$ 0.0428 [s] | 3.4950 $\pm$ 0.4921 [s] |
| i*e + j | 0.0178 $\pm$ 0.0048 [s] | 0.1073 $\pm$ 0.0307 [s] | 1.2618 $\pm$ 0.4319 [s] |
| str(i)+"_"+str(j) | 0.0308 $\pm$ 0.0047 [s] | 0.3857 $\pm$ 0.0403 [s] | 4.8799 $\pm$ 0.7493 [s] |
| [ i ][ j ] | 0.0155 $\pm$ 0.0009 [s] | 0.0998 $\pm$ 0.0062 [s] | 1.3760 $\pm$ 0.3300 [s] |
各キーについて、計算量の増加に比例して計算時間がほぼ線形で増加しています。標準偏差の値を見ると、今回の計算環境での一回の計算時間は、平均値に対して10％から20％以上のばらつきがあるようです。
次に、上記のコードのとおりに、ループ内でキーを生成した場合の計算時間の表です。
| キー＼計算量 | $10^5$ | $10^6$ | $10^7$ |
|---|---|---|---|
| ( i , j ) | 0.0224 $\pm$ 0.0058 [s] | 0.3623 $\pm$ 0.0312 [s] | 4.8980 $\pm$ 0.5525 [s] |
| i*e + j | 0.0139 $\pm$ 0.0037 [s] | 0.1948 $\pm$ 0.0640 [s] | 1.4536 $\pm$ 0.4049 [s] |
| str(i)+"_"+str(j) | 0.0572 $\pm$ 0.0045 [s] | 0.6758 $\pm$ 0.0080 [s] | 8.4560 $\pm$ 0.6212 [s] |
| [ i ][ j ] | 0.0083 $\pm$ 0.0004 [s] | 0.1332 $\pm$ 0.0548 [s] | 1.1034 $\pm$ 0.2516 [s] |
キーの生成を計算時間に含めているため、もちろん計算時間は増加しています。タプルも計算時間が長いですが、文字列をキーとした場合の計算時間はより長いです。文字列の長さ自体も計算時間を伸ばす要因なのでしょうか。
計算時間を短くするなら、文字列とタプルをキーにすることはなるべく避けるべきでしょう。
次に、値を参照する場合の計算時間の表です。キーの生成を計算時間に含めない場合です。
| キー＼計算量 | $10^5$ | $10^6$ | $10^7$ |
|---|---|---|---|
| ( i, j ) | 0.0244 $\pm$ 0.0027 [s] | 0.2797 $\pm$ 0.0083 [s] | 3.7129 $\pm$ 0.6277 [s] |
| i*e + j | 0.0150 $\pm$ 0.0025 [s] | 0.0921 $\pm$ 0.0032 [s] | 0.9956 $\pm$ 0.3714 [s] |
| str(i)+"_"+str(j) | 0.0264 $\pm$ 0.0020 [s] | 0.2627 $\pm$ 0.0037 [s] | 3.6148 $\pm$ 0.4040 [s] |
| [ i ][ j ] | 0.0128 $\pm$ 0.0013 [s] | 0.0893 $\pm$ 0.0034 [s] | 1.2482 $\pm$ 0.4765 [s] |
次に、キーの生成を計算時間に含める場合です。
| キー＼計算量 | $10^5$ | $10^6$ | $10^7$ |
|---|---|---|---|
| ( i , j ) | 0.0192 $\pm$ 0.0015 [s] | 0.3258 $\pm$ 0.0082 [s] | 4.0239 $\pm$ 0.3904 [s] |
| i*e + j | 0.0121 $\pm$ 0.0010 [s] | 0.2354 $\pm$ 0.0636 [s] | 1.3143 $\pm$ 0.3533 [s] |
| str(i)+"_"+str(j) | 0.0568 $\pm$ 0.0065 [s] | 0.8386 $\pm$ 0.2137 [s] | 8.4125 $\pm$ 0.4917 [s] |
| [ i ][ j ] | 0.0067 $\pm$ 0.0004 [s] | 0.0914 $\pm$ 0.0063 [s] | 1.0976 $\pm$ 0.3144 [s] |
値の参照の計算時間は、値の追加の計算時間と同様の傾向を見せます。
今回得られた計算時間では、キーの生成を含めない場合、整数のキー（i*e+j）と二重の辞書構造（[i][j]）の計算時間は、値の追加についても参照についてもほぼ同じです。キーの生成を含めた場合、整数のキー（i*e+j）の計算時間が長くなることは納得が行きます（エラーバー（標準偏差）の範囲内ですが）。一方、標準偏差を考慮しても、タプルと文字列の計算時間がより長いことは明確です。まとめると計算時間の長短は以下のようになります。
- 整数キー ～ 二重辞書 ＜ タプルキー ＜ 文字列キー
おわりに
辞書や連想配列と呼ばれるデータ構造の入出力が高速に行われる事はよく知られていますが、キーのデータ構造による計算時間の長短があるとは私は知りませんでした。使用者としては、プログラム内部のハッシュ変換には手が出ないので、キーのデータ構造を適切に選ぶ必要があります。
過日のAtCoderのコンテストで、高速なはずの辞書の入出力がちっとも高速で無くて困り果てました。試行錯誤の挙げ句、今回の記事となりました。今回の投稿がみなさんのお役に立てば幸いです。