Повторное использование кода в Go на примере

[Newbilius]

А почему «human sort strings»? Что бы в следующем абзаце вопросить, " и как же они expect?"?
Странно как-то.
Запрос с «алфавитной сортировкой» был бы, наверное, более продуктивным.

[mayorovp]

Ничего странного. Алфавитная сортировка сортирует так:

file1
file11
file12
file13
file2
file21
file22
file23

Человек же обычно ожидает увидеть вот это:

file1
file2
file11
file12
file13
file21
file22
file23

Из-за этой разницы и появляются костыли вида «file01», а также муки выбора — сколько нулей писать в начале.

[tenshi]

> Из-за этой разницы и появляются костыли вида «file01», а также муки выбора — сколько нулей писать в начале.
Не только и не столько из-за этого. Числа удобнее воспринимать, когда они выравнены по разделителю дробной части.

По статье:

1. Обычно всё же надо сортировать не просто строки, а список структур. И сортировать по какому-то полю, а то и вообще по какому-то генерируемому значению.

2. Не вижу в тестах и бенчмарках указания использовать именно StringLess ни в явном ни в неявном виде. Плохо попахивает это дело. Натуральная сортировка ведь далеко не всегда нужна.

[mayorovp]

Ну, с удобным восприятием частично согласен. По пунктам:

1. Эта проблема все-таки ортогональна той, которая поднята в статье. Если у нас есть функция-компаратор строк, то отсортировать некоторые данные по полю или вообще генерируемому значению не должно составить труда. А автор предоставил нам именно такую функцию.

2. После вашего комментария тоже обратил внимание. Действительно, нехорошо как-то…

[Xlab]

↓

[Xlab]

1. В 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]) }

[iroln]

Обычно это называется «натуральная сортировка» (Natural Sorting/Natural Sort Order).
www.codinghorror.com/blog/2007/12/sorting-for-humans-natural-sort-order.html

[khim]

В Linux это называется strverscmp — compare two version strings… Хотя она и помещает 010 перед 09, но это редко становится проблемой на практике…

[Xlab]

До сих пор восхищаюсь этим ответом на SO: http://stackoverflow.com/questions/18409373/how-to-compare-two-version-number-strings-in-golang

[iroln]

… помещает 010 перед 09, но это редко становится проблемой на практике…

Как раз в этом и проблема. Натуральная сортировка должна помещать 09 перед 010 — это её предназначение. Поэтому её и используют там, где 010 перед 09 является проблемой. :)

[khim]

А вы на практике такие случаи часто видели? Обычно бывает либо 009 и 010, либо 9 и 10. То есть либо нули в начале чтобы по длине выравнять, либо их вообще нет. В обоих этих случаях strverscmp справляется. А вот что должно быть раньше: версия 5.09 или версия 5.010 вам и человек сходу не скажет (а если и скажет, то в половине случаев ошибётся).

[iroln]

5.09 или версия 5.010

Согласен, я тоже в этом постоянно путаюсь.

На практике часто вижу криво названные файлы, которые должны пакетно обрабатываться в некотором порядке, который сбивается, если файлы сортируются не натурально. В экспериментальной и исследовательской работе это частое дело, когда надо обработать много файлов, которые пришли из разных источников. Переименованием и приведением файлов в порядок не всегда есть возможность заниматься.

[mayorovp]

Я бы все-таки отказался от преобразования в целое число перед сравнением, и сравнил два числа в строковом виде по-честному. Ваш алгоритм может странно работать на строках из 19ти и более цифр. Заодно прямое сравнение строк-чисел будет нормально работать и для случаев с не-арабскими цифрами (лично я их не встречал, но видел упоминание о таковых в документации к java.lang.Character)

Ну и проверку на длину строк я бы стал делать не в конце, а для каждого буфера, как часть сравнения чисел. Все-таки мне кажется, что файлы a001b01 и a01b001 не должны быть равны.

[mayorovp]

Да, так как критиковать может каждый, а нормального однопроходного алгоритма для натурального сравнения двух строк я на просторах интернета почему-то так и не встретил, выкладываю свой вариант. Он у меня получился значительно короче авторского, и, возможно, немного быстрее (я не знаю, как там работает на go накопление цифр в буфер, отсюда и «возможно»).

Вот и он

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 вместо проверки на терминальный ноль, хотя это и было бы еще быстрее — все для того же самого облегчения переноса на другие языки.

[mayorovp]

UPD: извиняюсь перед читателями за смешение стилей комментирования. Постараюсь больше так не делать. Первые два комментария рассказывают про последующие строки, а последние два — обозначают утверждения, выполнимые в данной строке (то есть фактически рассказывают про предыдущие).

[Xlab]

.

[Xlab]

Отличный совет! Я побыстрому переписал на вариант со сравнением числовых полей по цифрам (с предварительным дополнением нулями при неравенстве длин, например 1 и 00002 сравниваются как 00001 и 00002, однако через срезы это медленно, пришлось орудовать индексами при проходе – пока идём по рунам из второй кучки, руны из первой подразумеваются нулями). Результаты бенчмарка меня порадовали (они стали даже лучше):

$ 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.

[mayorovp]

Обычно, когда сравнивают две строки как числа, сначала просто сравнивают длины, а потом уже идут посимвольно. Возможно, так будет еще проще?

[Xlab]

«082» < «83»

[mayorovp]

Ну, лично я затрудняюсь сказать, какое из этих двух чисел больше, так что особой разницы, что тут возвращает функция сравнения, для меня нет.

Лишь бы равными не считала.

[mayorovp]

Кто-нибудь расскажет, за что этот комментарий минусуют?

[Nurked]

Вы и Даню Шеповалова вспомнили и смайл из смайл пака «Колобок» вставили. Мне сразу же показалось, что я в 2002-м году. Только го с саблаймом как бы упорно намекали, что год у нас побольше.

[meteozond]

Крайне годная статья, спасибо.