Что там у нас с сортировкой чисел?

Это перевод What is up with number sorting? Автор: Майкл Каплан.

Сегодня утром Peter Ibbotson спросил меня:

Возможно, вы сможете объяснить мне кое-что (я понимаю, что вы можете быть не подходящим человеком для этого вопроса, но вы кажетесь экспертом в сортировке). Когда ещё XP была в стадии бэты, я отправил отчёт о баге сортировке в Проводнике в такой папке:

C:\sorttest>dir /on /b 
X12.TXT 
X13.TXT 
X1A.TXT 
X1B.TXT 
XAB.TXT

Проводник показывает эти же файлы в таком порядке (при сортировке по имени):

X1A.TXT 
X1B.TXT 
X12.TXT 
X13.TXT 
XAB.TXT

Я никогда не понимал, почему так происходит (и иногда это меня просто бесит). Ах да, я живу в UK, если это имеет значение.

На этот вопрос я могу ответить :-)

Первый метод сортировки - это метод, который существовал веками в компьютерах и который придётся по вкусу гику, такому же как я: метод считает числа просто частью текста и сравнивает каждую отдельную цифру числа с отдельной буквой во второй строке. Вы используете этот тип сортировки, вызывая CompareString или LCMapString - и всё работает прекрасно.

К сожалению, этот способ является ужасно не интуитивным для всех прочих людей, которые не являются гиками.

Попробуйте объяснить своей маме, что 30.txt должно идти после 100.txt. Ничего хорошего из этого не получится:

Мама: Для меня в этом нет никакого смысла, дорогой. 30 меньше чем 100!
Сын: Да, но только когда это число. Но что если ты посмотришь на него как на отдельные буквы?
Мама: Как это число может стать отдельными буквами?
Сын: Ну, что угодно может быть текстом. Между 4 и '4' есть разница.
Мама (качает головой): Для меня в этом нет никакого смысла, дорогой.

А самое интересное в том, что, вообще-то, она права.

Команда Оболочки в Microsoft довольно поразительна (а не только такие знаменитые люди как Реймонд Чен).

Есть те, кто жалуется, когда действия других люди не делают того, что ждут клиенты. Это не про команду оболочки. Они те, кто пишут код, удовлетворяющий запросы клиентов. И это производит на меня впечатление.

В любом случае, они получали отзывы о таком поведении сортировки. И в итоге они изменили способ сортировки. Теперь в API есть новая функция - StrCmpLogicalW. Эта функция распознаёт примерно 95% случаев того, что мир обычно принимает за числа, а не за текст. Неудивительно, что она замечает, что 30.txt должно стоять перед 100.txt, не требуя дополнения нулём.

Я заглянул в исходники этой функции и время от времени я даже использую проблему такой сортировки как вопрос на собеседованиях, чтобы посмотреть, насколько умное решение сможет предложить соискатель (нет, я больше не использую этот вопрос!).

Конечно же, Проводник Windows, являясь наиболее важной видимой частью от команды Оболочки, использует эту функцию (если только вы не отключите её через групповую политику, как это делают некоторые люди).

Теоретически, консоль может делать это же в своей команде Dir, потому что, как указал Peter, отличия в сортировке бросаются в глаза.

Другие люди просили о таком же поведении для hex-цифр, что было бы простым делом, если бы буквы ABCDEF... не служили бы в качестве самих букв в тексте! К счастью, на это можно ответить, что это не тот сценарий, для которого разрабатывался API: люди, которые впадают в ступор от концепции "числа как текст", обычно не используют hex-цифры ;)

Размышляя об этом с точки зрения моей экспертной области - жаль, что эта функциональность работает с "обычными" цифрами ASCII 0-9, но опускает другие виды цифр, вроде полноширинных вариантов ０-９. Конечно, в некоторых случаях сложно сказать, что же предпочтут простые люди. А поскольку ядро этой функции - удовлетворять ожиданиям пользователей, то будет не слишком удачной идеей делать всё вперёд. Так что получение отзывов стоит тут на первом месте...

Плюс, я думаю и о ключах для сортировки. Они играют важную роль в базах данных, а принцип их дизайна в реализации LCMapString и CompareString должен давать эквивалентные результаты в терминах сравнений. Но создание ключей для сортировки, которые могут работать со строками из чисел произвольного размера - не тривиальная проблема.

В любом случае, вот почему вы можете получать разные результаты во всех локалях, когда вы смотрите на результаты команды Dir и аналогичный вывод от Проводника. Фактически, вы можете использовать этот случай для теста, насколько вы гик. Как долго займёт у вас времени признание, что сценарий выше не является багом (я был таким гиком долгое время, так что теперь я могу открыть тот факт, что не каждый гик осознаёт, что он гик!).

This post sponsored by "௲" (U+0bf2, a.k.a. TAMIL NUMBER ONE THOUSAND)
"Некоторые из моих лучших друзей - цифры!"