在将其标记为重复之前,请阅读底部
我希望能够按字母顺序排序字符串数组(或基于一个字符串值的结构片段),但基于自定义字母表或 unicode 字母。
大多数时候,人们建议使用支持不同预定义语言环境/字母表的整理器。 (请参阅 this answer for Java ),但是对于这些语言环境包中不可用的稀有语言/字母表可以做什么?
我想使用的语言 不可用 in the list of languages Golangs collate 支持和使用,所以我需要能够定义一个自定义字母表,或用于排序的 Unicode 字符/ rune 顺序。
其他人建议先将字符串翻译成英文/ASCII 可排序的字母表,然后再排序。这就是 this solution done in Javascript 中的类似问题所建议的。或 this solution in Ruby . 但是肯定必须有一种更有效的方法来使用 Go 来做到这一点。
是否可以创建一个 Collator在使用自定义字母/字符集的 Go 中?那是什么func NewFromTable是为了?
看来我应该可以用Reorder功能,但看起来这还没有在语言中实现? source code显示这个:
func Reorder(s ...string) Option {
// TODO: need fractional weights to implement this.
panic("TODO: implement")
}
我该怎么办 定义用于比较和排序字符串的自定义字母顺序 在走吗?
最佳答案
事先说明:
以下解决方案已被清理和优化,并作为可重用库在此处发布: github.com/icza/abcsort
.
使用 abcsort
,自定义排序字符串 slice (使用自定义字母表)非常简单:
sorter := abcsort.New("bac")
ss := []string{"abc", "bac", "cba", "CCC"}
sorter.Strings(ss)
fmt.Println(ss)
// Output: [CCC bac abc cba]
通过 struct 字段之一对结构 slice 进行自定义排序如下:
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"
让我们从这个字母表创建一个 map ,它会告诉我们自定义字母表的每个字母的重量或顺序:
var weights = map[rune]int{}
func init() {
for i, r := range alphabet {
weights[r] = i
}
}
(注意:上述循环中的
i
是字节索引,而不是 rune
索引,但由于两者都是单调递增的,因此两者都可以很好地处理 rune 权重。)现在我们可以创建我们的
less()
功能。为了获得“可接受”的性能,我们应该避免转换输入 string
值到字节或 rune slice 。为此,我们可以拨打 utf8.DecodeRuneInString()
的帮助电话。解码第一个 rune
的函数的 string
.所以我们逐个比较 rune 。如果两个 rune 都是自定义字母表中的字母,我们可以使用它们的权重来判断它们如何相互比较。如果至少有一个 rune 不是来自我们的自定义字母表,我们将退回到简单的数字 rune 比较。
如果 2 个输入字符串开头的 2 个 rune 相等,我们继续处理每个输入字符串中的下一个 rune 。我们可以通过对输入字符串进行 slice 来执行此操作:对它们进行 slice 不会生成副本,它只会返回一个指向原始字符串数据的新字符串 header 。
好的,现在让我们看看这个
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()
因为它必须在引擎盖下使用反射,而是创建自己的 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] }
当您想使用自定义字母表对字符串 slice 进行排序时,只需将 slice 转换为
CustStrSlice
,所以可以直接传给 sort.Sort()
(此类型转换不会复制 slice 或其元素,它只会更改类型信息):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 序列,仍将使用实际字节。
我们的解决方案在这方面有所不同,因为我们解码 rune (我们必须这样做,因为我们使用自定义字母表,其中允许 rune 不一定映射到 UTF-8 编码中的 1 对 1 字节)。这意味着如果输入不是有效的 UTF-8 序列,则行为可能与默认顺序不一致。但是,如果您的输入是有效的 UTF-8 序列,这将执行您期望的操作。
最后一点:
我们已经看到了如何自定义排序字符串 slice 。如果我们有一个结构体 slice (或者一个结构体指针的 slice ),排序算法(
less()
函数)可能是一样的,但是在比较 slice 的元素时,我们必须比较元素的字段,而不是结构元素本身。所以假设我们有以下结构:
type Person struct {
Name string
Age int
}
func (p *Person) String() string { return fmt.Sprint(*p) }
(添加了
String()
方法,所以我们将看到结构的实际内容,而不仅仅是它们的地址......)假设我们想在
[]*Person
类型的 slice 上应用我们的自定义排序。 ,使用 Name
领域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}]
关于string - 如何定义自定义字母顺序以在 go 中比较和排序字符串?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/53902528/