単純で正しそうなものが正しいとは限らない

Coding Horror: The Danger of Naïveté

配列の中身をランダムな順序にシャッフルするコードを書きたい。単純でいいから分かりやすくて間違いの無いコードを書こう。例えば,こんな感じに……

for (int i = 0; i < cards.Length; i++)
{
    int n = rand.Next(cards.Length);
    Swap(ref cards[i], ref cards[n]);
}

これは単純で分かりやすい! でも残念! このコードは間違っている。シャッフル後の順序に偏りが出てしまう。正解はこちら。

for (int i = cards.Length - 1; i > 0; i--)
{
    int n = rand.Next(i + 1);
    Swap(ref cards[i], ref cards[n]);
}

ぱっと見て違いが分かる? インデクスを進める方向が逆になっただけのようにも見えるけど,もう少し違いがある。詳しいところは Atwood さんが解説している。

ここで得られる教訓は,単純な―いわゆる「ナイーブな」コードが,正しいとは限らないということ。単純さが正しい風を装っているだけで,その中に気付きにくい誤りを潜めていることだってある。