CODE Polyglot / よく使う書き方 / 09

複数のキーで並べる

「部署の昇順、同じなら給与の降順」のように、キーを2つ3つ重ねて並べ替えます。一覧画面やレポートで毎回書く処理です。よく見かける書き方は、キーの値が同じ行の順番を崩し、数として読めない値を数の0として並べ、壊れた行を黙って捨てます。

画面にこう出れば正解

どの言語で書いても、同じ入力なら画面に出る文字は1文字も違わない、というのが正解の決め方です(例は Python で動かしたときのコマンドです)。

基本(部署の昇順、同じなら給与の降順)

input.txt の中身

name,dept,salary
佐藤,営業,500
鈴木,開発,900
高橋,営業,1000
田中,開発,900
伊藤,営業,500
$ python3 multi_sort.py dept:asc:text,salary:desc:num < input.txt
name,dept,salary
高橋,営業,1000
佐藤,営業,500
伊藤,営業,500
鈴木,開発,900
田中,開発,900

数として比べる(文字として比べると 1000 が 900 より先になる)

input.txt の中身

name,dept,salary
佐藤,営業,500
鈴木,開発,900
高橋,営業,1000
田中,開発,900
伊藤,営業,500
$ python3 multi_sort.py salary:asc:num < input.txt
name,dept,salary
佐藤,営業,500
伊藤,営業,500
鈴木,開発,900
田中,開発,900
高橋,営業,1000

キーの値がどれも同じ20行は、入力の順のまま(安定な並べ替え)

input.txt の中身

name,dept,salary
r01,営業,100
r02,営業,100
r03,営業,100
r04,営業,100
r05,営業,100
r06,営業,100
r07,営業,100
r08,営業,100
r09,営業,100
r10,営業,100
r11,営業,100
r12,営業,100
r13,営業,100
r14,営業,100
r15,営業,100
r16,営業,100
r17,営業,100
r18,営業,100
r19,営業,100
r20,営業,100
$ python3 multi_sort.py dept:asc:text < input.txt
name,dept,salary
r01,営業,100
r02,営業,100
r03,営業,100
r04,営業,100
r05,営業,100
r06,営業,100
r07,営業,100
r08,営業,100
r09,営業,100
r10,営業,100
r11,営業,100
r12,営業,100
r13,営業,100
r14,営業,100
r15,営業,100
r16,営業,100
r17,営業,100
r18,営業,100
r19,営業,100
r20,営業,100

text の降順

input.txt の中身

name,dept,salary
佐藤,営業,500
鈴木,開発,900
高橋,営業,1000
田中,開発,900
伊藤,営業,500
$ python3 multi_sort.py name:desc:text < input.txt
name,dept,salary
高橋,営業,1000
鈴木,開発,900
田中,開発,900
佐藤,営業,500
伊藤,営業,500

text はコードポイント順(UTF-16 の並びとは変わる)

input.txt の中身

id,name
1,🍣
2,¥
3,私
$ python3 multi_sort.py name:asc:text < input.txt
id,name
3,私
2,¥
1,🍣

数として読めない値は後ろ(読めない値同士は入力の順)

input.txt の中身

name,salary
a,300
b,
c,1e3
d,100
e,100
f, 200
g,-50
$ python3 multi_sort.py salary:asc:num < input.txt
name,salary
g,-50
d,100
a,300
b,
c,1e3
e,100
f, 200

降順でも読めない値は後ろ。007 と 7、-0 と 0 は数として同じ

input.txt の中身

name,salary
a,7
b,007
c,10
d,-0
e,0
f,x
$ python3 multi_sort.py salary:desc:num < input.txt
name,salary
c,10
a,7
b,007
d,-0
e,0
f,x

16桁の数は読めない扱い(15桁までが数)

input.txt の中身

name,salary
a,999999999999999
b,1000000000000000
c,100
$ python3 multi_sort.py salary:asc:num < input.txt
name,salary
c,100
a,999999999999999
b,1000000000000000

3つのキーで並べる

input.txt の中身

name,dept,grade,salary
A,開発,2,500
B,開発,1,900
C,営業,1,500
D,開発,1,500
E,営業,1,500
$ python3 multi_sort.py dept:asc:text,grade:asc:num,salary:desc:num < input.txt
name,dept,grade,salary
C,営業,1,500
E,営業,1,500
B,開発,1,900
D,開発,1,500
A,開発,2,500

列の数が違う行と空の行が混ざる

input.txt の中身

name,dept,salary
佐藤,営業,500
鈴木,開発,900
高橋,営業,1000
田中,開発,900
伊藤,営業,500

佐藤,営業
田中,開発,900,余分
$ python3 multi_sort.py salary:asc:num < input.txt
name,dept,salary
佐藤,営業,500
伊藤,営業,500
鈴木,開発,900
田中,開発,900
高橋,営業,1000
読めない行 2

2つ目のキーが見出しに無い

input.txt の中身

name,dept,salary
佐藤,営業,500
鈴木,開発,900
高橋,営業,1000
田中,開発,900
伊藤,営業,500
$ python3 multi_sort.py dept:asc:text,bonus:desc:num < input.txt
NG: 列 bonus がありません

向きが asc でも desc でもない

input.txt の中身

name,dept,salary
佐藤,営業,500
鈴木,開発,900
高橋,営業,1000
田中,開発,900
伊藤,営業,500
$ python3 multi_sort.py salary:up:num < input.txt
NG: 並べ方の指定が読めません

空の入力

input.txt の中身

(空)
$ python3 multi_sort.py dept:asc:text < input.txt
NG: 列 dept がありません

見出しだけ(データの行が無い)

input.txt の中身

name,dept,salary
$ python3 multi_sort.py dept:asc:text < input.txt
name,dept,salary

改行が \r\n で、最後に改行が無い

input.txt の中身

name,dept,salary[CR]
佐藤,営業,500[CR]
鈴木,開発,900[CR]
高橋,営業,1000[CR]
田中,開発,900[CR]
伊藤,営業,500
$ python3 multi_sort.py dept:asc:text,salary:desc:num < input.txt
name,dept,salary
高橋,営業,1000
佐藤,営業,500
伊藤,営業,500
鈴木,開発,900
田中,開発,900

10言語のプログラム

どれもそのまま保存して動かせます。毎朝、上の正解の例をすべて実際に動かして確かめています。

multi_sort.php8.4.26 で 15 / 15 件の出力が正解と一致

<?php
// 標準入力の CSV を、指定した複数のキーで並べ替えて出す
$spec = $argv[1];

// 「<列>:<向き>:<比べ方>」をカンマで区切った指定を読む。形が違えばここで終わり
$keys = [];
foreach (explode(',', $spec) as $part) {
    $bits = explode(':', $part);
    if (count($bits) !== 3 || $bits[0] === ''
        || !in_array($bits[1], ['asc', 'desc'], true)
        || !in_array($bits[2], ['text', 'num'], true)) {
        echo "NG: 並べ方の指定が読めません\n";
        exit;
    }
    $keys[] = $bits;
}

// \r\n と \n のどちらでも区切り、空の行を落とす。残った最初の行が見出し
$lines = array_values(array_filter(preg_split('/\r?\n/', stream_get_contents(STDIN)), fn($l) => $l !== ''));
$header = $lines === [] ? [] : explode(',', $lines[0]);
$idx = [];
foreach ($keys as [$col, , ]) {
    // in_array や array_search は、第3引数を付けないと "0" と "" を同じとみなす
    $at = array_search($col, $header, true);
    if ($at === false) {
        echo "NG: 列 {$col} がありません\n";
        exit;
    }
    $idx[$col] = $at;
}

$rows = [];
$bad = 0;
foreach (array_slice($lines, 1) as $line) {
    $fields = explode(',', $line);
    if (count($fields) !== count($header)) {
        $bad++;
        continue;
    }
    $rows[] = [$line, $fields];
}

// 数として読めるのは「-?[0-9]{1,15}」の形だけ。読めなければ null(向きによらず後ろに置く)
$num = fn(string $s): ?int => preg_match('/^-?[0-9]{1,15}$/', $s) === 1 ? (int) $s : null;

// PHP 8.0 から usort は安定(同じと答えた行の順は変わらない)
usort($rows, function ($a, $b) use ($keys, $idx, $num) {
    foreach ($keys as [$col, $dir, $kind]) {
        $x = $a[1][$idx[$col]];
        $y = $b[1][$idx[$col]];
        if ($kind === 'num') {
            $nx = $num($x);
            $ny = $num($y);
            if ($nx === null && $ny === null) {
                $c = 0;
            } elseif ($nx === null) {
                return 1;
            } elseif ($ny === null) {
                return -1;
            } else {
                $c = $nx <=> $ny;
            }
        } else {
            // strcmp はバイトで比べる(UTF-8 なのでコードポイント順)。<=> は数字だけの文字列を数として比べるので使わない
            $c = strcmp($x, $y) <=> 0;
        }
        if ($c !== 0) {
            return $dir === 'desc' ? -$c : $c;
        }
    }
    return 0;
});

echo $lines[0] . "\n";
foreach ($rows as [$line, ]) {
    echo $line . "\n";
}
if ($bad > 0) {
    echo "読めない行 {$bad}\n";
}

動かし方(ファイルを保存したフォルダで)

$ php multi_sort.php dept:asc:text,salary:desc:num < input.txt

サンプルを持ち帰る

この書き方の10言語のプログラムと正解表を、zip でお送りします。利用条件を読んで同意のうえ、メールアドレスを入れてください。

持ち帰りの手続きへ

よく見かける書き方で試すと

仕事でよく見かける書き方(標準の関数をそのまま使う形や、よく紹介される正規表現など)を、同じ正解表で動かした結果です。言語を出した答えごとにまとめ、赤い字はその言語が実際に出した間違った行です。

入力よく見かける書き方の答え(10言語)
基本(部署の昇順、同じなら給与の降順)dept:asc:text,salary:desc:num

✓10言語すべて正解

数として比べる(文字として比べると 1000 が 900 より先になる)salary:asc:num

✓10言語すべて正解

キーの値がどれも同じ20行は、入力の順のまま(安定な並べ替え)dept:asc:text
  • C#r18,営業,100
    r17,営業,100
    r16,営業,100
    r15,営業,100
    r14,営業,100
    r13,営業,100
    r12,営業,100
    r11,営業,100
    r09,営業,100
    r08,営業,100
    r07,営業,100
    r06,営業,100
    r05,営業,100
    r04,営業,100
    r03,営業,100
    r02,営業,100
  • PHP・Python・Go・JavaScript・Java・Rust・Ruby・Kotlin・Swift✓ 正解
text の降順name:desc:text

✓10言語すべて正解

text はコードポイント順(UTF-16 の並びとは変わる)name:asc:text
  • JavaScript・Java・C#・Kotlin1,🍣
    2,¥
  • PHP・Python・Go・Rust・Ruby・Swift✓ 正解
数として読めない値は後ろ(読めない値同士は入力の順)salary:asc:num
  • PHP・JavaScript・C#・Kotlinb,
    e,100
    d,100
    f, 200
    a,300
    c,1e3
  • Pythonb,
    d,100
    e,100
    f, 200
    a,300
    c,1e3
  • Go・Rust・Swiftb,
    e,100
    f, 200
    d,100
    a,300
    c,1e3
  • Java・Rubye,100
    d,100
    f, 200
    a,300
    c,1e3
降順でも読めない値は後ろ。007 と 7、-0 と 0 は数として同じsalary:desc:num
  • Java・Kotline,0
    f,x
    d,-0
  • PHP・Python・Go・JavaScript・C#・Rust・Ruby・Swift✓ 正解
16桁の数は読めない扱い(15桁までが数)salary:asc:num

✓10言語すべて正解

3つのキーで並べるdept:asc:text,grade:asc:num,salary:desc:num

✓10言語すべて正解

列の数が違う行と空の行が混ざるsalary:asc:num
  • PHP・Python・Go・JavaScript・Java・C#・Rust・Ruby・Kotlin・Swift(何も出さなかった)
2つ目のキーが見出しに無いdept:asc:text,bonus:desc:num

✓10言語すべて正解

向きが asc でも desc でもないsalary:up:num

✓10言語すべて正解

空の入力dept:asc:text

✓10言語すべて正解

見出しだけ(データの行が無い)dept:asc:text

✓10言語すべて正解

改行が \r\n で、最後に改行が無いdept:asc:text,salary:desc:num

✓10言語すべて正解

この書き方の決まり

  • 引数は並べ方の指定1つ。「<列>:<向き>:<比べ方>」をカンマで区切って並べる(向きは asc か desc、比べ方は text か num。例 dept:asc:text,salary:desc:num)
  • 標準入力は CSV(1行目が見出し。値にカンマ・引用符・改行は入らない)
  • 1行目に見出しをそのまま出し、そのあとにデータの行を並べ替えて、元の行の文字列のまま1行ずつ出す
  • 指定した列を左から順に比べる。text は Unicode のコードポイントの小さい順(UTF-8 のバイトの並びの順と同じ)、num は数として小さい順。desc はその逆
  • 指定した列の値がどれも同じ行は、入力に出てきた順のまま(安定な並べ替え)
  • num は「-?[0-9]{1,15}」の形(符号は - だけ、桁は15桁まで)だけを数として読む。その形でない値(空・1e3・全角・前後に空白・16桁以上)は数として読めないものとして扱い、asc でも desc でも読めた値より後ろに置く(読めない値同士は入力の順のまま)
  • 値の前後の空白は取らない
  • 空の行は無いものとして捨てる。列の数が見出しと違う行は並べ替えず、その行は出さずに、最後に「読めない行 <数>」の1行を出す
  • まず指定の形を調べ、形が違ったら「NG: 並べ方の指定が読めません」の1行だけ。次に列を左から見て、最初に見つからなかった列の名前で「NG: 列 <名前> がありません」の1行だけ(空の入力は見出しが無いので、これになる)

解説

「同じ値の行」の順番は、並べ方の指定では決まらない

dept:asc:text だけで並べると、同じ部署の行の並びは並べ替えの実装が決めます。入力の順のまま残るか(安定)、入れ替わるか(安定でない)は言語ごとに違います。20行すべてのキーが同じ入力(c003)で、よく見かける書き方は検証に使っている Linux のコンテナでC# だけが順番を崩しました(先頭の行はそのままで、2行目以降が逆向きに並び、最後の2行だけ元の位置に残る形)。

言語既定の並べ替え安定か
Python・JavaScript・PHP・Java・Kotlin・Rustsort・sorted・usort・List.sort・sortedWith・sort_by安定(JavaScript は ES2019 から、PHP は 8.0 から)
Gosort.Slice安定ではない(sort.SliceStable が別にある)
Rubysort・sort_by安定ではない(仕様として決まっていない)
Swiftsorted(by:)安定ではない(仕様として決まっていない)
C#List.Sort・Array.Sort安定ではない(LINQ の OrderBy は安定)

Go・Swift は、この20行では順番が変わりませんでした。件数が少ないうちは挿入ソートで済むため、崩れないこともあるだけです。Ruby は同じ 4.0.7 でも、手元の Mac では15件中12件(c003 で先頭と末尾の行が入れ替わった)、コンテナでは15件中13件で、場所によって結果が変わりました。「今は順番が合っている」は、安定だという証拠になりません。

決めどころは2つです。出力の順番を最後まで決める(同じ値なら入力の順、あるいは id の順)か、安定な並べ替えを選ぶ(Go は SliceStable、C# は OrderBy、Ruby と Swift は「何番目に出てきたか」を最後の決め手に足す)。この回のコードは後者で書きました。

# Ruby: Array#sort は安定ではないので、何番目に出てきたかを最後の決め手に足す
rows.each_with_index.sort { |a, b| compare.call(a[0], b[0]).nonzero? || (a[1] <=> b[1]) }
// Swift: sorted(by:) も安定とは決まっていない
rows.enumerated().sorted { a, b in
    let c = compare(a.element.fields, b.element.fields, keys, idx)
    return c != 0 ? c < 0 : a.offset < b.offset
}

数として読めない値を、0 として並べてしまう(10言語中10言語)

給与の列に空・1e3・全角の100・前に空白が付いた 200を混ぜたケース(c006)は、よく見かける書き方が10言語すべて落ちました。しかも答えが4通りに割れました。

よく見かける書き方の答え(昇順)言語
-50 → (空) → 100 → 100 → 200 → 300 → 1e3PHP・JavaScript・C#・Kotlin(10言語中4言語)
-50 → (空) → 100 → 200 → 100 → 300 → 1e3Go・Rust・Swift
-50 → (空) → 100 → 100 → 200 → 300 → 1e3Python
-50 → 100 → 100 → 200 → 300 → 1e3(空の値の行が消えた)Java・Ruby
決まり(読めない値は後ろ)-50 → 100 → 300 → (空) → 1e3 → 100 → 200

言語ごとの数値変換のくせがそのまま出ています。

  • 空の値を 0 にする: PHP の (int)""、JavaScript の Number("")、Python の例外を拾って 0 にする書き方。0 は「いちばん小さい給与」として並ぶので、未入力の行が先頭に来ます
  • 1e3 を 1000 として読む: ほぼすべての言語の浮動小数の変換が受け付けます。1e3 と書かれた給与を 1000 として扱っていいかは仕様の話です
  • 前後の空白を飛ばす: Java の Double.parseDouble(" 200") と C#・Kotlin の変換は空白を飛ばして 200 にします。Go・Rust・Swift は断って 0 になりました
  • 全角の数字を読む言語がある: Python の float("100") は 100.0 を返します。他の9言語は読めずに 0 でした
  • 末尾の空の欄が消える: Java の String.split(",") と Ruby の split(",") は末尾の空の欄を捨てるので、b, の行は「列が1つしかない行」になり、行ごと消えました(第2引数に -1 を付けると残ります)

数の列を並べるときは、「どの形を数とみなすか」を先に決めて、その形だけを受けるのが安全です。この回のコードは -?[0-9]{1,15} を正規表現で確かめてから変換し、読めない値は向きによらず後ろに置きました。

// PHP: (int) に任せると "1e3" が 1000、" 200" が 200、"" が 0 になる
$num = fn(string $s): ?int => preg_match('/^-?[0-9]{1,15}$/', $s) === 1 ? (int) $s : null;

Java と Kotlin は -0 を 0 より小さいと答えた

10・7・007・-0・0・x を降順に並べたケース(c007)で、Java と Kotlin(10言語中2言語)だけが -0 を 0 の後ろに置きました。決まりでは -0 と 0 は数として同じなので、入力の順(-0 が先)のままです。

Double.compare(-0.0, 0.0) は -1 を返します。IEEE 754 の -0.0 == 0.0 は真ですが、Double.compare と Double.compareTo は「全順序」を作るために -0.0 < 0.0 と決めています。double で金額や件数を並べていると、マイナスの0が混ざった日に順番が変わります。

整数として扱える値なら、整数で比べるのが確実です(この回のコードは long・int64 で比べています。007 と 7、-0 と 0 はどちらも同じ値になります)。

文字の順は、UTF-16 で比べる4言語で変わる

text の比較で 私・¥・🍣 を並べたケース(c005)は、08 キーでまとめて数える と同じ割れ方になりました。

よく見かける書き方答え言語
決まり(コードポイント順)私 → ¥ → 🍣PHP・Python・Go・Ruby・Rust・Swift
UTF-16 の並び私 → 🍣 → ¥Java・Kotlin・JavaScript・C#(10言語中4言語)

🍣 は U+1F363、¥ は U+FFE5 です。この4言語の文字列は中身が UTF-16 で、🍣 は U+D83C U+DF63 のサロゲートペアとして入っているので、先頭の 0xD83C が 0xFFE5 より小さく、🍣 が先に来ます。UTF-8 のバイトの並びで比べ直すとコードポイント順になります。

C# の string.Compare は、さらに動かす場所の国の設定(カルチャ)に従います。検証に使っている Linux のコンテナは ICU(国ごとの並べ方の表)を持たない作りなので15件中11件でしたが、手元の Mac では漢字が辞書の順に並び、name:desc:text(c004)も落ちて15件中10件でした。機械が読む出力を作るときは、国の設定に左右されない比べ方を選びます。

壊れた行を黙って捨てる(10言語中10言語)

列が1つ足りない行と1つ多い行を混ぜたケース(c010)で、よく見かける書き方は10言語すべてが、その2行を黙って落とし、「読めない行 2」を出しませんでした。並べ替えの結果は決まりと同じなので、出力を見ても何も起きていないように見えます。

並べ替えは集計と違って合計が出ないので、行が減っても気づきにくいところです。読めなかった行の数を必ず出す(または標準エラーに出す)ようにしておくと、取り込みの元を直すきっかけになります。

元の行をそのまま出すか、組み立て直すか

この回は「元の行の文字列のまま出す」と決めました。欄に分けて並べ替えたあと join(",") で組み立て直すと、入力と1文字も同じにならないことがあります。末尾の空の欄が消える言語(Java・Ruby の split)や、空の欄をすべて捨てる言語(Swift の split(separator:))では、a,b, が a,b になって出てきます。

どちらでもよい場面は多いですが、「入力をそのまま並べ替えて返す」仕事(CSV の行の並べ替え、ログの整列)では、元の行を持ったまま並べ替えるほうが事故が起きません。