ちょっと複雑なアルゴリズムをPythonで実装してみて、自分の予想以上にメモリを食ってしまったので何が原因なのかプロファイルしてみた。 辞書を大量に使ってはいけない 指摘されてみれば当たり前のことなんだけども、辞書はハッシュテーブルなのでメモリをたくさん使う。「グラフの頂点ごとに整数→整数のマッピングを持ちたいな」と思って、うっかり辞書を使ってしまったのだが、エントリー数が6個でも 1048バイト×頂点数 のメモリが吹っ飛んでいく。いくらハッシュのアクセスがO(1)だからといって、1048バイトmallocしてスラッシング起こしてんだったら全然安くない。エントリの個数とアクセス頻度によってはO(n)で線形探索したほうがよっぽどよい。 エントリーの個数が5件までならハッシュテーブルではないコンパクトな持ち方をするので280バイト。それでもでかい。 自作クラスのインスタンスも辞書を持っている