Pythonのsetとdictは二次関数的な性能になることがある
Python sets and dictionaries can have quadratic-time performance
Pythonのsetやdictは一般にO(1)とみなされているが、ハッシュ衝突を意図的に起こすと挿入・検索が二次関数的に遅くなる。Apple M4 Max上のPython 3.14でnを倍にすると時間が約4倍になり、n=16000では1072ms、10万要素では45秒かかった。また、100万件の文字列キーを引く定数マップでは、dictはキャッシュミスによりキーあたり22nsから202nsへと約9倍遅くなる一方、fastconstmapは9バイト/キーでキャッシュに収まり11.8nsにとどまる。O(1)はあくまでモデルであり現実ではない。
モデルは優れた教育ツールである。素早く学べる単純化されたモデルを提示してくれる。しかしモデルは、私たちの思考の仕方にバイアスをもたらすこともある。
HNでの議論
42- juancn
これは通常、言語を問わず、ありとあらゆる一般的なハッシュテーブルの実装に当てはまることだ（オブジェクトに定義された順序がない場合。順序がある場合は平均O(1)、最悪O(log N)になる）。
O(1)というのは期待される平均ケースのことで、通常はこれが成り立つ。
そう、O(N^2)は理論上あり得るが、何らかの denial of service 攻撃に備えているのでなければ、実際にはほとんど問題にならない。
それでも、ハッシュテーブルの妥当な初期サイズを推測できれば、rehashing のオーバーヘッドをかなり避けられる。
- northisup
Raymond Hettinger が、Python の dict が長年にわたってどれだけ改善されてきたかについて素晴らしいトークをしている。だからこれはすごく興味深いし、おそらく最終的には組み込みの dict をより良くするだけだろう。
そのトークの教訓は、イディオマティックに書いていれば、言語が改善されるにつれて恩恵を受けられるということだ。
- xboxnolifes
ランダムメモリアクセスが O(√N) であるという記事を思い出す: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- ok123456
ほとんどのアルゴリズム解析はメモリ階層を組み込んでいない。この投稿の趣旨が何なのかよく分からない。
本当にそれが気になるなら、自分のマシンの経験的な roofline を計算すればいい。
あと、メモリ階層を指摘したいのであれば、それは「二次関数的な性能」ではない。アルゴリズムはスピルしたからといって挙動が変わるわけではない。コストが大きくなるだけだ。
- brudgers
しかし、真に定数時間のハッシュテーブルを作ることはできるだろうか？ いや、できない。データ構造のサイズが大きくなるにつれて、より遅いメモリが必要になる。
興味深いと思えるほど十分大きなサイズになると、すべては IO に支配される。そして IO は遅いので、興味深いサイズでは性能とは実装をデータの詳細に合わせて調整するかどうかの問題になる {0}。
エンジニアリングは大変な作業であって、素朴な数学ではない。
[0] データは任意であり得るが、決してランダムではない。ランダムでないことこそが、それをデータたらしめている。