Hacker News Digest

Новички в программировании часто зацикливаются на изучении структур данных и алгоритмов (DSA), потому что это проверяется на собеседованиях. Однако в реальной работе редко приходится реализовывать сложные алгоритмы вручную — вместо этого стоит понять базовые структуры, их trade-offs и основы Big O, чтобы эффективно организовывать и обрабатывать данные.

Гораздо полезнее сосредоточиться на тестировании: это навык, который постоянно применяется в разработке, улучшает качество кода и выделяет кандидата на фоне других. Тестирование помогает проектировать системы, учит писать проверяемый код и становится отдельной инженерной дисциплиной с богатым инструментарием.

• Участники обсуждают важность знания структур данных и алгоритмов (DSA) для разработчиков, отмечая, что понимание их характеристик (например, сложности операций) часто важнее умения реализовывать их с нуля.
• Подчеркивается необходимость баланса между теоретическими знаниями (DSA) и практическими навыками тестирования, при этом многие отмечают, что эти навыки не исключают, а дополняют друг друга.
• В дискуссии звучит критика статьи, указанной в исходном посте, за её провокационный заголовок, который, по мнению участников, упрощает сложную проблему и создает ложную дихотомию между DSA и тестированием.
• Несколько комментаторов приводят примеры из практики, где незнание базовых принципов DSA (например, сложности алгоритмов) приводило к серьезным проблемам с производительностью в продакшене.
• Обсуждается роль тестирования: одни видят в нем ключевой навык для обеспечения качества, другие указывают на его ограничения (например, сложность тестирования многопоточных систем) и необходимость сочетать его с другими методами, как property-based тестирование или формальные доказательства.

• Сортировка с хешем быстрее хеш-таблиц: на больших данных 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.