time.Timeのsortのアルゴリズム説明をお願いします。

Question

https://golang.org/src/sort/sort.go?s=7650:7680#L287
https://qiita.com/yut-kt/items/ef8ce10c66153dd84317
https://gist.github.com/xigang/827e342fc2580198f625ce272257ef37

package main

import (
    "fmt"
    "sort"
    "time"
)

type reviews_data struct {
    review_id   string
    date        time.Time
    score       int
    firstname   string
    anonymous   bool
    review_text string
    title_text  string
    rating      float64
    upcount     int
}

type timeSlice []reviews_data

func (p timeSlice) Len() int {
    return len(p)
}

func (p timeSlice) Less(i, j int) bool {
    return p[i].date.Before(p[j].date)
}

func (p timeSlice) Swap(i, j int) {
    p[i], p[j] = p[j], p[i]
}

func main() {
    var reviews_data_map = make(map[string]reviews_data)
    reviews_data_map["1"] = reviews_data{date: time.Now().Add(12 * time.Hour)}
    reviews_data_map["2"] = reviews_data{date: time.Now()}
    reviews_data_map["3"] = reviews_data{date: time.Now().Add(24 * time.Hour)}
    //Sort the map by date
    date_sorted_reviews := make(timeSlice, 0, len(reviews_data_map))
    for _, d := range reviews_data_map {
        date_sorted_reviews = append(date_sorted_reviews, d)
    }
    fmt.Println(date_sorted_reviews)
    sort.Sort(date_sorted_reviews)
    fmt.Println(date_sorted_reviews)
}

timeをsortするときには、現状sort.Sliceが使われるとの事ですが、
sort.sliceを使わない方法の際出てくる、len,less,swapの存在が気にかかります。

これらは、function(関数)だと思われるのですが、どこで使われているのか？どのように使われているのかがわからなかったので教えて頂きたいです。
コード上では、定義はしているのに使用していないのではないかとも取れるのですがどうなんでしょうか？？

Answer 1

元々、Go の任意の型をソートする方法としては Len, Less, Swap を使った方法しか提供されていませんでした。

理由は2つあります。

(1) オブジェクト自身が「ソート可能である事」を明示する事ができるという設計
(2) 任意型のサイズを取得する為に reflect を使う必要がある為

(1) についてはデザインですから、それは Go らしさの話になります。(2) についてですが、Go は []int と []float を両方どちらでも取れる引数の型を定義する事が出来ません。どうしても両方どちらでも受け取る様にする為には interface{} で宣言しなければなりません。

interface{} で引数の型を宣言するという事は、引数に与えられたスライスの長さを調べる為に、reflect パッケージを使う必要があるという事です。reflect パッケージを使うとどうしても遅くなります。

Len, Less, Swap は自分の型がサイズを提供しているのですから、reflect を使う必要がなかったのです。

しかし多くのエンジニアはこの冗長とも言える Len, Less, Swap のインタフェースを使うのを面倒に感じていました。

そこで GitHub 上で議論が行われ、結果として若干遅くなったとしても便利さを取るべきだろうという理由で sort.Slice が追加されました。

https://github.com/golang/go/issues/16721

この時の経緯を僕のブログに書いてあります。

https://mattn.kaoriya.net/software/lang/go/20161004092237.htm

Answer 2

これらを定義することでソートする時呼ばれるようになるやつですね。
こちらの説明など分かりやすいでしょうか。
https://text.baldanders.info/golang/sort/

sort.Sort() 関数の内部では … Len(), Less(), Swap() 各メソッドが呼ばれている。

この sort.Interface インタフェースを持つ型であれば sort.Sort() 関数でソート可能ということになる。