Sort map keys by values

[Miki Tebeka]

Assuming I have a map[string]int, what's the easiest way to sort the keys by their values?
(In Python I'd do sorted(m, key=lambda k: m[k])).

[Kyle Lemons]

You could make an object that implements sort.Interface that does the usual thing, except swaps both the key and value in a list.

https://gist.github.com/1236125

[Andrew Gerrand]

// A data structure to hold a key/value pair.

type Pair struct {

  Key string

  Value int

}

// A slice of Pairs that implements sort.Interface to sort by Value.

type PairList []Pair

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

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

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

// A function to turn a map into a PairList, then sort and return it. 

func sortMapByValue(m map[string]int) PairList {

   p := make(PairList, len(m))

   i := 0

   for k, v := range m {

      p[i] = Pair{k, v}

   }

   sort.Sort(p)

   return p

}

[Andy Balholm]

Here's what I did recently. Unlike the other solutions proposed, it sorts only the keys. (I used descending order because I wanted to get the highest-scoring categories on top; if you want ascending order, make Less() use < instead of >.):

package main

// sort a map's keys in descending order of its values.

import "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

}

Note that the sortedMap type is private to this file; it is not intended to be used for long-term storage.

[Nigel Tao]

On 24 September 2011 01:24, Andy Balholm <andyb...@gmail.com> wrote:
> Here's what I did recently. Unlike the other solutions proposed, it sorts
> only the keys.

This is drifting off the topic of the original post, but
http://code.google.com/p/leveldb-go/source/browse/leveldb/memdb/memdb.go
offers a skiplist-backed equivalent of a sorted-by-key
map[[]byte][]byte. Use it as-is (but be aware that you'll have to
manually compact after deletions), or use the code as inspiration for
your own skiplist implementation.

[John Fries]

I think Andrew Gerrand's solution is the most idiomatic (or at least, it's the one I came up with too :)

Is this still the best way to solve this problem? I love Go, but this seems to be one of those (usually rare) cases where the Python version is 10x more concise :(

[Rodrigo Kochenburger]

I don't know why my other post got deleted, so here it is again:

Go does not give you everything out-of-the-box, instead it gives you a concise and simple language to build from, so it's a language that exploring and applying algorithms and data structure is really well suited. That said, it looks to me that what you want is a binary search tree (or balanced ordered binary tree).

It will have logarithmic insert/lookup time (hash map is constant), which should be good enough, but it will preserve order.

Here are some 3rd party implementations:

http://www.stathat.com/src/treap

https://code.google.com/p/go-wiki/wiki/Projects#Trees

Hope that helps.

[John Fries]

Nicely reframed! :)

I tend to be so wedded to manipulating slices and maps that I don't often think to use trees, but for my particular problem it looks like a better solution. I'll try it out.

[David DENG]

If you consider Andrew's solution too verbose, here's a short one (of cause not so short as Python).

var keys := make([]string, 0, len(m))

for k := range(m) {

    keys := append(keys, k)

}

villa.SortF(len(keys),

    func(i, j int)bool { return m[keys[i] < m[keys[j]] },

    func(i, j) { keys[i], keys[j] = keys[j], keys[i] })

villa.SortF is defined in githum.com/daviddengcn/go-villa, you can copy its source out if you don't want to import it.

David

[Kevin Gillette]

Even shorter would be:

keys := make([]string, 0, len(m))

for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)

Of course this is key sorting. The OP was concerned with sorting the keys according to the values (essentially sorting-by-proxy), which is different from what has recently been demonstrated.

[David DENG]

If you are talking my code fragment, it sorts keys by corresponding values. But yours is not. What's your point?

David

[wri...@ldlibra.com]

The gauntlet hath been thrown down.

[gerald...@gmail.com]

I think this should be added to: https://code.google.com/p/go-wiki/wiki/SliceTricks ??

[Anthony Voutas]

Andrew, you forgot to i++ in that loop and it took me way longer to realise than it should have. I think range has spoiled me. :P