Previous Entry Share Next Entry
Sorting Time in Go
anime
he_the_great

A while back I was having a discussion about Go on Reddit. I don't program in Go so I had to come up with a task so that I could come to grasp what Go offered for polymorphic functions. Let me relay that information.

The task is simply to sort Time. It is something I've done in D and frankly expected I'd have to "fake" having a hard time, but luckily Go didn't make it any easier for me (to the best of my knowledge). In fact I find the sort package is full of great examples demonstrating Go's polymorphic problems.

golang
package main

import "fmt"
import "time"
import "sort"

// Define us a type so we can sort it
type TimeSlice []time.Time

func main() {
    // Create slice of two times
    events := make([]time.Time, 2)
    // 4:30AM
    events[0], _ = time.Parse("15:04""04:30")
    // 3:12PM
    events[1], _ = time.Parse("15:04""15:12")
    // Wrap array in type for sorting
    sort.Sort(TimeSlice(events))
    
    fmt.Println(events)
}

// Forward request for length
func (p TimeSlice) Len() int {
    return len(p) }

// Define compare
func (p TimeSlice) Less(i, j int) bool {
    return p[i].Before(p[j]) }

// Define swap over an array
func (p TimeSlice) Swap(i, j int) {
    p[i], p[j] = p[j], p[i] }

Starting from the beginning it is required to define a type which is a slice of Time. I've chosen to call it TimeSlice. At this point, I can't figure out why it is required. I would have expected just using the normal []time.Time would be fine... but maybe that doesn't work with the magic Interface{} type.

golang
    // Create slice of two times
    events := make([]time.Time, 2)

I found it interesting that a built-in function takes a type. It makes me wonder if one could make there own functions which operate on types... but it's Go, so doubtful.

golang
    // 4:30AM
    events[0], _ = time.Parse("15:04""04:30")
    // 3:12PM
    events[1], _ = time.Parse("15:04""15:12")
    // Wrap array in type for sorting
    sort.Sort(TimeSlice(events))

Nothing unusual about the date parse or the request for sorting a TimeSlice. To make a sortable TimeSlice I need three functions, Len, Swap, and Less. None of which are provided for my new type.

golang
func (p TimeSlice) Len() int {
    return len(p) }

Len is a fairly simple function, it just calls len and forwards the answer.

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

The Less function isn't too bad, I just need to access the two elements and compare them, I've chosen the Before function in this case, but I can define it to be anything.

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

The Swap function isn't quite as simple as the others. One must be familiar with Go and understand the order of evaluation which this expression will follow. Or you can do what I did and copy it out of source code in the sort package and trust that the Go authors know what they are doing.

Copy Paste

You heard what I said. I did a copy and paste from the official standard library package. That is how I started with all three functions, the main changes was use making it take TimeSlice rather than IntSlice. The second biggest change was Less needed to use a function rather than <.

Now I was going to do that anyway just to get an understanding of what it was like to create a polymorphic function. What I wasn't expecting to find was a complete lack of these functions for time.Time. The time package doesn't define any sorting helpers.

Update: See comments for reference to SortWrapper which addresses this issue.

Sort Strategy

The sort strategy is pretty nice, since time doesn't have a provided sort, I can make the Less function do what I want. For example I can sort by After. There are many times a default sort is insufficient to the goals of the program.

What about sorting a TimeSlice in a couple different ways? I may need to give the user choice over how they desire to sort the data so I'll want a couple strategies available. To achieve this I'd have to define TimeSliceBefore, TimeSliceAfter, TimeSliceInbetween because I've already defined Less for TimeSlice. This means implementing 3 * 3 functions (5 right? only 5). Ok, it isn't that bad, I can setup my build to run cpp across my source first.

Update: Read comment section for proper implementation of these types (don't need swap or len each time)

IntSlice

Yes, IntSlice, Float64Slice, StringSlice. These are all provided by the sort package for your convenience. And if that isn't enough, they have the sort functions (e.g. ints()) which provides the ability to sort a slice without wrapping it in IntSlice first.

I can only imagine that sorting is not very common (at least not outside of, int, float, and string). I see this as something very discouraging, it makes the toy examples and probably much work straight forward. Then step outside of that comfort zone and you're hit with building everything yourself

Conclusion

Go does provide means for polymorphic functions. Functions can be written to operate on a number of different types and still provide type safety. I will get compile time errors if TimeSlice is missing a required function.

Go has absolutely no form of generics, it can't understand how to navigate a slice without also knowing the type inside the slice. And Go does not provide built-in Len/Less/Swap functions for slices.

I think this example is one which demonstrates why this is such a big problem in Go. Sorting is such a common operation, it can happen in many forms. I would expect there to be quit a bit of duplicate "helper" sort functions out there. Even C provides a function which can walk an array and sort it ignoring the type and using a compare function.

"We don't feel an urgency for them, although we understand some programmers do." -- FAQ


  • 1
> To achieve this I'd have to define TimeSliceBefore, TimeSliceAfter, TimeSliceInbetween because I've already defined Less for TimeSlice. This means implementing 3 * 3 functions (5 right? only 5).

This is simply not true, please check out the ▹ Example (SortWrapper) of package sort. You'll need to adjust the Less() method only for each TimeSliceBefore, TimeSliceAfter, etc. to satisfy the sort interface. Also check out the ▹ Example (SortKeys) for demonstration how one could implement sort by a custom closure.

Of course this should be much easier, but I suppose there were reasons to keep things as they are now. And it's not so bad as you've described.

SortWapper looks to address that specific problem, while SortKeys just looks to be the same original problem in a different light.

I have the below structure :

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

}

and the below declaration,

type timeSlice []reviews_data

Also I have used the same sort functions with a small change in the Less function
// Forward request for length
func (p timeSlice) Len() int {
return len(p)
}

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

// Define swap over an array
func (p timeSlice) Swap(i, j int) {
p[i], p[j] = p[j], p[i]
}

I have a map in golang(var reviews_data_map = make(map[string]reviews_data)) and I am sorting the date as mentioned;
//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)
}
sort.Sort(timeSlice(date_sorted_reviews))


The problem is that the result is not sorted, i will be highly obliged if you could resolve this problem.

Looks like it gets sorted to me: http://ideone.com/MWW6C5

If I try to just print the array of struct it seems to print a memory address for the date, but the score is being moved as would be expected. And I can call out each date to print with a for loop.

  • 1
?

Log in

No account? Create an account