CODEWITHSUNDEEP
sortinggo
RisingSun
RisingSun

Reputation: 1733

Golang Sort adds extra values to map

type GeoNameTally struct {
    Id    uint32
    Count uint32
}

type Tally map[uint32]GeoNameTally

Above are the structs i have. The idea is pretty simple. I'm just tallying how many times something occurs.

func (t Tally) Len() int           { return len(t) }
func (t Tally) Less(i, j int) bool { return t[uint32(i)].Count < t[uint32(j)].Count }
func (t Tally) Swap(i, j int)      { t[uint32(i)], t[uint32(j)] = t[uint32(j)], t[uint32(i)] }

Everything works perfectly fine until I get to the sort. Right before sort, the map looks fine: 

map[1043487:{Id:1043487 Count:1} 1043503:{Id:1043503 Count:1} 1043444:{Id:1043444 Count:1} 1043491:{Id:1043491 Count:1} 1043459:{Id:1043459 Count:1} 1043475:{Id:1043475 Count:1} 1043464:{Id:1043464 Count:1} 1043441:{Id:1043441 Count:1} 1043470:{Id:1043470 Count:1} 1043460:{Id:1043460 Count:1}]

However right after sort.Sort(myTally) the map has extra and empty values as you can see from the following output:

map[1043503:{Id:1043503 Count:1} 1043491:{Id:1043491 Count:1} 1043459:{Id:1043459 Count:1} 1043475:{Id:1043475 Count:1} 4:{Id:0 Count:0} 8:{Id:0 Count:0} 1043487:{Id:1043487 Count:1} 1:{Id:0 Count:0} 5:{Id:0 Count:0} 9:{Id:0 Count:0} 1043470:{Id:1043470 Count:1} 2:{Id:0 Count:0} 6:{Id:0 Count:0} 1043444:{Id:1043444 Count:1} 1043441:{Id:1043441 Count:1} 1043460:{Id:1043460 Count:1} 3:{Id:0 Count:0} 7:{Id:0 Count:0} 1043464:{Id:1043464 Count:1}]

Have I done something wrong to the 3 functions?

Upvotes: 0

Views: 452

Answers (2)

Franck Jeannin
Franck Jeannin

Reputation: 6844

As of Go 1.8, there is an easier way to sort a slice that does not require you to define new types. You simply create a Less (anonymous) lambda.

a := []int{5, 3, 4, 7, 8, 9}
sort.Slice(a, func(i, j int) bool {
    return a[i] < a[j]
})
for _, v := range a {
    fmt.Println(v)
}

Upvotes: 0

thwd
thwd

Reputation: 24848

You're passing inexistent indexes to Swap(i, j).

A map type is composite. It is defined in terms of 2 other types: the key type and the value type. Example:

map[string]bool

In the previous example, string is the key type, bool is the value type.

As you may know, map access returns 1 or 2 values. In a 1 return value context like yours, a map access will return the zero-value for the map's value type when given an inexistent index.

This means that if you access m["im_not_defined"] on some map m of type map[string]bool, you'll get a return value that is the zero-value for bool (the map's value type).

You can check if the indexes are defined by doing (inside Swap):

if a, k := t[uint32(i)]; k {
    t[uint32(j)] = a
} else {
    panic("undefined index")
}

And analogously for j.

So basically, if i is undefined, the zero-value of GeoNameTally is assigned to t[j] and that causes your "empty" (zero) values.

Anyhow, if you want to sort anything, you'll have to use a slice. A map is unordered by definition.

Upvotes: 4

Related Questions