Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 23
А почему «human sort strings»? Что бы в следующем абзаце вопросить, " и как же они expect?"?
Странно как-то.
Запрос с «алфавитной сортировкой» был бы, наверное, более продуктивным.
Странно как-то.
Запрос с «алфавитной сортировкой» был бы, наверное, более продуктивным.
Ничего странного. Алфавитная сортировка сортирует так:
file1Человек же обычно ожидает увидеть вот это:
file11
file12
file13
file2
file21
file22
file23
file1Из-за этой разницы и появляются костыли вида «file01», а также муки выбора — сколько нулей писать в начале.
file2
file11
file12
file13
file21
file22
file23
> Из-за этой разницы и появляются костыли вида «file01», а также муки выбора — сколько нулей писать в начале.
Не только и не столько из-за этого. Числа удобнее воспринимать, когда они выравнены по разделителю дробной части.
По статье:
1. Обычно всё же надо сортировать не просто строки, а список структур. И сортировать по какому-то полю, а то и вообще по какому-то генерируемому значению.
2. Не вижу в тестах и бенчмарках указания использовать именно StringLess ни в явном ни в неявном виде. Плохо попахивает это дело. Натуральная сортировка ведь далеко не всегда нужна.
Не только и не столько из-за этого. Числа удобнее воспринимать, когда они выравнены по разделителю дробной части.
По статье:
1. Обычно всё же надо сортировать не просто строки, а список структур. И сортировать по какому-то полю, а то и вообще по какому-то генерируемому значению.
2. Не вижу в тестах и бенчмарках указания использовать именно StringLess ни в явном ни в неявном виде. Плохо попахивает это дело. Натуральная сортировка ведь далеко не всегда нужна.
Ну, с удобным восприятием частично согласен. По пунктам:
1. Эта проблема все-таки ортогональна той, которая поднята в статье. Если у нас есть функция-компаратор строк, то отсортировать некоторые данные по полю или вообще генерируемому значению не должно составить труда. А автор предоставил нам именно такую функцию.
2. После вашего комментария тоже обратил внимание. Действительно, нехорошо как-то…
1. Эта проблема все-таки ортогональна той, которая поднята в статье. Если у нас есть функция-компаратор строк, то отсортировать некоторые данные по полю или вообще генерируемому значению не должно составить труда. А автор предоставил нам именно такую функцию.
2. После вашего комментария тоже обратил внимание. Действительно, нехорошо как-то…
1. В Go сортировка делается через реализацию интерфейса (делаем хелпер). Вы описываете для своей коллекции структур следующие методы:
Затем
2.
Ещё раз обращаю внимание, момент получился неочевидным:
А сам хелпер был в strings.go:
Len, Swap, Less.Затем
sort.Sort(МояРеализация(коллекция)).2.
StringLess используется в реализации метода Less у хелпера handysort.Strings, в тестах он используется как Strings, потому что пакет тот же. Вы можете написать свой хелпер для сортировки сложных объектов, но везде вместо сравнения через "<" делаете сравнение через handysort.StringLess.Ещё раз обращаю внимание, момент получился неочевидным:
// сортировка с применением лексиграфического сравнения строк
sort.Strings(set[b.N])
// сортировка с примененим нашего сравнения строк
sort.Sort(Strings(set[b.N])) // то же самое что и sort.Sort(handysort.Strings(set[b.N]))
А сам хелпер был в strings.go:
// Strings implements the sort interface, sorts an array
// of the alphanumeric strings in decreasing order.
type Strings []string
func (a Strings) Len() int { return len(a) }
func (a Strings) Swap(i, j int) { a[i], a[j] = a[j], a[i] }
func (a Strings) Less(i, j int) bool { return StringLess(a[i], a[j]) }
Обычно это называется «натуральная сортировка» (Natural Sorting/Natural Sort Order).
www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html
www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html
В Linux это называется strverscmp — compare two version strings… Хотя она и помещает 010 перед 09, но это редко становится проблемой на практике…
До сих пор восхищаюсь этим ответом на SO: http://stackoverflow.com/questions/18409373/how-to-compare-two-version-number-strings-in-golang
… помещает 010 перед 09, но это редко становится проблемой на практике…
Как раз в этом и проблема. Натуральная сортировка должна помещать 09 перед 010 — это её предназначение. Поэтому её и используют там, где 010 перед 09 является проблемой. :)
А вы на практике такие случаи часто видели? Обычно бывает либо 009 и 010, либо 9 и 10. То есть либо нули в начале чтобы по длине выравнять, либо их вообще нет. В обоих этих случаях strverscmp справляется. А вот что должно быть раньше: версия 5.09 или версия 5.010 вам и человек сходу не скажет (а если и скажет, то в половине случаев ошибётся).
5.09 или версия 5.010
Согласен, я тоже в этом постоянно путаюсь.
На практике часто вижу криво названные файлы, которые должны пакетно обрабатываться в некотором порядке, который сбивается, если файлы сортируются не натурально. В экспериментальной и исследовательской работе это частое дело, когда надо обработать много файлов, которые пришли из разных источников. Переименованием и приведением файлов в порядок не всегда есть возможность заниматься.
Я бы все-таки отказался от преобразования в целое число перед сравнением, и сравнил два числа в строковом виде по-честному. Ваш алгоритм может странно работать на строках из 19ти и более цифр. Заодно прямое сравнение строк-чисел будет нормально работать и для случаев с не-арабскими цифрами (лично я их не встречал, но видел упоминание о таковых в документации к java.lang.Character)
Ну и проверку на длину строк я бы стал делать не в конце, а для каждого буфера, как часть сравнения чисел. Все-таки мне кажется, что файлы a001b01 и a01b001 не должны быть равны.
Ну и проверку на длину строк я бы стал делать не в конце, а для каждого буфера, как часть сравнения чисел. Все-таки мне кажется, что файлы a001b01 и a01b001 не должны быть равны.
Да, так как критиковать может каждый, а нормального однопроходного алгоритма для натурального сравнения двух строк я на просторах интернета почему-то так и не встретил, выкладываю свой вариант. Он у меня получился значительно короче авторского, и, возможно, немного быстрее (я не знаю, как там работает на go накопление цифр в буфер, отсюда и «возможно»).
Этот код использует нуль-терминальные однобайтовые строки, и не умеет работать с русскими символами (по крайней мере, в 2012й студии с настройками проекта по умолчанию), но я его написал так намеренно. Поскольку он использует только последовательный перебор символов строки и проверку isdigit (ну и сравнение символов, конечно же), его можно без труда перенести на любой другой язык.
Также я намеренно использовал функцию strlen вместо проверки на терминальный ноль, хотя это и было бы еще быстрее — все для того же самого облегчения переноса на другие языки.
Вот и он
bool less(char* a, char* b)
{
int lena = strlen(a), lenb = strlen(b);
int i;
for (i=0; i<lena && i<lenb; i++)
{
// Сначала сравним числовые блоки, начинающиеся в данной точке (возможно, нулевой длины).
// num_less - признак того, что первый блок меньше второго
// num_diff - признак того, что они вообще отличаются
// num_block - признак того, что оба блока не нулевой длины
bool num_less = false, num_diff = false, num_block = isdigit(a[i]) && isdigit(b[i]);
for (; isdigit(a[i]) && isdigit(b[i]); i++)
if (a[i] != b[i])
{
num_less = a[i] < b[i];
num_diff = true;
break;
}
// Сравнение длин числовых блоков. Тот блок, который длиннее, представляет собой большее
// по величине число, независимо от num_less.
// НО! Нулевой блок, тем не менее, больше ненулевого (поскольку цифры идут раньше букв)
for (; isdigit(a[i]) && isdigit(b[i]); i++) ;
if (isdigit(a[i])) return !num_block;
if (isdigit(b[i])) return num_block;
// Длины чисел одинаковы (возможно, обе - нулевые).
if (num_diff) return num_less;
// В числовых блоках различий нет (возможно, оба блока были нулевой длины)
if (a[i] != b[i]) return a[i] < b[i];
}
return i == lena && i != lenb;
}
Этот код использует нуль-терминальные однобайтовые строки, и не умеет работать с русскими символами (по крайней мере, в 2012й студии с настройками проекта по умолчанию), но я его написал так намеренно. Поскольку он использует только последовательный перебор символов строки и проверку isdigit (ну и сравнение символов, конечно же), его можно без труда перенести на любой другой язык.
Также я намеренно использовал функцию strlen вместо проверки на терминальный ноль, хотя это и было бы еще быстрее — все для того же самого облегчения переноса на другие языки.
Отличный совет! Я побыстрому переписал на вариант со сравнением числовых полей по цифрам (с предварительным дополнением нулями при неравенстве длин, например 1 и 00002 сравниваются как 00001 и 00002, однако через срезы это медленно, пришлось орудовать индексами при проходе – пока идём по рунам из второй кучки, руны из первой подразумеваются нулями). Результаты бенчмарка меня порадовали (они стали даже лучше):
Ещё и без привязки к uint64. «a01b001» < «a001b01», если что, проверил в OS X.
$ go test -bench=.
PASS
BenchmarkStringSort 500 3611235 ns/op
BenchmarkHandyStringSort 100 15821388 ns/op
ok github.com/Xlab/handysort 93.953s
Ещё и без привязки к uint64. «a01b001» < «a001b01», если что, проверил в OS X.
Вы и Даню Шеповалова вспомнили и смайл из смайл пака «Колобок» вставили. Мне сразу же показалось, что я в 2002-м году. Только го с саблаймом как бы упорно намекали, что год у нас побольше.
Крайне годная статья, спасибо.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Повторное использование кода в Go на примере