Go map排序的问题

问题
原因
解决
最终

问题

用户反馈说某个本来应该是某个顺序固定的列表，每次刷新顺序都不固定。原因可能是排序问题，追踪的时候发现了下面的代码（做了简化）

func testSortMap() []map[string]interface{} {
    normalMap := make(map[string]int, 0)
    result := make([]map[string]interface{}, 0)

    normalMap["a"] = 1
    normalMap["b"] = 2
    normalMap["c"] = 3

    for key, value := range normalMap {
        result = append(result, map[string]interface{}{
            "key": key,
            "value": value,
        })
    }

    return result
}

原因

实际的过程并不是在一个函数中完成的，还涉及到数据库的读取以及一些运算，刚开始的时候觉得返回的是一个 Slice，也很奇怪为什么会出现排序不固定的问题，又往下层追踪才发现实际上这个 Slice 是由一个 map 转换过来的。（也不知道当初为什么要这么设计），golang 中 map 默认是不排序的。所以下面的代码输出是不固定的：

func printMap() {
    normalMap := make(map[string]int, 0)

    normalMap["a"] = 1
    normalMap["b"] = 2
    normalMap["c"] = 3

    for key, value := range normalMap {
        fmt.Println(key, value)
    }
}

解决

至于为什么不固定，这里不深究，但如果只是要把 map 根据 value 来排序，可以通过写 len/less/swap 函数实现 sort 接口，来对 map 排序。

首先需要定义一个结构体：

type Pair struct {
    Key string
    Value int
}

type PairList []Pair

然后实现 sort 接口：

func (p PairList) Len() int { return len(p) }
func (p PairList) Less(i, j int) bool { return p[i].Value < p[j].Value }
func (p PairList) Swap(i, j int){ p[i], p[j] = p[j], p[i] }

最后就可以按照如下方法使用：

func rankByWordCount(wordFrequencies map[string]int) PairList{
    pl := make(PairList, len(wordFrequencies))
    i := 0
    for k, v := range wordFrequencies {
        pl[i] = Pair{k, v}
        i++
    }
    sort.Sort(sort.Reverse(pl))
    return pl
}

（以上代码来自：https://stackoverflow.com/questions/18695346/how-to-sort-a-mapstringint-by-its-values）同理可以修改上述代码按照 key 排序。

但问题也来了，上面的方法需要定义结构体，需要改动较多的代码。下面的代码可以比较“无痛”排序：

package main

import "fmt"
import "sort"

func main() {
    m := map[string]int{
        "One":   100,
        "Two":   2,
        "Three": 3,
        "Ten":   10,
        "Fifty": 50,
    }
    vs := NewValSorter(m)
    fmt.Printf("%v\n", *vs)
    vs.Sort()
    fmt.Printf("%v\n", *vs)
}

type ValSorter struct {
    Keys []string
    Vals []int
}

func NewValSorter(m map[string]int) *ValSorter {
    vs := &ValSorter{
        Keys: make([]string, 0, len(m)),
        Vals: make([]int, 0, len(m)),
    }
    for k, v := range m {
        vs.Keys = append(vs.Keys, k)
        vs.Vals = append(vs.Vals, v)
    }
    return vs
}

func (vs *ValSorter) Sort() {
    sort.Sort(vs)
}

func (vs *ValSorter) Len() int           { return len(vs.Vals) }
func (vs *ValSorter) Less(i, j int) bool { return vs.Vals[i] < vs.Vals[j] }
func (vs *ValSorter) Swap(i, j int) {
    vs.Vals[i], vs.Vals[j] = vs.Vals[j], vs.Vals[i]
    vs.Keys[i], vs.Keys[j] = vs.Keys[j], vs.Keys[i]
}

基本原理也是实现 sort 接口，简单版如下：

type sortedMap struct {
    m map[string]int
    s []string
}

func (sm *sortedMap) Len() int {
    return len(sm.m)
}

func (sm *sortedMap) Less(i, j int) bool {
    return sm.m[sm.s[i]] > sm.m[sm.s[j]]
}

func (sm *sortedMap) Swap(i, j int) {
    sm.s[i], sm.s[j] = sm.s[j], sm.s[i]
}

func sortedKeys(m map[string]int) []string {
    sm := new(sortedMap)
    sm.m = m
    sm.s = make([]string, len(m))
    i := 0
    for key, _ := range m {
        sm.s[i] = key
        i++
    }
    sort.Sort(sm)
    return sm.s
}

最终

本着“一定有更简洁的方法”原则，其实 golang（1.8之后）提供了 sort.Slice 函数，两行代码解决问题：

sort.Slice(ss, func(i, j int) bool {
    return ss[i].Value > ss[j].Value  // 降序
})

因为实际代码比例子中的复杂，实现上述几种比较复杂的方法有一定的难度，但是这个最终的解决方法非常契合需求，而且简单明了，所以记录一下。