1単語あたり11ナノ秒：アナグラムの過剰最適化

1単語あたり11ナノ秒：アナグラムの過剰最適化

David G. Andersen 2026年10月27日

BLOG → BLOT → SLOT → SPOT ↝ POST

友人が最近、新しいワードラダーゲームのバリアントについて教えてくれました。それは、開始単語から終了単語への変異のパスを見つけるというものです。変異とは、1文字の変更、1文字の削除または追加、あるいは単語のアナグラム化が可能です。それが私を悩ませました（アナグラムを含むパスは見つけるのが非常に難しいことがあります）。そのため、当然ながら、私はそれのソルバーを作成しました。そして、ソルバーの実行に1秒以上かかったため、当然ながら最適化する必要がありました。その過程で、アナグラムインデックス作成のための楽しいトリックを見つけました。辞書のすべての単語に対して衝突のない素数積識別子を単一の64ビット整数に収めるというものです。これは以前見たことがありませんでした（ただし、コンピューティングの歴史は長く、おそらく1965年にKnuthがそれに気づいていたでしょう）。

完全を期すために、私が興味を持っていたのは辞書内のすべてのアナグラムを見つけることでした。特定の単語のアナグラムを見つけたいだけであれば、はるかにシンプルなハッシュテーブル設計で済むでしょう！次の投稿でワードラダー全体を解く際に、すべてのアナグラムを使用します。

アナグラムの発見

アナグラムを見つけるための2つの一般的なトリックは、文字をソートした順列、または文字カウントベクトルを、順序に依存しない一意の識別子として使用することです。

letter_sort("spot") -> "opst"

または

letter_count("spot") -> "[... o:1, p: 1, s: 1, t:1 ...]"

そして、辞書を走査し、文字カウントに基づいてハッシュテーブルに項目を挿入します。Python風の疑似コードでは次のようになります。

for word in dictionary:
  table[letter_sort(word)] += word

これにより、次のようなエントリを持つテーブルが作成されます。

"opst" : ["spot", "post", "tops", "stop"]

ベースライン：文字列のソート

最近コーディングの腕が鈍っていると感じていたので、LLMに指示する代わりにRustで自分で実装することにしました（これはLeetCodeのような問題なので、LLMなら簡単にできたでしょう）。そのコードは次のようになりました。

fn anagram_dictionary(words: &[String]) -> HashMap<String, Vec<String>> {
    let mut anagrams: HashMap<String, Vec<String>> = HashMap::new();
    for word in words {
        let mut key: Vec<u8> = word.bytes().collect();
        key.sort_unstable();
        let key = String::from_utf8(key).expect("dictionary words must be ASCII");
        anagrams.entry(key).or_default().push(word.clone());
    }
    anagrams
}

メモリに事前に読み込まれたScrabble(tm)辞書を使用して、この関数は次のようにアナグラム辞書を生成します。

結果：31ms (1単語あたり173ns)

これは問題ないように思えます。ああ、待ってください、冗談です、これは信じられないほど遅いです。辞書には178,690エントリが含まれており、これは辞書を構築するために単語あたり173ナノ秒を費やしていることを意味します。173ナノ秒あれば、私のMacbook Pro M1では約4400命令を実行できます。そんなものを待つ時間があるでしょうか？？

Vec割り当ての排除

最適化する際、最初に疑うべき場所の1つは割り当てです。このコードには大量の割り当てがあります。各単語は、Vecの割り当て、またはVecへの追加（時には割り当てが必要）のいずれかを結果として生じます。実際には、ハッシュテーブルには約161,019のエントリがあり、これは161kの割り当て（!!）です。より巧妙なデータ構造を使用してこれらを改善しましょう。2つの点に注意してください。

• ハッシュテーブルに161kのエントリがあり、辞書アイテムは178kしかないため、これらのハッシュテーブルエントリのほとんどは単一エントリになります。
• 元の単語リストはメモリに格納されており、そのサイズに基づいてu32でインデックス付けできます。

そこで、2つのことを行います。動的な長さのデータ構造をまったく必要とせずに単一エントリを格納する方法を見つけ、リストへの項目の追加のための連結リストの等価物を実装します。これらは追加専用であり、最後に一度だけスキャンするためです。これを行うために、次のような構造を使用します。

  heads: HashMap::<K, u32>,
  next: Vec<u32>,
  word: Vec<u32>

ここで、headsはアナグラム識別キー（例：文字ソート済み文字列）でインデックス付けされます。このu32をオーバーロードして、最上位ビット（170k程度の単語しかありません）を使用して、実際のデータ値（リスト内の要素のインデックス）またはnext+word配列のインデックスのいずれかを表すようにします。next配列は連結リストであり、next配列の別のエントリへのポインタを格納します。word配列は関連データを格納します。次のようになります。

［画像: keygroups］

結果：31ms -> 20ms (1単語あたり112ns)

ずっと良くなりましたが、さらに改善できます。その文字列をソートして新しい文字列割り当てを作成する時間は無視できず、178k回実行しています。これはナノ秒の大きな塊になります。

代わりに文字カウントベクトルを使用し、それを整数に密にパッキングしてみましょう。文字は26種類しかなく、どの単語も同じ文字を15回以上繰り返さないと仮定すると、文字あたり4ビットを使用でき、26 x 4 = 104ビットになります。これはu128に快適に収まり、小さいわけではありませんが、少なくとも高速なハッシュテーブルキーとして使用できる、 nice fixed size 16 byte のものです。

/// 各文字A-Zの4ビットカウントを保持するu128で単語をグループ化します。
/// 大文字A-Zの単語で、各文字が15回を超えて繰り返されないことを前提とします。
fn u128_lettercount(words: &[String]) -> KeyGroups {
    let items = words.iter().enumerate().map(|(idx, word)| {
        let mut lettercount = 0u128;
        for letter in word.bytes() {
            // A=0, B=1, ... となるように文字をシフトします。
            // 各文字に4ビットを割り当てます。
            lettercount += 1u128 << ((letter - b'A') as u32 * 4);
        }
        (lettercount, idx as u32)
    });
    KeyGroups::new(words.len(), items)
}

（ここでは別のことも行っています。アナグラムを持たないすべての単語を含む完全な辞書ではなく、アナグラムのリストのみを返しています。）

文字列操作とソートを回避することで大きな勝利が得られます。

結果：20ms -> 5.6ms (1単語あたり31ns)

より高速なハッシュテーブル

この時点で、「遅いデフォルトのRustハッシュテーブルはどれくらいコストがかかるのか？」といった質問をすることができます。

そこで、rustc_hashのFxHashMapに切り替えます。これは、ハッシュテーブルに対する敵対的な入力について心配する必要がない場合に、はるかに高速です。

結果：5.6ms -> 4.1ms (1単語あたり23ns)

これはかなり良さそうです。しかし、これで終わりでしょうか？

64ビットゲーデル数化と調整済み素数

もちろん終わりではありません！

文字カウントをu128として格納することも、少し遅すぎます。なぜなら、それは2つの64ビットレジスタに分割され、コンパイラがそれらの間で加算を伝播させ、等価性テストのために2倍の作業を行う必要があるからです。しかし、64ビットで文字カウントを試した場合、2ビットしか格納できず、多くの単語は3文字以上の同じ文字を持っています（例：「MISSISSIPPI」はすでにSを4つ持っています）。

代わりに、ゲーデル数化に基づいたアプローチを使用します。各文字に1つの異なる素数を関連付ける小さなテーブルを作成し、各単語を文字素数の積で識別します。これにより、文字の組み合わせの一意の識別子が保証されます。素朴に考えると、「a -> 2, b -> 3, c -> 5」のように割り当てることができます。しかし、これは実用的なブログ記事であり、結果を64ビットに収めたいと考えています。素朴な割り当てを使用すると、辞書の365番目の単語「ABORTIVENESSES」でオーバーフローします。そしてそれはわずか14文字の長さであり、15文字の単語も3157個あります！ラップアラウンドさせると、ハッシュ関数を実装したことになり、2つの単語が偶然衝突しないという保証はないため、それをチェックするための仕組みを追加する必要が出てきます。

そこで、トリックは次のとおりです。アルファベットへの素数の最適化された割り当てを見つけ、Scrabble辞書のどの単語も64ビット数でオーバーフローしないようにします。標準的な英語の文字頻度（ETAOINSHRDLUなど）から始めましたが、それは少し間違っていることがわかりました。私たちは「the」のような単語にはあまり関心がありません。私たちは「WRONGHEADEDNESS」のような単語に関心があります。したがって、代わりに、3157個の15文字単語に見られるパターンに基づいていく必要があります。特に、「E」は2に割り当てられたままですが、一般的な「T」は29に割り当てられ、「I」には3を使用します。私たちの友人「J」は101に割り当てられています。なぜなら、Jが2つ以上含まれる最も長い単語はわずか12文字だからです：JEJUNENESSES。それを見ると、これらのE、N、Sは低い値を持つべきであり、実際、それらは2、19、17です。64ビットでも15個のNを連続して処理できます。

これを解決するために、小さなプログラムで文字頻度順（アルファベット順よりもはるかに優れていますが、十分ではありません）から始め、オーバーフローした最初の単語を見つけて、その素数の一部をより低い値の素数と交換するループを実行しました。これもソルバーに投入すると面白かったでしょう。

const LETTER_PRIMES: [u64; 26] = [
    5,   // A
    61,  // B
    37,  // C
    53,  // D
    2,   // E
    71,  // F
    47,  // G
    41,  // H
    3,   // I
    101, // J
    73,  // K
    23,  // L
    59,  // M
    19,  // N
    7,   // O
    43,  // P
    97,  // Q
    11,  // R
    17,  // S
    29,  // T
    31,  // U
    89,  // V
    67,  // W
    83,  // X
    13,  // Y
    79,  // Z
];

これはScrabble辞書のどの単語でもオーバーフローしません。単語の文字のバッグに対する衝突のない正規の64ビット識別子を見つけました。コードでは次のようになります。

fn prime_anagramdict(words: &[String]) -> KeyGroups {
    let items = words.iter().enumerate().map(|(idx, word)| {
        let mut product = 1u64;
        for letter in word.bytes() {
            product = product.wrapping_mul(LETTER_PRIMES[(letter - b'A') as usize]);
        }
        (product, idx as u32)
    });
    KeyGroups::new::<FxBuildHasher, _>(words.len(), items)
}

この表現では、最大の積を持つ単語は次のとおりです。

PSYCHOPATHOLOGY = 17763551150644031915

これはlog2で63.945であり、64ビット数値空間の約96.2%を占めています。近いですが、収まります。

結果：4.1ms -> 2.6ms (1単語あたり14.7ns — ベースラインの12倍高速)

u128パッキング単語表現の使用

そして、最後の最適化があります。辞書を文字列として読み込む代わりに、文字あたり5ビットを使用してパッキングされたu128表現に読み込み、次にCPUの命令レベル並列性（ILP）のために2つの独立したアキュムレータを使用して積の累積を行うことで、いくつかの命令レベル並列性を追加します。このu128表現は、後でワードラダーソルバーの他の部分を高速化するのに役立ちます。そのコードは次のようになります。

fn prime_anagramdict_packed(packed_words: &[u128]) -> KeyGroups {
    let items = packed_words.iter().enumerate().map(|(idx, &packed)| {
        let mut even = 1u64;
        let mut odd = 1u64;
        let mut rest = packed;
        while rest != 0 {
            // 最初の5ビット（文字）
            even = even.wrapping_mul(PACKED_PRIMES[(rest & 0x1f) as usize]);
            // 次の5ビット（文字）
            odd = odd.wrapping_mul(PACKED_PRIMES[((rest >> 5) & 0x1f) as usize]);
            rest >>= 10;
        }
        (even.wrapping_mul(odd), idx as u32)
    });
    KeyGroups::new::<FxBuildHasher, _>(packed_words.len(), items)
}

結果：2.6ms -> 2.3ms (1単語あたり13ns - ベースラインの13倍高速)

低レベル最適化：分岐と自動ベクトル化

これはかなり順調に見えます。追加する最後の最適化は、rest != 0ループでのいくつかの分岐ミス予測に対処することです。代わりに、すべての単語を16文字の長さとして扱い、素数テーブルでそれらを1にマッピングすることによって末尾の0を無視します（つまり、積に影響しません）。固定長16を使用すると、コンパイラによる自動ベクトル化も可能になります。それをサポートするために、素数積の計算とハッシュテーブルへの挿入を分離し、ベクトル化された乗算ループからより多くのILPを可能にします。

そのコードは最終的に次のようになります。

fn packed_prime_product(packed: u128) -> u64 {
    debug_assert!(packed >> 80 == 0, "word longer than 16 letters");
    let mut even = 1u64;
    let mut odd = 1u64;
    let mut rest = packed;
    for _ in 0..8 { // 16文字 * 5ビット/文字 = 80ビット。10ビットずつ進むので8回ループ。
        even = even.wrapping_mul(PACKED_PRIMES[(rest & 0x1f) as usize]);
        odd = odd.wrapping_mul(PACKED_PRIMES[((rest >> 5) & 0x1f) as usize]);
        rest >>= 10;
    }
    even.wrapping_mul(odd)
}

fn prime_anagramdict_packed(packed_words: &[u128]) -> KeyGroups {
    let products: Vec<u64> = packed_words.iter().map(|&p| packed_prime_product(p)).collect();
    let items = products.iter().enumerate().map(|(idx, &product)| (product, idx as u32));
    KeyGroups::new::<FxBuildHasher, _>(packed_words.len(), items)
}

結果：2.3ms -> 1.96ms (1単語あたり10.9ns、ベースラインの15倍高速)

これで、明示的なベクトル化なしで私のマシンのシングルコアで到達できる速度にかなり近づきました。1.96msは1バイトあたり約1.23nsであり、理論的には約3.2 x 8 x 1.23 = 31命令（ただし現実にはそれより少ない）になる可能性があります。これは最適化の余地をあまり残していません—ただし、間違っている可能性もあります！さらに高速なハッシュテーブル実装のためのスペースはありますが、そこでは一般的な既製のものを使い続けたいと思います。

最適化の概要

次の投稿では、見つけたアナグラムをその一部として使用して、ワードラダー問題全体をどのように解くかを示します。