If maps can't be sorted in Go lang, what is the right way to do it?

Question

Let's say I have a string and I would like to count each letter's frequency and then sort the table by the frequency. Desired output of "hello larry" would be:

+--------+-----------+
| Letter | Occurence |
+--------+-----------+
| l      |         3 |
| r      |         2 |
| h      |         1 |
| e      |         1 |
| o      |         1 |
| a      |         1 |
| y      |         1 |
+--------+-----------+

First I thought I'll deal with this easily using map having the letters as keys. This is really easy. However, map items don't have an order hence can't be sorted.

I guess I could deal with this using a structure:

type Letter struct {
    Value string
    Score int
}
type LetterList []Letter

However that brings bunch of other problems:

1. I need to check if the Letter is not already present in LetterList because I can't use the letters as keys
2. There's no direct way to sort them (using Int.sort() or so)

Using the structures just doesn't feel elegant at all. Is there a better solution?

Answer 1

You would be surprised how fast and efficient looping over a small slice is, and you can implement sorting on top of it fairly simple.

I recommend reading http://golang.org/pkg/sort/ SortWrapper.

type Letter struct {
    Value rune
    Score int
}

type LetterList []*Letter

func (ll *LetterList) FindOrAdd(r rune) (l *Letter) {
    for _, l = range *ll {
        if l.Value == r {
            return
        }
    }
    l = &Letter{Value: r, Score: 0}
    *ll = append(*ll, l)
    return
}

func (ll LetterList) SortByScore() LetterList {
    sort.Sort(llByScore{ll})
    return ll
}

func (ll LetterList) SortByValue() LetterList {
    sort.Sort(llByValue{ll})
    return ll
}

func (ll LetterList) String() string {
    var b bytes.Buffer
    b.WriteByte('[')
    for _, v := range ll {
        b.WriteString(fmt.Sprintf("{%q, %d}, ", v.Value, v.Score))
    }
    b.WriteByte(']')
    return b.String()

}

func New(s string) (ll LetterList) {
    ll = LetterList{}
    for _, r := range s {
        ll.FindOrAdd(r).Score++
    }
    return
}

func (ll LetterList) Len() int      { return len(ll) }
func (ll LetterList) Swap(i, j int) { ll[i], ll[j] = ll[j], ll[i] }

type llByScore struct{ LetterList }

func (l llByScore) Less(i, j int) bool {
    return l.LetterList[i].Score > l.LetterList[j].Score
}

type llByValue struct{ LetterList }

func (l llByValue) Less(i, j int) bool {
    return l.LetterList[i].Value > l.LetterList[j].Value
}

func main() {
    ll := New(`Let's say I have a string and I would like to count each letter's frequency and then sort the table by the frequency. Desired output of "hello larry" would be`)
    fmt.Println(ll)
    fmt.Println(ll.SortByScore())
    fmt.Println(ll.SortByValue())
}

playground

Another approach is to use a map then for sorting generate a list out of it and sort it.