对于给定的一组符文,你想要对其进行排序吗?

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

Go sort a slice of runes?

问题

我遇到了一个问题,需要按字符对字符串进行排序(为了检查两个字符串是否为变位词,我想要对它们进行排序,并检查是否相等)。

我可以这样将字符串s转换为[]rune表示:

runes := make([]rune, len(s)) 
copy(runes, []rune(s))

而且我可以这样对整数进行排序:

someInts := []int{5, 2, 6, 3, 1, 4} // 未排序
sort.Ints(someInts)

但是,rune只是int32的别名,所以我应该能够调用:

sort.Ints(runes)

然而,我得到了错误信息:

cannot use runes (type []rune) as type []int in function argument

那么...我该如何对int32int64int*的切片进行排序呢?

编辑:我确实对我的runes进行了排序,但是,这真的很丑陋。

type RuneSlice []rune

func (p RuneSlice) Len() int           { return len(p) }
func (p RuneSlice) Less(i, j int) bool { return p[i] < p[j] }
func (p RuneSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func sorted(s string) string {
    runes := []rune(s)
    sort.Sort(RuneSlice(runes))
    return string(runes)
}

所以,基本上,如果你有一个任意类型的切片,你将不得不将其包装在一个实现了sort.Interface接口的类型中。所有这些实现将具有完全相同的方法体(例如sort.IntSlicesort.Float64Slice)。如果这确实是这么丑陋的话,那为什么他们没有在sort包中提供这些WhateverSlice的包装器呢?泛型的缺失现在开始非常痛苦了。肯定有更好的排序方法。

英文:

I'm having trouble sorting strings by character (to check whether two strings are anagrams, I want to sort both of them, and check for equality).

I can get a []rune representation of the string s like this:

runes := make([]rune, len(s)) 
copy(runes, []rune(s))

And I can sort ints like this

someInts := []int{5, 2, 6, 3, 1, 4} // unsorted
sort.Ints(someInts)

But rune is just an alias for int32 so I should be able to call

sort.Ints(runes) 

However, I get the error:

cannot use runes (type []rune) as type []int in function argument

So... how do I sort a slice of int32, int64, or int*?

EDIT: I did get my runes sorted, but boy, this is ugly.

type RuneSlice []rune

func (p RuneSlice) Len() int           { return len(p) }
func (p RuneSlice) Less(i, j int) bool { return p[i] &lt; p[j] }
func (p RuneSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

func sorted(s string) string {
    runes := []rune(s)
    sort.Sort(RuneSlice(runes))
    return string(runes)
}

So basically if you have a slice of whatever, you'll have to wrap it in a type that implements sort.Interface. All those implementations will have the exact same method bodies (like sort.IntSlice and sort.Float64Slice). If this is really how ugly this has to be then why didn't they provide these WhateverSlice wrappers in the sort package? The lack of generics start to hurt very badly now. There must be a better way of sorting things.

答案1

得分: 7

使用sort.Sort(data Interface)并实现sort.Interface,请参考包文档中的示例。

你不能将runeint32)作为int使用。请查看int的注释

> int是一个至少有32位大小的有符号整数类型。然而,它是一个独立的类型,而不是int32的别名。

英文:

Use sort.Sort(data Interface) and implement sort.Interface, see the examples on package documentation.

You cannot use rune which is int32 as int. Check the comment of int.

> int is a signed integer type that is at least 32 bits in size. It is a
> distinct type, however, and not an alias for, say, int32.

答案2

得分: 5

注意:Go 1.8将引入用于对切片进行排序的辅助函数
参见问题16721提交22a2bdf,由Brad Fitzpatrick完成。

var strings = [...]string{"", "Hello", "foo", "bar", "foo", "f00", "%*&^*&^&", "***"}

func TestSlice(t *testing.T) {
    data := strings
    Slice(data[:], func(i, j int) bool {
        return data[i] < data[j]
    })
}
英文:

Note: Go 1.8 will introduce helpers for sorting slices.
See issue 16721 and commit 22a2bdf by Brad Fitzpatrick

var strings = [...]string{&quot;&quot;, &quot;Hello&quot;, &quot;foo&quot;, &quot;bar&quot;, &quot;foo&quot;, &quot;f00&quot;, &quot;%*&amp;^*&amp;^&amp;&quot;, &quot;***&quot;}

func TestSlice(t *testing.T) {
	data := strings
	Slice(data[:], func(i, j int) bool {
		return data[i] &lt; data[j]
	})
}

答案3

得分: 3

作为比较的一点,如果排序接口稍有不同,情况可能会如何呢?也就是说,如果接口不是在容器上,而是在元素上,会是什么样子呢?

package main

import (
	"fmt"
	"sort"
)

type Comparable interface {
	LessThan(Comparable) bool
}

type ComparableSlice []Comparable

func (c ComparableSlice) Len() int {
	return len(c)
}

func (c ComparableSlice) Less(i, j int) bool {
	return c[i].LessThan(c[j])
}

func (c ComparableSlice) Swap(i, j int) {
	c[i], c[j] = c[j], c[i]
}

func SortComparables(elts []Comparable) {
	sort.Sort(ComparableSlice(elts))
}

//////////////////////////////////////////////////////////////////////
// 让我们尝试使用这个:

type ComparableRune rune

func (r1 ComparableRune) LessThan(o Comparable) bool {
	return r1 < o.(ComparableRune)
}

func main() {
	msg := "Hello world!"

	comparables := make(ComparableSlice, len(msg))
	for i, v := range msg {
		comparables[i] = ComparableRune(v)
	}

	SortComparables(comparables)

	sortedRunes := make([]rune, len(msg))
	for i, v := range comparables {
		sortedRunes[i] = rune(v.(ComparableRune))
	}

	fmt.Printf("result: %#v\n", string(sortedRunes))
}

在这里,我们定义了一个Comparable接口,并使我们的类型ComparableRune满足它。但由于它是一个接口,我们必须进行笨拙的装箱,从rune转换为ComparableRune,以便动态分派可以启动:

comparables := make(ComparableSlice, len(msg))
for i, v := range msg {
	comparables[i] = ComparableRune(v)
}

并进行拆箱以恢复我们的符文:

sortedRunes := make([]rune, len(msg))
for i, v := range comparables {
	sortedRunes[i] = rune(v.(ComparableRune))
}

这种方法似乎要求我们知道如何进行类型转换,以在接口和值的动态类型之间来回转换。与将容器作为接口的方法相比,似乎需要使用更多的Go语言机制。

英文:

Just as a point of comparison, here's what things might look like if the sort interface were slightly different. That is, rather than the interface being on the container, what would things look like if the interface were on the elements instead?

package main

import (
	&quot;fmt&quot;
	&quot;sort&quot;
)

type Comparable interface {
	LessThan(Comparable) bool
}

type ComparableSlice []Comparable

func (c ComparableSlice) Len() int {
	return len(c)
}

func (c ComparableSlice) Less(i, j int) bool {
	return c[i].LessThan(c[j])
}

func (c ComparableSlice) Swap(i, j int) {
	c[i], c[j] = c[j], c[i]
}

func SortComparables(elts []Comparable) {
	sort.Sort(ComparableSlice(elts))
}

//////////////////////////////////////////////////////////////////////
// Let&#39;s try using this:

type ComparableRune rune

func (r1 ComparableRune) LessThan(o Comparable) bool {
	return r1 &lt; o.(ComparableRune)
}

func main() {
	msg := &quot;Hello world!&quot;

	comparables := make(ComparableSlice, len(msg))
	for i, v := range msg {
		comparables[i] = ComparableRune(v)
	}

	SortComparables(comparables)

	sortedRunes := make([]rune, len(msg))
	for i, v := range comparables {
		sortedRunes[i] = rune(v.(ComparableRune))
	}

	fmt.Printf(&quot;result: %#v\n&quot;, string(sortedRunes))
}

Here, we define a Comparable interface, and we get our type ComparableRune to satisfy it. But because it's an interface, we've got to do the awkward boxing to go from rune to ComparableRune so that dynamic dispatch can kick in:

	comparables := make(ComparableSlice, len(msg))
	for i, v := range msg {
		comparables[i] = ComparableRune(v)
	}

and unboxing to get back our runes:

	sortedRunes := make([]rune, len(msg))
	for i, v := range comparables {
		sortedRunes[i] = rune(v.(ComparableRune))
	}

This approach appears to require us to know how to do typecasts to go back and forth between the interface and the dynamic type of the value. It seems like we would need to use more parts of Go---more mechanics---than the approach that uses the container as the interface.

答案4

得分: 3

截至2020年11月,https://golang.org/pkg/sort/ 提供了使用作为闭包传递的自定义Less函数的选项。下面的代码具有所需的效果:

package main

import (
	"fmt"
	"sort"
)

func main() {

	s1 := "eidbaooo"

	runeSlice := []rune(s1)

	fmt.Println(string(runeSlice))

	sort.Slice(runeSlice, func(i, j int) bool {
		return runeSlice[i] < runeSlice[j]
	})
	
	fmt.Println(string(runeSlice))
}

输出:

eidbaooo
abdeiooo

这样可以避免完整的接口实现。

英文:

As of November 2020 at least, https://golang.org/pkg/sort/ offers to use a custom Less function passed as a closure. The code below has the desired effect:

package main

import (
	&quot;fmt&quot;
	&quot;sort&quot;
)

func main() {

	s1 := &quot;eidbaooo&quot;

	runeSlice := []rune(s1)

	fmt.Println(string(runeSlice))

	sort.Slice(runeSlice, func(i, j int) bool {
		return runeSlice[i] &lt; runeSlice[j]
	})
	
	fmt.Println(string(runeSlice))
}

Output:

eidbaooo
abdeiooo

This can spare you the full interface implementation.

答案5

得分: 2

实际上,有一种“软通用”的方法可以实现你想要的功能。

请查看以下软件包:

https://github.com/BurntSushi/ty/tree/master/fun

特别是以下文件:

https://github.com/BurntSushi/ty/blob/master/fun/sort_test.go

下面是使用示例:

tosort := []int{10, 3, 5, 1, 15, 6}

fun.Sort(func(a, b int) bool {
    return b < a
}, tosort)

该软件包中还实现了许多其他有趣的通用算法,通过反射来实现。

所有的功劳归功于@BurntSushi

英文:

There is, in fact a soft-generic way to do what you want.

Check out the following package:

> https://github.com/BurntSushi/ty/tree/master/fun

especially the following file:

> https://github.com/BurntSushi/ty/blob/master/fun/sort_test.go

Example of how it is used:

tosort := []int{10, 3, 5, 1, 15, 6}

fun.Sort(func(a, b int) bool {
    return b &lt; a
}, tosort)

There are lots of other interesting fun generic algorithms implemented through reflection in that package.

All credits go to @BurntSushi.

huangapple
  • 本文由 发表于 2013年8月11日 18:49:47
  • 转载请务必保留本文链接:https://go.coder-hub.com/18171136.html
匿名

发表评论

匿名网友

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

确定