问题 去排序一片符文?


我无法按字符排序字符串(检查两个字符串是否为字谜,我想对它们进行排序,并检查是否相等)。

我可以得到一个 []rune 字符串的表示 s 喜欢这个:

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

我可以像这样排序

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

rune 只是一个别名 int32 所以我应该可以打电话

sort.Ints(runes) 

但是,我得到错误:

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

那么......我如何对int32,int64或int *进行排序?

编辑:我确实把我的符文分类了,但男孩,这很难看。

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.IntSlice 和 sort.Float64Slice)。如果这真的是多么难看,那么为什么他们不提供这些WhateverSlice包装 sort 包?缺乏仿制药现在开始受到非常严重的伤害。必须有更好的方法来分类。


2036
2017-08-11 10:49


起源

是的,这是对DRY的可怕违反。我的意思是完全相同的代码复制很多次,因为基本类型非常糟糕。在没有任何额外拼接的情况下处理基本类型的通用排序算法几乎就是您对任何语言的期望。但是必须教会编译器如何获得切片长度20次才是不真实的。 - andras
你完全错过了这一点。通用排序算法不仅适用于切片,也适用于切片 什么 满意的 sort.Interface。现在,你如何建议自动获得 Len 和朋友们 什么 你懂 没有 提前(在编译时)???呃,你的咆哮不合理。 - zzzz
我不希望编译器能够排序 BucketOfFish 开箱即用的实例。 sort.Interface 对于这些情况来说,这似乎是一个很好的抽象(尽管我可能也希望将我的Fishes保留在切片中,而不是一些自定义容器)。我发现奇怪的是,标准库没有涵盖这样一个基本用例(基本类型的切片)。 - andras
你的 make 声明应该使用 utf8.RuneCountInString (从 unicode/utf8) 而不是 len; len 计算字节数,而不是符文数。 - Brad Ackerman
实际上类型转换也有效! len([] rune(someString))与utf8.RuneCountString(更少的导入)产生相同的效果,但对于anagram解算器,它在99%的情况下无关紧要。所有utf8字符的字节相同的colision是不太可能的(虽然可能)。 - Phrozen


答案:


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

你不能用 rune 是的 int32 如 int。检查 评论 的 int

int是有符号整数类型,其大小至少为32位。它是一个   但是,不同的类型,而不是int32的别名。


6
2017-08-11 11:12



我检查了sort.go,这就是我最终做的事情,但是请继续!我真的必须实现RuneSlice,ByteSlice,Int32Slice,UintSlice等等吗?这些方法体完全相同的3种方法!如果这实际上是除了int和float64切片之外的切片排序的唯一方法,那么为什么他们不在sort.go中实现这些WhateverSlice类型?无论如何,我最终会在我的utils中实现它们。这是因为缺乏仿制药吗?来吧,必须有更好的方法。 - andras
@andras这是一个很好的问题。我会把它放在StackOverflow上。 - Grzegorz Żur
@andras:看 godoc.org/github.com/cznic/sortutil#RuneSlice - zzzz
@jnml谢谢,至少这是件事。可能想发一个答案,以便我接受它。顺便说一句,我用google搜索“golang sort util”但没找到这个包。你如何寻找golang套餐? - andras
安德拉什: code.google.com/p/go-wiki/wiki/Projects 似乎是寻找优质第三方套餐的好地方。 - dyoo


实际上有一个 软通用 做你想做的事。

查看以下包:

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


3
2017-08-12 10:10



谢谢,这看起来很有用。它似乎在运行时使用反射强制类型安全? (或黑魔法,就此而言,因为我无法绕过源代码:) - andras


作为一个比较点,如果排序界面略有不同,这里的内容可能会是什么样子。也就是说,而不是界面上 容器,如果界面在上面会是什么样子 分子 代替?

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))
}

//////////////////////////////////////////////////////////////////////
// Let's try using this:

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的更多部分 - 更多的机制 - 而不是使用容器作为接口的方法。


2
2017-08-11 19:57



谢谢你!这很有用(虽然仍然没有实际可用:)。至少我看到你将如何用Java风格做到这一点。尽管如此,缺乏仿制药(一篮子苹果不是一篮子水果)使解决方案变得不可行。 - andras
对!但是至少就目前而言,让我们保留关于仿制药的说明。否则,这个问题可能会转变为“为什么不支持泛型?!”,这是我们无法有效回答的问题。会非常的 不错 如果它确实(也许),但这里提出的解决方案似乎是使用非常一般的正确方法 sort.Sort 例程以及Go的当前类型系统如何影响其使用。 - dyoo
你是对的,我并不是说这是“为什么不像X语言一样?”。我想学习惯用Go,但必须实施 sort.Interface对于基本类型感到如此奇怪,以为我一定做错了。也许及时我会学习Go的方式,这个问题不会打扰我那么多:) - andras


注意:去1.8会 引入帮助器来分类切片
看到 问题16721 和 提交22a2bdf 通过 布拉德菲茨帕特里克

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]
    })
}

2
2017-10-04 20:08



beta.golang.org/pkg/sort/#Slice - robert king