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).