Заранее обратите внимание:
Следующее решение было очищено и оптимизировано и опубликовано здесь как библиотека многократного использования: 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]
Выборочная сортировка фрагмента структуры одним из полей структуры выглядит следующим образом:
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(), которая декодирует первые 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, фактические байты все равно будут использоваться.
Наше решение отличается в этом отношении, поскольку мы декодируем руны (мы должны это сделать, потому что мы используем собственный алфавитв котором мы разрешаем руны, которые не обязательно отображаются на байты 1-в-1 в кодировке UTF-8).Это означает, что если ввод не является допустимой последовательностью UTF-8, поведение может не соответствовать порядку по умолчанию.Но если ваши входные данные являются действительными последовательностями UTF-8, это будет делать то, что вы ожидаете.
Последнее замечание:
Мы видели, как можно отсортировать фрагмент строки.Если у нас есть фрагмент структур (или фрагмент указателей структур), алгоритм сортировки (функция less()) может быть таким же, но при сравнении элементов фрагмента мы должны сравнивать поля элементов, а несами элементы структуры.
Итак, допустим, у нас есть следующая структура:
type Person struct {
Name string
Age int
}
func (p *Person) String() string { return fmt.Sprint(*p) }
(добавлен метод String(), поэтому мы увидим фактическое содержимоеструктуры, а не только их адреса ...)
И скажем, мы хотим применить нашу пользовательскую сортировку к срезу типа []*Person, используя поле 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}]