何気なくGoのsortパッケージのdocを眺めていたら、冒頭にこんな感じのサンプルが書かれていたんですよ。
sort.Slice(people, func(i, j int) bool {
return people[i].Age > people[j].Age
})
要素の大小関係を比較する関数が、compareとかcmpって名前じゃなくて、lessと名付けられていて、しかもbool値を返すようになっている！！
個人的にtimeのFormat構文レベルでびっくりしたんだけど、特にググってもびっくりしてる人が見当たらなかったので記事にまとめます。
※ちなみに経緯が調べきれなかったので、読み終わってもすっきりしない記事です！！
sortのcomparatorと言えばintじゃないの？！
ユーザー定義の比較関数を使って配列をソートする関数や機構は、さまざまな言語で実装されています。この比較関数、私が知っていた言語ではたいてい同じようなインターフェースでした。
function cmp($a, $b): int {
if ($a < $b) return -1;
if ($a > $b) return 1;
return 0;
}
翻訳するまでもないですが、3種類の値を返すことが求められます。
- a < b ならば 負の値
- a > b ならば 正の値
- a == b ならば 0
ちなみに数値同士だったら、単純に引き算することで実現できます。
function cmp(int $a, int $b): int {
return $a - $b;
}
ただ、文字列を辞書順比較するなど、comparator関数はよく必要になる割には行数が長いので、宇宙船演算子(<=>)と呼ばれる専用の演算子を用意している言語もあります。
参考: PHP7で宇宙船演算子を使いこなすぞ - Qiita
私はPHPが一番得意な言語なので、先にPHPの事例を書きましたが、
C言語も
void qsort(
void *base,
size_t nmemb,
size_t size,
int (*compar)(const void *, const void *)
);
JavaScriptのArray.prototype.sortも
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort
function compare(a, b) {
if (a is less than b by some ordering criterion) {
return -1;
}
if (a is greater than b by the ordering criterion) {
return 1;
}
// a must be equal to b
return 0;
}
Rustも
pub fn sort_by<F>(&mut self, mut compare: F)
where F: FnMut(&T, &T) -> Ordering
{
merge_sort(self, |a, b| compare(a, b) == Less);
}
やっぱり戻り値は正負とゼロの3種類の値を求めているケースが多いようです。
我が道を行くGo言語
そんな中、Goのsortパッケージは…
sort.Interfaceならこうだし、
type Interface interface {
// Len is the number of elements in the collection.
Len() int
// Less reports whether the element with
// index i should sort before the element with index j.
Less(i, j int) bool
// Swap swaps the elements with indexes i and j.
Swap(i, j int)
}
スライスをソートするときに便利なsort.Sliceはこうです。
func Slice(slice interface{}, less func(i, j int) bool)
徹底的に less という名前、そして戻り値はbool！！！
比較関数はcomparatorじゃないのか…
「同値判定をしなくて非効率にならないのか？」
lessというインターフェースのせいで、値が同じだという情報を使ってソートできないわけですから、非効率なのでは？という疑問が出てきます。
コンパイル言語としての高速性も重視しているgoが、そんな非効率なことをしているとは信じがたい…。
Goはセルフホスティングの言語ですので、この辺のアルゴリズムもgoで書かれています。ってわけで中身を読んでいくと、、、
- 標準のsortはクイックソート、要素数によってはヒープソートとシェルソートを使い分ける感じ
- クイックソートのピボット探しなどはLessだけで実装されている
当たり前ではあるんですが、Lessだけでアルゴリズムが実装できていますね。うーん。非効率なのかどうかよく分からん。
PHPの場合は？
このへんだけど、LLVMの実装を使っていると書いてある。(ライセンス込み)
https://github.com/php/php-src/blob/master/Zend/zend_sort.c#L317
…読んでいると、 cmp()==0 のケースを活用しているように見えない…
要素数が少ないときに発動する挿入ソートの方でも、安定ソートにもかかわらず特に活用がされていないように見える。
あれれ？
オレたちはなぜ…comparatorにこだわっていたのか！？
だんだんよく分からなくなってきました。。
- comparatorの同値判定を活用していないのは現状の偶然？
- 別のソートアルゴリズムなら活用する可能性がある？
- いろんな言語がcomparatorは3値を要求しているのはなぜ？
- 他の言語と揃えるため？
- 実はcomparatorが3値を返す必要はなかったんだよ！！ってのが事実ならすごい英断！と言えるんだけど、ちょっと判断つかない
- golangのsortパッケージ開発時の議論が知りたいけど調べ方がわからなかった
Gitをたどっていくと、最初の2008年のcommitが出てきたけど、すでにless方式のinterfaceになってた。
https://github.com/golang/go/commit/18852cf6d3f23a4fbcf2756836eb929283126827
追記: Goと同じくless方式の言語
C++のstd::sort
https://en.cppreference.com/w/cpp/algorithm/sort
同値判定は equiv(a, b), an expression equivalent to !comp(a, b) && !comp(b, a) でできると書いてある。まあそれはそうか。
https://en.cppreference.com/w/cpp/named_req/Compare
Swift
https://developer.apple.com/documentation/swift/array/2296801-sort