Rust の Vec の sort_by_key は気をつけて使おう

当たり前っちゃ当たり前だが、

vec.sort_by_key(|&value| heavy_function(value));

みたいなことをすると、 heavy_function が比較のたびに呼ばれるので、ソートが定数倍遅くなる。これは sort_by_cached_key でなんとかなるっぽい。

sort_by_key は

This sort is stable (i.e. does not reorder equal elements) and O(m n log(m n)) worst-case, where the key function is O(m).

sort_by_cached_key は

During sorting, the key function is called only once per element.

This sort is stable (i.e. does not reorder equal elements) and O(m n + n log n) worst-case, where the key function is O(m).