線形時間で座標圧縮
序文
座標圧縮は大小関係を維持したまま、小さな値に書き直す操作を言います。この手法は、値そのものよりも大小関係が重要な問題を考える際に有効です。たとえば次のような問題が考えられます。
- 高さが
で幅がh_i のブロックを与えられた順に積み上げたときの最大の高さを求めよ。ただし、w_i とする。0 < h_i, w_i < 10^{12} - 面積が
のシートをたくさん敷く。シートに覆われた面積を求めよ。ただし、h_i \times w_i とする[1]。0 < h_i, w_i < 10^{12}
座標圧縮は愚直には
アルゴリズム
値がソート済みであれば、要素を昇順に2つずつ比較すると圧縮後の値が得られます。値の大きさが問題になるとき、それは大抵整数なので、基数ソートが使えます[2]。これが線形時間で動作する座標圧縮アルゴリズムの全体像です。
/// 座標圧縮後の配列と復元用の配列を返す。
pub fn compress(values: &[usize]) -> (Vec<usize>, Vec<usize>) {
if values.is_empty() {
// アロケーションは遅延されるので、悪影響はない。
return (Vec::new(), Vec::new())
}
// 1バイトごとに基数ソート
const MASK: usize = 0b1111_1111;
let mut bucket = [0; 256];
let mut result1 = Vec::from_iter(0..values.len());
let mut result2 = vec![0; values.len()];
// values の最大値のビットサイズで抑えても良い
for shift in (0..usize::BITS).step_by(8) {
bucket.fill(0);
for i in result1.iter() {
bucket[(values[*i] >> shift) & MASK] += 1
}
// バケットの左端を計算
let mut sum = 0;
bucket.iter_mut().for_each(|n| {
sum += *n;
*n = sum - *n
});
// 安定ソート
for i in result1.iter() {
let j = (values[*i] >> shift) & MASK;
result2[bucket[j]] = *i;
bucket[j] += 1
}
std::mem::swap(&mut result1, &mut result2);
}
// 座標圧縮。隣接二項を比較する。
result2[result1[0]] = 0;
result1
.windows(2)
.for_each(|i| result2[i[1]] = result2[i[0]] + (values[i[0]] != values[i[1]]) as usize);
let compressed = result2;
// 復元用配列の計算
result1.iter_mut().for_each(|i| *i = values[*i]);
result1.dedup();
let restore = result1;
(compressed, restore)
}
結び
標準ライブラリのソート関数は高速ですが、二分探索は毎回
また、圧縮後の値を求める部分は、SA-ISで部分問題を構築するときと同じ考え方です。本記事は、
最後にベンチマークを載せておきます。執筆時点で3位です。標準ライブラリの汎用ソートを利用する場合よりもわずかに高速でした。
追記(2026/03/07)
最適化
改善点は2か所です。
bucketを事前にまとめて計算し、ソートの直前で累積和をとるようにしました。バケットサイズは
また、元の実装では添え字のみをソートしていましたが、添え字と値の組をソートするようにしました。添え字から値を取得する過程は最悪の場合ランダムアクセスになります[5]。メモリ使用量は

最適化なし(青)・1つ目の最適化(緑)・2つの最適化(赤)での実行時間の比較。両対数グラフ。要素数が
以上より、基数ソートと復元用配列の計算を最適化できました。圧縮後の値の計算は最適化されましたが、書き込みは依然としてランダムアクセスになり得ます[6]。
基数の大きさとTLBについて
配列は仮想的にはメモリ上に連続的に配置されているものとして扱いますが、実際にはいくつかの塊に分けられてバラバラの場所に格納されます。この塊をページと言います。配列に添え字アクセスするとき、それがどのページに割り当てられているのかを知る必要があります。この変換テーブルはキャッシュと同じように管理されています。これをTLBといいます。
基数ソートで利用する基数を
本実装では
Discussion
追記
基数ソートから線形時間が従いますが、汎用ソートでも定数倍の高速化は可能です。具体的にはソート済み配列をEythinger layoutで並べたり、クエリを圧縮後の値に置き換えて復元配列をもてばよいです。