Rustのソートの理屈を大雑把に理解する
概要
備忘録も兼ねて、Rustのソートを調べた時の記録を残しておきます。
基本型のベクタを昇順ソートするだけならsort()
メソッドで事足りますが、少し複雑なことをしようとすると自前でソートのロジックを定義する必要があります。
あくまで大まかな理解のために必要な最低限の事柄のみに絞ります。
自前のロジックを定義する方法
比較関数の書き方
ソートのロジックを定義するには、sort_by()
といったソート用メソッドにクロージャーとして比較関数を渡します。
ソートに使用するメソッドは他にもいろいろありますが割愛。
例:構造体のベクタを特定のフィールドでソート
#[derive(Debug)]
struct Person {
name: String,
age: i32,
}
let mut people = vec![
Person{name: String::from("taro"), age: 28},
Person{name: String::from("jiro"), age: 14},
Person{name: String::from("hanako"), age: 28},
];
people.sort_by(|a, b| a.name.cmp(&b.name));
println!("{:?}", people); // [Person { name: "hanako", age: 28 }, Person { name: "jiro", age: 14 }, Person { name: "taro", age: 28 }]
比較関数にでてきたcmp()
メソッドは以下のようにOrdering
型のenumを返します。
-
a < b
ならばOrdering::Less
-
a = b
ならばOrdering::Equal
-
a > b
ならばOrdering::Greater
では、Ordering
とは?
Ordering
Ordering
は2つの値の比較結果を表現しており、次のように定義されています。
pub enum Ordering {
Less = -1,
Equal = 0,
Greater = 1,
}
sort_by()
メソッドは比較関数の引数a, b
に対し返ってくる値に応じて要素の大小関係を把握し、ソートを実行します。
-
Less
ならばa
がb
より前に位置する -
Greater
ならばa
がb
より後に位置する -
Equal
ならば元の順番を維持(ただし、これはsort_by()
が安定ソートであるためで、不安定ソートを実行するメソッドでは保証されないと考えられます)
実例
理解を深めるためにいくつかの例に当たってみます。
降順ソート
reverse()
メソッドは以下のようにOrdering
を変換するため、順番が逆になり降順でソートできます。
-
Less
->Greater
-
Greater
->Less
-
Equal
->Equal
let mut numbers = vec![1, 5, 3, 2];
// 降順ソート
numbers.sort_by(|a, b| a.cmp(&b).reverse());
println!("{:?}", numbers); // [5, 3, 2, 1]
もちろんreverse()
を使わずとも次のように実装することもできます。
numbers.sort_by(|a, b| b.cmp(&a));
複数キーでソート
then()
によってOrdering
をつなげることができます。
let mut people = vec![
Person{name: String::from("taro"), age: 28},
Person{name: String::from("jiro"), age: 14},
Person{name: String::from("hanako"), age: 28},
];
people.sort_by(|a, b| a.age.cmp(&b.age).then(a.name.cmp(&b.name)));
println!("{:?}", people); // [Person { name: "jiro", age: 14 }, Person { name: "hanako", age: 28 }, Person { name: "taro", age: 28 }]
この例ではage
> name
の優先順位でソートしています。すなわち、age
が同じ人達の中での並び順はname
の辞書順となっています。
Ordering
型であるo1
とo2
に対しo1.then(&o2)
のようにthen()
を呼んだ時、then()
は
-
o1
がEqual
以外(Less
またはGreater
) ならばo1
を返す -
o1
がEqual
ならばo2
を返す
という働きをします。
すなわち、上の例においては
-
a.age.cmp(&b.age)
がEqual
でない場合(age
が異なる場合)-> 比較関数はa.age.cmp(&b.age)
の結果を返す(age
の比較結果を元に順番を決める) -
a.age.cmp(&b.age)
がEqual
の場合(age
が等しい場合)-> 比較関数はa.name.cmp(&b.name)
の結果を返す(name
の比較結果を元に順番を決める)
となります。そのため、age
、name
という2つのキーを用いてソートすることができるのです。
まとめ
Ordering
の働きがわかればいろいろ応用が効きそうです。
Discussion