リストのソートと重複除去で驚かないために
ソートと重複除去は、リストに対して行える最も単純な 2 つの操作に見えます。だからこそ、その結果が静かに間違っていることがこれほど多いのです。どちらも比較の上に成り立っており、2 つの行が等しいとは何か、どちらの行が先に来るのかについて、唯一の答えはありません。
辞書順は数値順ではない
テキストの既定の比較は、2 つの文字列を 1 文字ずつたどってコードポイントを比較し、最初の相違点で止まります。そこには数値という概念がまったくありません。
input: img1.png, img2.png, img10.png
sorted: img1.png, img10.png, img2.png
img10.png が 2 番目に来るのは、4 文字目で 1 (U+0031) が 2 (U+0032) より小さく、比較がそこで終わるからです。同じ規則により、バージョン 1.10 は 1.9 より前に来ますし、スクリーンショットのフォルダーは撮影された順とは違う並びで表示されます。
| 方式 | 動作 | 注意点 |
|---|---|---|
| 数値ソート | 各行を数値として読む | 数値でない行をどこかに置く必要があり、桁区切り記号は解析を壊す |
| 自然順ソート | 数字の連なりは数値として、それ以外は文字列として比較する | 01 と 1 が等しいと判定されるため、同値時の決着方法が結果を左右する |
数値比較は負の数の問題も解決します。辞書順では -10 が -1 と -2 の間に来てしまいます。マイナス記号も、コードポイントを持つ 1 つの文字にすぎないからです。
大文字が小文字より先に来る、そのほかのコードポイントの驚き
ASCII では大文字が 65 から 90、小文字が 97 から 122 を占めるので、すべての大文字がすべての小文字より前に並びます。
| 入力 | コードポイント順 | 大文字と小文字を区別しない順 |
|---|---|---|
| Zebra, apple, Apricot, banana | Apricot, Zebra, apple, banana | apple, Apricot, banana, Zebra |
数字はすべての文字より下に、空白 (32) はすべての印字可能文字より下に、空行はさらにその下に位置します。そのため昇順のソートは、空行と空白で始まる行を最上部に集め、降順のソートは最下部に集めます。
行末の空白は、同じ問題の目に見えない版です。apple と apple は隣り合って並び、どうしても取り除けない重複のように見えます。ノーブレークスペース (U+00A0) はさらに厄介で、見た目は普通の空白と同じなのに、すべての文字より上に並びます。Windows のファイルを改行だけで分割したときに残る復帰文字も同様です。2 つの行がまったく同じに見えるのにまとまらないなら、隠れた文字を確認してください。
同じリストが国によって違う順に並ぶ
コードポイント順では、アクセント付きの文字はすべて、アクセントのない文字より後ろに置かれます。Zürich は Zzz より後、Ärger は zebra より後になります。自国のアルファベットをそのように並べる言語はありません。ロケールを考慮した照合は代わりに言語の規則で比較しますが、その規則どうしも一致していません。
| ロケール | 規則 | 結果 |
|---|---|---|
| ドイツ語、辞書順 | ä は a、ö は o、ü は u として並ぶ | Apfel, Ärger, Azubi |
| ドイツ語、電話帳順 | ä は ae、ü は ue として並ぶ | Müller は Mueller と同じ場所に入る |
| スウェーデン語 | å、ä、ö が z の後でアルファベットを締めくくる | Apfel, Zebra, Ärger |
| スペイン語 | ñ は独立した文字で、n の後に来る | anzuelo が año より前 |
JavaScript では、これは Intl.Collator にあります。
const words = ["Zebra", "Ärger", "Apfel"];
words.sort(new Intl.Collator("de").compare);
// Apfel, Ärger, Zebra
words.sort(new Intl.Collator("sv").compare);
// Apfel, Zebra, Ärger
同じオブジェクトが、先ほどの問題も扱えます。{ numeric: true } は数字の連なりを数値として比較するもので、これが自然順です。sensitivity は何を差異とみなすかを設定します。"base" は大文字小文字とアクセントを無視し、"accent" は大文字小文字だけを無視し、"case" はアクセントだけを無視します。ロケールを省略するとマシンの設定が使われるため、同じコードが 2 台のノートパソコンで別の順序を返すことになります。出力をどこでも一致させたいなら、ロケールを明示してください。
どれを重複と数えるか
重複除去の明確さは、その背後にある等価判定の明確さを超えません。アキュートアクセント付きの cafe という語として表示される 5 行を考えてみます。
| # | 行 | 実際に格納されているもの |
|---|---|---|
| 1 | café | 合成済みの é (U+00E9) |
| 2 | café | e と結合アキュート (U+0301) |
| 3 | Café | 大文字の C、合成済み |
| 4 | café | 行末に空白 |
| 5 | café | 1 行目と同一 |
妥当な規則を 4 つ考えると、答えも 4 通りになります。
| 規則 | 残る行 | 件数 |
|---|---|---|
| 完全一致 | 1, 2, 3, 4 | 4 |
| トリムしてから完全一致 | 1, 2, 3 | 3 |
| トリムして大文字小文字を畳む | 1, 2 | 2 |
| トリムし、大文字小文字を畳み、NFC に正規化する | 1 | 1 |
どれも間違いではありません。それぞれ別の問いに答えているだけです。正規化は見た目以上に重要です。macOS のファイル名から来たテキストは分解済み (NFD) で届きやすく、Windows や Web フォームから来たテキストは合成済み (NFC) だからです。2 つの出どころから貼り付けたリストには、目に見えない双子が紛れ込みます。NFKC はさらに踏み込み、fi のような合字を含む互換文字を素の形に畳み込みます。
慣習として最初に現れたものが残るので、雑なほうの写しを先に貼り付けていれば、それが生き残ります。そして、重複を取り除くことと、ユニークな項目を見つけることは別の要求です。Remove Duplicate Lines は各項目を 1 つずつ残しますが、List Frequency のユニーク集合は、ちょうど 1 回だけ現れる項目という、より小さなグループです。
安定性と、2 つのキーによるソート
安定ソートは、比較関数が等しいと判定した要素どうしが入力での順序を保つことを保証します。これがあるからこそ、複数のキーによるソートを処理の繰り返しで実現できます。重要度の低いキーから先にソートし、最後に最も重要なキーでソートするのです。名前でソートしてから部署でソートすれば、部署が順に並び、その中で名前が並びます。不安定なソートは、2 回目の処理をしながら 1 回目の結果を崩してしまいます。しかも、その結果はほぼ正しく見えてしまい、明らかに間違って見えるよりたちが悪いのです。
反転にも同じ落とし穴があります。ソート済みのリストをひっくり返すと、同値のグループの中身も逆順になるからです。Reverse List は、順序全体をひっくり返すこと自体が目的のときに使ってください。降順ソートの近道として使うものではありません。
実装によっても違います。JavaScript の Array.prototype.sort が安定であることを要求されるようになったのは ES2019 からです。それ以前の V8 は、配列が一定の大きさを超えると不安定なクイックソートを使っていたため、同じコードが 10 件と 1 万件とで違う挙動を示しました。Python の sorted は安定であり、GNU の sort は -s を付けない限り安定ではありません。
シャッフルはソートの一種ではない
1 行で書けるシャッフル list.sort(() => Math.random() - 0.5) には偏りがあります。ソートは比較関数が一貫した順序を表していることを前提とし、アルゴリズムが必要とする組み合わせだけを問い合わせます。呼び出しのたびに新しい乱数を出す比較関数はその前提を壊すため、結果はアルゴリズムと配列の長さに依存します。要素は元の位置の近くにとどまりやすく、一部の並びは他より格段に高い頻度で現れます。
正しいシャッフルは Fisher-Yates 法を使います。末尾から順にたどり、各要素を、それ自身を含めそれより前から一様に選んだ要素と交換します。
for (let i = list.length - 1; i > 0; i--) {
const j = Math.floor(Math.random() * (i + 1));
[list[i], list[j]] = [list[j], list[i]];
}
よくある壊れた変種は、ループの中で Math.random() * list.length を使い、毎回配列全体から選びます。これは等確率の抽選列を n の n 乗通り生み出しますが、その数は並び順の総数である n の階乗では割り切れないため、一部の並びがより頻繁に現れます。
乱数とソートを正しく組み合わせることもできます。各要素にあらかじめランダムなキーを 1 つ与え、そのキーでソートすればよいのです。こうすれば比較関数は一貫したままです。失敗の原因は、比較の内側でサイコロを振ることにあります。
手順を並べる順序
リストにまつわる問題の多くは、正しい操作を誤った順序で行うことから生じます。
- まず囲みを外す。 コードからコピーしたリストは
"apple",の形で届きます。クォートとカンマは文字列の一部なので、appleとは決して一致しません。Unwrap List Items がこれらを取り除きます。 - トリムして正規化する。 等価判定が、自分の思っているとおりの意味になるようにします。
- 重複を除去する。 一致の規則は既定のまま使うのではなく、意図して選びます。
- ソートする。 Sort Lines はテキスト順、数値順、長さ順、ランダム順に対応します。アクセント付きのデータにはロケールを指定してください。
- 形の変更は最後に。 Group List Items は、リクエストごとの上限に合わせて結果を一定サイズのまとまりに切り分けます。Rotate List は内部の順序を変えずに全体をずらします。
トリムより先に重複除去を行うと、ほぼ同一の行が残ります。重複除去より先にソートを行うのは、これから捨てられる行を並べ替えているだけです。