計測に基づくパフォーマンス最適化

計測から始める

推測で書き換えず、再現可能なベンチマークでボトルネックを特定します。入力サイズ、環境、ビルド設定、測定回数を揃えます。

計算量と実測

計算量は入力サイズによる増加傾向を表します。実測時間にはキャッシュ、分岐、割り当て、I/Oも影響します。不要なcloneを減らす、借用する、Vec::with_capacityを使うなどの改善があります。

Top-K

n個から大きい順にk個を取るには全体ソートO(n log n)やサイズkのヒープO(n log k)があります。