在Go语言中按不同维度对点(结构体)进行排序。

huangapple go评论145阅读模式
英文:

sort points (structs) by different dimensions in go lang

问题

我有一个类型为Points的多维点列表。

我已经实现了sort.Sort接口,现在可以按y值进行排序。

例如:

type Points []*Point

func (points Points) Len() int {
    return len(points)
}
func (points Points) Less(i, j int) bool {
    return points[i].y < points[j].y
}
func (points Points) Swap(i, j int) {
    points[i], points[j] = points[j], points[i]
}

type Point struct {
    x int
    y int
    country_id int
}

现在我想按x值而不是y值对我的点进行排序。

我的想法是使用一个带有全局标志的if语句(在排序之前可以打开或关闭):

func (points Points) Less(i, j int) bool {
    if SORT_BY_X {
        return points[i].x < points[j].x
    }
    return points[i].y < points[j].y
}

有没有更好的方法来做到这一点?我应该多次实现Less方法吗?例如,如果我要按列对数据表进行排序呢?

英文:

I have a list of multidimensional points of type Points.

I've implemented the sort.Sort interface and can now sort by y value.

e.g.

type Points []*Point

func (points Points) Len() int {
	return len(points)
}
func (points Points) Less(i, j int) bool {
	return points[i].y &lt; points[j].y
}
func (points Points) Swap(i, j int) {
	points[i], points[j] = points[j], points[i]
}

type Point struct {
	x int
	y int
	country_id int
}

Now I want to sort my points by x value instead of y value.

My idea is to use an if statement with a global flag (which can be switched on or off before sorting):

func (points Points) Less(i, j int) bool {
    if SORT_BY_X {
        return points[i].x &lt; points[j].x
    }
    return points[i].y &lt; points[j].y
}

Is there a better way of doing this? Should I be implementing Less multiple times? What if I was sorting tables of data by columns for example?

答案1

得分: 7

啊,这很有趣:sort.Sort() 期望类型定义一个排序和一些数组操作。你可以有“可按X排序的点列表”和“可按Y排序的点列表”类型,但是它们共享数组操作的方式与其他语言不同,因为Go语言不使用继承。

我首先想到的方法是创建 XSortablePointsYSortablePoints 类型,它们分别独立实现 sort.Interface,并将你的 Points 实例转换为你当前需要的类型--参见这里:http://play.golang.org/p/9V3WlKjOwX。

然后nemo提供了一种更好的方法:类型嵌入允许 XSortablePointsYSortablePoints 共享数组操作的函数。此外,nemo没有将可排序类型保存在变量中,这是有道理的,因为它们只存在于这一个排序调用中。这是调整后的示例代码:http://play.golang.org/p/wNm-ilM18n

请注意,当你进行类型转换时,这两种方法都不会实际复制你的点数据,只会复制切片头部。你可以通过查看第一个示例中打印出的指针地址来验证这一点。

你还可以更高级一些:有一个接受任意比较函数的 Points.Sort 方法,参见:http://play.golang.org/p/4PmJVi2_7D。我认为只定义更多类型的蛮力方法在只有两三种排序方式时是可以接受的,但具体情况因人而异。请注意,对于比这里的点要大得多的类型,你可能希望定义比较函数接受指针而不是值,以避免复制。

关于 SORT_BY_X:我通常会避免全局的模式设置变量,因为这样的变量在程序运行时更新,很容易出问题。例如,也许你将来会有两个并行的 goroutine,当它们同时访问全局变量时就会出问题。或者也许某些代码在 SORT_BY_X 的初始值为 false 时工作正常,但某一天因为在另一个任务运行后它被设置为 true 而失败。如果你确实需要一个模式变量,想想是否可以将其作为函数参数或附加到一个对象上,而不是将其作为全局变量。

最后,可能已经有一些包提供了你想要的更高级功能。例如,这里列出了一些与地理数据相关的包:https://code.google.com/p/go-wiki/wiki/Projects#GIS

英文:

Ah, this is interesting: sort.Sort() expects the type to define an ordering and some array operations. You can have "X-sortable point list" and "Y-sortable point list" types, but making them share the array ops works differently from in other languages because Go doesn't use inheritance.

The first way I thought of is to create XSortablePoints and YSortablePoints types that each independently implement sort.Interface, and convert your Points instance to whichever one you need at the moment--see here: http://play.golang.org/p/9V3WlKjOwX.

Then nemo had a better way: type embedding allows XSortablePoints and YSortablePoints to share the functions for array operations. Also, nemo doesn't save the sortable types in a variable, which makes sense as they only exist for this one sort call. Here's adjusted sample code: http://play.golang.org/p/wNm-ilM18n

Note that neither of these approaches actually copies your point data when you cast, just the slice header. You can see that by looking at the pointer addresses printed out by the first example.

You can get fancier: there's a Points.Sort taking an arbitrary comparison function at http://play.golang.org/p/4PmJVi2_7D. I think the brute-force approach of just defining more types is fine as long as you only have two or three orderings, but situations vary. Note that for types much bigger than the points here, you might want to define the comparer to take pointers rather than values, to avoid copying.

re: SORT_BY_X: I'd generally avoid global mode-setting variables that you update as the program runs, because there are lots of ways those can come back to bite you. For example, maybe you'll have two parallel goroutines someday and then trouble happens when they both access the global at once. Or maybe some code will work when the initial value of SORT_BY_X is false, then someday fail because it was left true after another task ran. If you do find yourself needing a mode variable, figure out if, instead of it being global, you could make it a function parameter or attach it to an object.

Finally, there might be a package that already provides some of the higher-level functionality you want. For example, there are some packages related to geographic data listed here: https://code.google.com/p/go-wiki/wiki/Projects#GIS

答案2

得分: 6

除了user2714852的答案之外,你还可以使用与sort包中反向排序相同的技术:使用Less()定义进行屏蔽。

虽然这与之前提出的方法类似,但实现方式有些不同(play示例)。你可以定义你的点:

type Points []Point

func (points Points) Swap(i, j int) {
    points[i], points[j] = points[j], points[i]
}

func (points Points) Len() int {
    return len(points)
}

对于每种排序方法,你可以实现自己的类型,其中嵌入了你的Points类型:

type XPoints struct {
    Points
}

func (points XPoints) Less(i, j int) bool {
    return points.Points[i].x < points.Points[j].x
}

type YPoints struct {
    Points
}

func (points YPoints) Less(i, j int) bool {
    return points.Points[i].y < points.Points[j].y
}

现在你可以像这样使用不同的排序方法:

pts := Points{{1, 2, 3}, {2, 1, 3}}

sort.Sort(XPoints{pts})
fmt.Println("X-sorted points:", pts)

sort.Sort(YPoints{pts})
fmt.Println("Y-sorted points:", pts)
英文:

In addition to user2714852's answer, you can use the same technique as is already used for
reversing sorting in the sort package: shadowing the Less() definition.

While this is similar to what was already proposed, the way of getting there is
a bit different (example on play). You define your points:

type Points []Point

func (points Points) Swap(i, j int) {
	points[i], points[j] = points[j], points[i]
}

func (points Points) Len() int {
	return len(points)
}

And for each sorting method you implement your own type which embeds your Points type:

type XPoints struct {
	Points
}

func (points XPoints) Less(i,j int) bool {
	return points.Points[i].x &lt; points.Points[j].x
}

type YPoints struct {
	Points
}

func (points YPoints) Less(i, j int) bool {
	return points.Points[i].y &lt; points.Points[j].y
}

Now you can use the different sorting methods like this:

pts := Points{{1, 2, 3}, {2, 1, 3}}

sort.Sort(XPoints{pts})
fmt.Println(&quot;X-sorted points:&quot;, pts)

sort.Sort(YPoints{pts})
fmt.Println(&quot;Y-sorted points:&quot;, pts)

huangapple
  • 本文由 发表于 2013年11月4日 07:00:12
  • 转载请务必保留本文链接:https://go.coder-hub.com/19759274.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定