⚡

線形時間で座標圧縮

に公開
2026/03/07
1件

序文

座標圧縮は大小関係を維持したまま、小さな値に書き直す操作を言います。この手法は、値そのものよりも大小関係が重要な問題を考える際に有効です。たとえば次のような問題が考えられます。

  • 高さがh_iで幅がw_iのブロックを与えられた順に積み上げたときの最大の高さを求めよ。ただし、0 < h_i, w_i < 10^{12}とする。
  • 面積がh_i \times w_iのシートをたくさん敷く。シートに覆われた面積を求めよ。ただし、0 < h_i, w_i < 10^{12}とする[1]。

座標圧縮は愚直にはO(N \log N)で実装できますが、少しの工夫でO(N)にできます。

アルゴリズム

値がソート済みであれば、要素を昇順に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)
}

結び

標準ライブラリのソート関数は高速ですが、二分探索は毎回\Theta(\log N)ステップ必要なためか、座標圧縮の問題は実行時間の長い感覚があります[3]。本稿で紹介したアルゴリズムは、二分探索をまったく必要としません。

また、圧縮後の値を求める部分は、SA-ISで部分問題を構築するときと同じ考え方です。本記事は、|\Sigma| = O(N)の場合でも簡単に接尾辞配列を構築したいという問題意識から生まれました。そのようなアルゴリズムは存在しますが、技巧に走っていて面白くありません[4]。

最後にベンチマークを載せておきます。執筆時点で3位です。標準ライブラリの汎用ソートを利用する場合よりもわずかに高速でした。

追記(2026/03/07)

最適化

改善点は2か所です。

bucketを事前にまとめて計算し、ソートの直前で累積和をとるようにしました。バケットサイズは 4 倍になりましたが、イテレーションが 3 回減りました。バケットの容量はたったの 4 KiBなので、メモリアクセスが減少しました。

また、元の実装では添え字のみをソートしていましたが、添え字と値の組をソートするようにしました。添え字から値を取得する過程は最悪の場合ランダムアクセスになります[5]。メモリ使用量は 2 倍に増加しましたが、分配する値にシーケンシャルアクセスできます。

ベンチマーク
最適化なし(青)・1つ目の最適化(緑)・2つの最適化(赤)での実行時間の比較。両対数グラフ。要素数が 10^6 を超えると性能差が顕著になる。これは後述するTLBミスが多発するためであると考えられる。競技プログラミングで問題になる範囲(N \le 5 \times 10^5)では数ミリ秒の高速化に留まるが、N \sim 4 \times 10^6 では 1/4 程度になった。

以上より、基数ソートと復元用配列の計算を最適化できました。圧縮後の値の計算は最適化されましたが、書き込みは依然としてランダムアクセスになり得ます[6]。

基数の大きさとTLBについて

配列は仮想的にはメモリ上に連続的に配置されているものとして扱いますが、実際にはいくつかの塊に分けられてバラバラの場所に格納されます。この塊をページと言います。配列に添え字アクセスするとき、それがどのページに割り当てられているのかを知る必要があります。この変換テーブルはキャッシュと同じように管理されています。これをTLBといいます。

基数ソートで利用する基数を B とします。管理するページの数は高々 B 個なので、B をTLBサイズよりも小さくすると、高速なメモリアクセスが期待できます。B 個のエントリーで並列して連続書き込みをしているイメージです。各エントリーにランダムアクセスしても、それぞれキャッシュが効くので高速です。

本実装では B = 2^8 を採用しました。これは筆者の環境で実験的に決定された値ですが、典型的な値でもあります。大容量化が進めば B=2^{11} としても良いかもしれません。

脚注
  1. マスの面積がa_i \times b_jになる。 ↩︎

  2. 基数ソートはワードサイズに依存します。比較ソートではないので、最悪\Omega(N \log N)の制約はかかりません。 ↩︎

  3. メモリの読み込み回数が減り、キャッシュミスが減る点でも有利。 ↩︎

  4. O(1)の作業メモリでよいのが強みのアルゴリズムです。 ↩︎

  5. 直感に反しますが、一様な分布をもつソート済みVec<u32>が最悪ケースに近いです。基数ごとのカウントソートをするたびに 2^8 回程度valuesを順方向に走査します。 ↩︎

  6. カウントソートなのでこれ以上の高速化は望めないかも。 ↩︎

Discussion

qdot3qdot3

追記

基数ソートから線形時間が従いますが、汎用ソートでも定数倍の高速化は可能です。具体的にはソート済み配列をEythinger layoutで並べたり、クエリを圧縮後の値に置き換えて復元配列をもてばよいです。