如何定义自定义字母顺序以便在go中比较和排序字符串？

Question

在将此标记为重复之前,请先阅读底部

我希望能够按字母顺序排序字符串数组(或基于一个字符串值的结构片),但基于自定义字母或unicode字母.

大多数时候,人们建议使用支持不同预定义语言环境/字母表的collat​​or.(请参阅Java的这个答案),但是对于这些语言环境包中没有的稀有语言/字母表可以做些什么呢？

我想要使​​用的语言在Golangs的整理支持和使用的语言列表中不可用 ,因此我需要能够定义自定义字母或Unicode字符/符文的顺序以进行排序.

其他人建议首先将字符串翻译成英文/ ASCII可排序字母,然后对其进行排序.这就是用Javascript或Ruby中的这个解决方案完成的这个解决方案中的类似问题.但是肯定必须有一种更有效的方法来实现Go.

是否可以在Go中创建使用自定义字母/字符集的Collat​​or？这是Func NewFromTable的用途吗？

似乎我应该可以使用重新排序功能,但看起来这还没有在语言中实现？的源代码显示了此:

func Reorder(s ...string) Option {
    // TODO: need fractional weights to implement this.
    panic("TODO: implement")
}

如何定义自定义字母顺序以便在go中比较和排序字符串？

Answer 1

事先注意：

以下解决方案已被清理和优化，并作为可重用的库在此处发布：github.com/icza/abcsort.

使用abcsort，自定义排序字符串切片（使用自定义字母表）非常简单：

sorter := abcsort.New("bac")

ss := []string{"abc", "bac", "cba", "CCC"}
sorter.Strings(ss)
fmt.Println(ss)

// Output: [CCC bac abc cba]

通过 struct 字段之一对结构切片进行自定义排序如下：

type Person struct {
    Name string
    Age  int
}

ps := []Person{{Name: "alice", Age: 21}, {Name: "bob", Age: 12}}
sorter.Slice(ps, func(i int) string { return ps[i].Name })
fmt.Println(ps)

// Output: [{bob 12} {alice 21}]

原答案如下：

我们可以实现使用自定义字母表的自定义排序。我们只需要创建合适的less(i, j int) bool函数，剩下的就交给sort包了。

问题是如何创建这样的less()函数？

让我们从定义自定义字母表开始。方便的方法是创建一个string包含自定义字母表的字母，从最小到最高枚举（有序）。例如：

const alphabet = "bca"

让我们从这个字母表创建一个地图，它会告诉我们自定义字母表的每个字母的重量或顺序：

var weights = map[rune]int{}

func init() {
    for i, r := range alphabet {
        weights[r] = i
    }
}

^{（注意：i在上面的循环中是字节索引，而不是rune索引，但由于两者都是单调递增的，两者都可以很好地处理符文权重。）}

现在我们可以创建我们的less()函数了。为了获得“可接受”的性能，我们应该避免将输入string值转换为字节或符文切片。为此，我们可以从utf8.DecodeRuneInString()解码 a 的第rune一个的函数调用帮助string。

所以我们逐个比较符文。如果两个符文都是自定义字母表中的字母，我们可以使用它们的权重来判断它们如何相互比较。如果至少有一个符文不是来自我们的自定义字母表，我们将退回到简单的数字符文比较。

如果 2 个输入字符串开头的 2 个符文相等，我们继续处理每个输入字符串中的下一个符文。我们可以通过对输入字符串进行切片来执行此操作：对它们进行切片不会生成副本，它只会返回一个指向原始字符串数据的新字符串标头。

好了，现在我们来看看这个less()函数的实现：

func less(s1, s2 string) bool {
    for {
        switch e1, e2 := len(s1) == 0, len(s2) == 0; {
        case e1 && e2:
            return false // Both empty, they are equal (not less)
        case !e1 && e2:
            return false // s1 not empty but s2 is: s1 is greater (not less)
        case e1 && !e2:
            return true // s1 empty but s2 is not: s1 is less
        }

        r1, size1 := utf8.DecodeRuneInString(s1)
        r2, size2 := utf8.DecodeRuneInString(s2)

        // Check if both are custom, in which case we use custom order:
        custom := false
        if w1, ok1 := weights[r1]; ok1 {
            if w2, ok2 := weights[r2]; ok2 {
                custom = true
                if w1 != w2 {
                    return w1 < w2
                }
            }
        }
        if !custom {
            // Fallback to numeric rune comparison:
            if r1 != r2 {
                return r1 < r2
            }
        }

        s1, s2 = s1[size1:], s2[size2:]
    }
}

让我们看看这个less()函数的一些琐碎测试：

pairs := [][2]string{
    {"b", "c"},
    {"c", "a"},
    {"b", "a"},
    {"a", "b"},
    {"bca", "bac"},
}
for _, pair := range pairs {
    fmt.Printf("\"%s\" < \"%s\" ? %t\n", pair[0], pair[1], less(pair[0], pair[1]))
}

输出（在Go Playground上试试）：

"b" < "c" ? true
"c" < "a" ? true
"b" < "a" ? true
"a" < "b" ? false
"bca" < "bac" ? true

现在让我们less()在实际排序中测试这个函数：

ss := []string{
    "abc",
    "abca",
    "abcb",
    "abcc",
    "bca",
    "cba",
    "bac",
}
sort.Slice(ss, func(i int, j int) bool {
    return less(ss[i], ss[j])
})
fmt.Println(ss)

输出（在Go Playground上试试）：

[bca bac cba abc abcb abcc abca]

同样，如果性能对你很重要，你不应该使用sort.Slice()因为它必须在引擎盖下使用反射，而是创建你自己的切片类型来实现sort.Interface，并且在你的实现中你可以知道如何在不使用反射的情况下做到这一点。

这是它的样子：

type CustStrSlice []string

func (c CustStrSlice) Len() int           { return len(c) }
func (c CustStrSlice) Less(i, j int) bool { return less(c[i], c[j]) }
func (c CustStrSlice) Swap(i, j int)      { c[i], c[j] = c[j], c[i] }

当您想使用自定义字母表对字符串切片进行排序时，只需将您的切片转换为CustStrSlice，这样它就可以直接传递给sort.Sort()（这种类型转换不会复制切片或其元素，它只是更改类型信息）：

ss := []string{
    "abc",
    "abca",
    "abcb",
    "abcc",
    "bca",
    "cba",
    "bac",
}
sort.Sort(CustStrSlice(ss))
fmt.Println(ss)

上面的输出又是（在Go Playground上试试）：

[bca bac cba abc abcb abcc abca]

一些注意事项：

默认字符串比较按字节比较字符串。也就是说，如果输入字符串包含无效的 UTF-8 序列，仍将使用实际字节。

我们的解决方案在这方面有所不同，因为我们解码符文（我们必须这样做，因为我们使用自定义字母表，其中允许符文不一定映射到 UTF-8 编码中的 1 对 1 字节）。这意味着如果输入不是有效的 UTF-8 序列，则行为可能与默认顺序不一致。但是，如果您的输入是有效的 UTF-8 序列，这将执行您期望的操作。

最后一点：

我们已经看到了如何自定义排序字符串切片。如果我们有一个结构体切片（或结构体指针的切片），排序算法（less()函数）可能是一样的，但是在比较切片的元素时，我们必须比较元素的字段，而不是结构体元素他们自己。

所以假设我们有以下结构：

type Person struct {
    Name string
    Age  int
}

func (p *Person) String() string { return fmt.Sprint(*p) }

^{（String()添加了该方法，因此我们将看到结构的实际内容，而不仅仅是它们的地址......）}

假设我们想[]*Person使用元素的Name字段在type 的切片上应用我们的自定义排序Person。所以我们简单地定义这个自定义类型：

type PersonSlice []*Person

func (p PersonSlice) Len() int           { return len(p) }
func (p PersonSlice) Less(i, j int) bool { return less(p[i].Name, p[j].Name) }
func (p PersonSlice) Swap(i, j int)      { p[i], p[j] = p[j], p[i] }

就这样。其余相同，例如：

ps := []*Person{
    {Name: "abc"},
    {Name: "abca"},
    {Name: "abcb"},
    {Name: "abcc"},
    {Name: "bca"},
    {Name: "cba"},
    {Name: "bac"},
}
sort.Sort(PersonSlice(ps))
fmt.Println(ps)

输出（在Go Playground上试试）：

[{bca 0} {bac 0} {cba 0} {abc 0} {abcb 0} {abcc 0} {abca 0}]