Hacker News Digest

На macOS и Linux команда sort упорядочивает строки по-разному даже при одинаковой локали en_US.UTF-8. Например, на macOS python-dev идет перед python3-dev, а на Linux - наоборот. Причина - в файлах LC_COLLATE: на большинство локалей в macOS ссылаются на la_LN.US-ASCII, что представляет собой базовое ASCII-упорядочивание. Даже для нелатинских локалей (китайской, японской, корейской) используется та же ссылка. В то время как на Linux используются более сложные правила сортировки, учитывающие национальные особенности.

Автор обнаружил, что в macOS 122 из 178 локалей используют la_LN.US-ASCII в качестве основы для сортировки. Исследуя исходный код Apple, он нашел, что правила сортировки для la_LN.US-ASCII чрезвычайно просты - это просто базовое ASCII-упорядочивание без учета национальных особенностей. Это объясняет, почему на macOS "python-dev" идет перед "python3-dev", так как дефис (ASCII 0x2D) имеет меньший код, чем цифра 3 (ASCII 0x33).

• Сортировка строк в Unix-подобных системах зависит от локали, и это может привести к неожиданным результатам, особенно при работе с диакритическими символами.
• Сортировка строк в Unix-подобных системах зависит от локали, и это может привести к неожиданным результатам, особенно при работе с диакритическими символами.
• Сортировка строк в Unix-подобных системах зависит от локали, и это может привести к неожиданным результатам, особенно при работе с диакритическими символами.
• Сортировка строк в Unix-подобных системах зависит от локали, и это может привести к неожиданным результатам, особенно при работе с диакритическими символами.
• Сортировка строк в Unix-подобных системах зависит от локали, и это может привести к неожиданным результатам, особенно при работе с диакритическими символами.

Автор обнаружил, что современные файловые менеджеры (включая Google Drive, Windows Explorer, Dolphin и другие) не сортируют файлы в строгом алфавитном порядке. Вместо этого они применяют «естественную сортировку»: если в имени встречаются цифры, система сравнивает их числовые значения, а не символы. Из-за этого file-10.txt оказывается перед file-9.txt, поскольку 10 > 9, хотя буква «1» идёт раньше «9».

Проблема проявилась при сортировке фотографий с двух Android-устройств, где в одном названии миллисекунды были отделены подчёркиванием, а в другом — нет. Это привело к неправильной группировке по времени. Только консольная утилита ls и некоторые UNIX-системы сохранили классическую сортировку. Автор с ностальгией отмечает, что компьютеры теперь часто «думают за пользователя», вместо того чтобы чётко выполнять команды.

• Участники обсуждают разницу между алфавитной и естественной (natural) сортировкой, где числа сортируются по их числовому значению, а не посимвольно.
• Многие пользователи ожидают, что "файл10" будет после "файла9", что является распространённым поведением в современных ОС, хотя это и не строго алфавитный порядок.
• Поднимается вопрос корректности labeling: интерфейсы часто называют сортировку "по имени", а не "алфавитной", что технически позволяет использовать любой алгоритм.
• Некоторые пользователи предпочитают лексикографическую сортировку (например, для хэшей или дат) и критикуют отсутствие выбора алгоритма в системах.
• Обсуждаются сложности сортировки с учётом локалей, не-ASCII символов и контекстно-зависимых правил, делающих единый стандарт невозможным.

• Сортировка с хешем быстрее хеш-таблиц: на больших данных 1,5–4×, несмотря на «O(n log n)».
• Память: хеш-таблица тянет 128 Б на 8-Б ключ (64 чтение + 64 запись), радикс-сорт 3 прохода — 48 Б (вся линия кэша используется).
• Плохие распределения (мало заполненных корзин) замедляют радикс-сорт; решаем хешем hash(key) перед сортировкой. Берём обратимую функцию (Murmur3, MulSwapMul), хешируем «на лету» в первом проходе.
• Результат: 2 ГиБ уникальных uint64 за 1,9 с против 2,6 с у оптимизированной хеш-таблицы.
• Подходит, когда порядок не важен, а нужны только уникальные значения; иначе остаёмся на хеш-таблицах.

• Улучшенная нестабильная сортировка Rust почти догнала по скорости специально настроенный radix-sort, несмотря на разницу в O(n log n) vs O(n).
• Хэш-таблица «побеждает» лишь при ограниченном размере ключа и хорошем кэше; при росте данных снова проигрывает из-за промахов и O(n log n) внутри.
• Radix можно ускорить, выделяя buckets через MMU, а не вручную управляя памятью.
• На очень больших объёмах (≥120 ГБ) константы radix снова могут перевесить, но пока доминирует кэш-эффективность сортировки.
• Всё обсуждение подчёркивает: конкретные константы и архитектура CPU важнее «чистой» Big-O.