TimSort - алгоритм сортировки, о котором мало говорят

Сортировка данных - не просто вопрос на собеседовании, а интересная алгоритмическая задача и важный прикладной инструмент в написании приложений и сервисов. И достаточно долгое время в этом вопросе доминировал алгоритм быстрой сортировки (Quick Sort или сортировка Хоара), который был встроен в стандартные библиотеки различных ЯП многие годы.
Кажется, что на фоне популярности быстрой сортировки, можно и не слышать о TimSort. И это удивительно, учитывая его эффективность и важность в современной разработке программного обеспечения.

Этот алгоритм был разработан Тимом Петерсом и впервые внедрен в Python в 2002 году. В этом плане алгоритм гораздо новее, чем QuickSort, первая публикация о котором появилась в 1960 году.

✅ В основе этой сортировки лежат сразу двух алгоритма - сортировка вставкой (Insertion Sort) и сортировка слиянием (Merge Sort). Эта комбинация позволяет алгоритму с одной стороны гарантировано сортировать случайный набор данных за О(n * log n), а частично упорядоченные данными будут отсортированы еще быстрее. Для быстрой сортировки - худший случай O(n^2).

✅ Также TimSort является устойчивым (или стабильным) алгоритмом сортировки. Это значит, что расположение элементов с одинаковыми значениями друг относительно друга не изменится после сортировки. QuickSort по умолчанию является нестабильным алгоритмом.

🤩 Все вышеописанное привело к тому, что TimSort стал использоваться в стандартных библиотека Python, Java, Swift и JavaScript (реализация V8) вместо быстрой сортировки. А в набирающем популярность языке Rust присутствует и стабильная (TimSort), и нестабильная сортировка (QuickSort).

Единственная небольшая ложка дегтя - это требование дополнительной памяти в размере O(n), как правило не более n / 2. В этом моменте TimSort проигрывает QuickSort, которому не нужно дополнительной памяти для работы.

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

До связи 🤘

Подходы в разработке фичей: тИповой vs тУповой

В мире разработки продуктов мы часто видим, как фичи создаются в соответствии с типовым процессом, требующим длительного цикла, включающего анализ конкурентов, глубинные интервью с пользователями, анализ метрик, UX-исследования и множество других этапов. Этот путь, конечно, имеет свои преимущества, но не всегда оправдывает затраты. 😞

Часто, несмотря на все проделанные усилия, разработанная фича не приносит ожидаемых результатов. Множество времени и ресурсов были потрачены, и всё, что мы имеем, это разочарование. Но что, если существует другой подход? 🤔

Давайте представим, что можно было бы выбрать более короткий. Вместо глубокого анализа и долгих исследований, мы могли бы решить создать более "тупую" или "туповатую" версию фичи. Мы не затрачивали бы много времени на исследования, а сразу проверили бы самую простую реализацию в бою 🚀

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

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

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

Быстрой вам разработки крутых фичей!
До связи 🤘

Пакетные менеджеры и lock-файлы

В процессе разработки программного обеспечения сторонние библиотеки играют все более важную роль. Они выступают в качестве зависимостей для вашего проекта, и нужно тратить время и силы для управления ими 🤯. Именно для этого используют пакетные менеджеры, которые позволяют легко установить, обновить или удалить зависимость. Казалось бы, для пакетного менеджера достаточно иметь список библиотек с соответствующими версиями для установки. Но рядом появляются какие-то lock-файлы - для чего же они нужны? 🤔

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

Lock-файлы фиксируют конкретные версии всего дерева зависимостей вашего проекта и это дает нам:
🦾 консистентность установленных библиотек между всеми участниками процесса
🚀 ускорение установки (пакетный менеджер точно знает, какую версию нужно скачивать)

Давайте приведу ряд примеров:
- Pipenv и Poetry для языка Python используют pipfile.lock и poetry.lock
- Composer в мире PHP использует composer.lock
- Bundler для Ruby пологается на Gemfile.lock
- npm и yarn в экосистеме JavaScript используют package-lock.json и yarn.lock
- Cargo для Rust полагается на Cargo.lock

Стабильного управления зависимостями и не забывайте коммитеть lock-файлы в git.

До связи 🤘

Факапы и что делать дальше?

В жизни каждого из нас бывают моменты, когда не всё идет по плану 🤯. Это могут быть плохие релизы, несоблюдение сроков, ошибки в принятии решений и так далее. Факапы - неотъемлемая часть любой деятельности. И, что важно понимать, это нормально. Мы не роботы, и совершать ошибки - часть процесса саморазвития и профессионального роста.

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

Важно дать своему организму возможность восстановиться после стресса. Иногда этим может быть день отдыха 🧘‍♂️, когда вы просто расслабляетесь и забываете о проблемах. Для других это может быть спортивный зал 🏋️, где физическая активность помогает очистить ум от негативных мыслей. Иногда это просто несколько часов в уединении с хорошей книгой или фильмом 📺.

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

P.S. В четверг был очень тяжелый релиз. Была потрачена куча времени на подготовку, но все равно очень многое пошло не так 😩
В пятницу не работал, посмотрел тупейший "Отряд самоубийц 2", лег рано спать. Суббота уже прошла нормально.

Падаем, но поднимаемся! До связи 🤘

Алгоритмы сжатия и gzip

Быстрая современная передача информации по проводным или беспроводным сетям была бы невозможна без алгоритмов сжатия. Ведь универсальный способ увеличить скорость доставки - это уменьшение объема. Неотъемлемой частью современной веб-разработки и обработки данных стал gzip. Скорее всего каждый сайт открытый в вашем браузере так или иначе использует Content-Encoding: gzip. Давате немного разберемся.

Первый публичный релиз Gzip состоялся в 1992 году, а в 1993 была выпущена версию 1.0. Gzip не является алгоритмом как таковым, а в первую очередь является форматом данных и программным обеспечением для хранения (обычно `.gz`) и сжатия. Под капотом gzip использует алгоритм сжатия без потерь Deflate, который является универсальным алгоритмом и, например, применяется для сжатия изображений в формате PNG.

Deflate в свою очередь является комбинацией из двух наиболее успешных и достаточно древних алгоритмов сжатия без потерь, которые используют разные подходы: LZ77 (1977 г.) и кодирование Хаффмана (1952 г.). LZ77 находит повторяющиеся последовательности байт и заменяет их на указатели на первое вхождение. Кодирование Хаффмана осуществляется путем частотного анализа - чем чаще последовательность кодов встречается, тем в более короткий код на выходе она преобразуется.

В мире Unix для работы с gzip можно использовать следующие утилиты:
gzip - собственно сжимает файл или поток данных (для сжатия нескольких файлов используется в паре с утилитой tar)
gunzip - распаковка .gz файлов
zcat - для чтения сжатых файлов без их распаковки (например, можно просматривать сжатые логи веб-сервера)

Используйте gzip и не забывайте сжимать данные на створе веб-сервера перед отправкой вашим клиентам.

До связи 🤘

Бинарный поиск или Binary search

Представьте себе задачу: вам нужно найти позицию определенного значения в массиве. 🤔

Наивное решение задачи сводится к вызову функции типа indexOf(...), и в таком случае поиск занимает линейное время. Но что если данные отсортированы и нам хочется осуществить поиск как можно быстрее?

Алгоритм бинарного поиска поможет вам справиться с этой задачей за логарифмическое время! Принцип работы очень прост:

1. Находим средний элемент в отсортированном массиве
2. Сравниваем его с искомым значением. Если они совпали, значит задача выполнена
3. Если значение в среднем элементе больше искомого, то искомое значение находится слева от среднего элемента, и мы продолжаем поиск в левой половине массива.
4. Если значение меньше искомого, то продолжаем поиск в правой половине массива.
5. Возвращается к пункту 1 и так, пока не найдем элемент.

✅ Деление исходных данных пополам на каждом шаге и приводить нас в логарифмической оценке временной сложности алгоритма.

Бинарный поиск пользуется популярностью и входит в стандартные библиотеки С/C++, Java, Python, Go, .NET.

Эффективного поиска и до связи 🤘

B-tree и базы данных

B-tree, несмотря на первое впечатление, это не бинарное дерево 🌲. Это сбалансированное (self-balancing) дерево поиска, где каждый узел может хранить более 1 ключа, а количество потомков может быть более 2. В такой трактовке B-tree - это обобщение бинарного дерева. Давайте теперь разберемся, что нам дают две основных части определения - дерево поиска и сбалансированное дерево.

✅ В деревьях поиска данные упорядочиваются на основе выбранной операции (обычно это операция < или “меньше”). В случае с B-tree это означает, что все ключи узла упорядочены по возрастанию, а значения в ключах левого потомка меньше, чем значения в ключах потомков правее. Зная такую структуру хранения можно, итерационно применяя операцию “меньше”, найти необходимый элемент в дереве.

✅ Сбалансированные деревья устроены таким образом, что расстояние от корня до листьев дерева (узлов без потомков) примерно равно для всех веток дерева. Обычно в реализациях B-tree оно строго одинаково для всех листьев.

Устройство ключей в B-tree и комбинация свойств выше делают такие деревья не очень глубокими. Именно поэтому в таких популярных реляционных базах данных, как PostgreSQL и MySQL, а также в различных NoSQL решениях, типа MongoDB, индексы хранятся именно в виде B-деревьев. Это обеспечивает высокую производительность 🚀 при выполнении запросов и с точным совпадением, и при поиске по диапазону, а так же для сортировки данных.

Всегда приятно знать чуть больше, когда выполняете операцию CREATE INDEX.

До связи 🤘

Чем отличается HTTP/2 от HTTP/1.1

Спецификация HTTP/2 была опубликована в мае 2015, и это стало одним из важнейших шагов по улучшению производительности всего интернета за последние 10 лет. Какие же существенные отличия в сравнении с HTTP/1.1 нужно иметь ввиду:

1️⃣ Бинарный протокол. HTTP/2 использует бинарный протокол для передачи данных, в то время как HTTP/1.1 использует текстовый формат. Бинарные данные меньше по объему - скорость передачи и обработки увеличивается.

2️⃣ Мультиплексирование. В HTTP/1.1 для экономии времени на установление нового TCP-соединения (а так же SSL/TLS в случае https) использовалась техника keep-alive, чтобы слать запросы через одно соединения, но в блокирующем режиме: сначала должен прийти ответ на первый запрос, чтобы можно было отправить второй. В HTTP/2 через одно TCP-соединение можно отправлять множество запросов параллельно.

3️⃣ Приоритизация. HTTP/2 вводит приоритизацию для потоков данных. Это дает возможность клиентам (например, браузеру) более рационально использовать единое TCP-соединения. Теперь запросить все данные у сервера можно одновременно, но поступать на клиенты они будут в заранее выбранном порядке.

4️⃣ Сжатие заголовков. Кроме перехода на бинарный формат HTTP/2 может сжимать заголовки запросов и ответов с помощью специального алгоритма HPACK. Объем передаваемых данных еще меньше, скорость выше.

5️⃣ Server Push. В HTTP/2 серверу предоставляется возможность самостоятельно направить данные клиенту, как бы предугадывая его будущие потребности. Это может существенно уменьшить задержки, например, при переходе между разными страницами одного сайта.

Так же стоит отметить, что современные браузеры поддерживают HTTP/2 только поверх защищенного SSL/TLS соединения. Интернет становится еще безопаснее 🔐

Если в голых цифрах, то почти 95% пользователей интернета используют браузеры с поддержкой HTTP/2. Nginx получил поддержку в версии 1.9.5 (2015 год!). Так что если вы еще не включили для своих клиентов HTTP/2, то сделайте это прямо сейчас - нет причин откладывать!

До связи 🤘

Принципы разработки: KISS

В мире разработки программного обеспечения существует целый ряд принципов, рекомендаций и практик, которые помогают создавать эффективные и поддерживаемые решения. Принцип KISS - “Keep It Simple, Stupid” - был сформирован еще в середине XX века и применим почти в любой сфере интеллектуальной человеческой деятельности.

Почему KISS так важен в программировании?

Простота и читаемость кода 🤓 Принцип KISS настаивает на том, что код должен быть максимально понятным для разработчиков. Простой и ясный код легче поддерживать, тестировать и масштабировать.

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

Легкость в обучении и внедрении 📚 Простой код и ясная архитектура упрощают процесс передачи знаний и обучения для новых членов команды.

Соблюдение сроков 🗓️ Как правило, простой код требует меньше времени на разработку и тестирование. Простота помогает соблюсти сроки проекта.

Как говорится, простое лучше сложного! 😁

До связи 🤘

Что такое ORM?

ORM, или Object-Relational Mapping, представляет собой программный подход, который связывает объекты в приложении напрямую с записями в реляционной базе данных. Вместо того чтобы писать SQL-запросы вручную, разработчики могут использовать объекты и методы для выполнения типовых операций, типа SELECT, INSERT и так далее.

Давайте рассмотрим, какие преимущества и недостатки сопутствуют использованию ORM.

✅ Ускорение разработки. Использование ORM не только уменьшает количество написанного кода, если сравнивать с голым SQL, но и заметно упрощает написание однотипных выражений, типа фильтраций на больше/меньше/равно. Кроме этого все операции маппинга из БД в объекты вашего языка программирования происходят внутри ORM и для этого не нужно писать дополнительный код.

✅ Защищает от ошибок и опечаток. Если при написании SQL можно допустить ошибку в синтаксисе или вообще обратиться к несуществующей таблице, то как правило при использовании ORM это сделать значительно сложнее. В этом помогают и автоматические подсказки в IDE при вызове методов ORM, и проверки на этапе компиляции и/или статического анализа. Всё это позволяет больше сосредоточиться на бизнес-логике во время непосредственного программирования.

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

⛔️ Непрозрачность. При использовании ORM сложно быть до конца уверенным, как именно будет обработана конкретная конструкция под капотом и в какой SQL-запрос она будет преобразована. Это может усложнить отладку и понимание того, что происходит в базе данных.

⛔️ Потери в производительности. Часто использование ORM приводит к потере производительности из-за генерации неэффективных SQL-запросов, выборки избыточного количества полей, а также излишних преобразований, выполняемых внутри ORM.

⛔️ Невозможность написать сложный SQL-запрос. Возможности ORM по генерации SQL почти всегда ограничены и не весь доступный функционал вашей СУБД может быть отражен в синтаксисе ORM. Очень часто сложные запросы приходится писать на голом SQL, что лишает вас преимуществ работы с ORM.

Так же большинство ORM пытается обобщить работу с разными СУБД через единый интерфейс. Это с одной стороны может быть удобным, позволяет работать с разными СУБД через одну и туже известную вам ORM. С другой стороны не дает воспользоваться максимум преимуществ каждой отдельно взятой базы данных.

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

До связи 🤘

Null-ссылки и Null Safety

Null - это концепция, которая представляет собой ссылку на "ничто" или отсутствие значения, поэтому активно используется различными языками программирования в качестве значения по-умолчанию.

🤓 Появление null-ссылок в программировании обычно приписывают языкам из семейства ALGOL в 1960ых годах. В последствии Тони Хоар - лауреат премии Тьюринга, один из автором ALGOL и создатель “быстрой сортировки” - называл Null своей “ошибкой на миллиард долларов”. Почему же так?

🤔 Несмотря на всю простоту и вроде бы логичность концепции, Null порождает бесконечное количество ошибок при обращении к переменным, которые могут содержать в себе null в качестве значения. И действительно, какой-то полноценной защиты от таких ошибок до последнего времени не было - только вездесущие проверки if (arg != null) и различные виды тестирования для выявления ошибок на ранних стадиях.

А проблема остается актуальной для широко используемых в наше время языков, таких как Java, Python, Go, C#, JavaScript.

🔒 Но не так давно на сцену вышел принцип Null Safety или Void Safety. Данный принцип строится на поддержке в языке программирования продвинутой системы типов с возможностью Union и Intersection типов. Благодаря этому типы с null и без null можно отделить друг от друга, и становится возможным провести все необходимые проверки на этапе статического анализа или компиляции и не допускать обращения к null в рантайме. Наиболее популярными языками, которые поддерживаю данную возможность, являются Rust, Kotlin, TypeScript, Swift, Dart.

Будьте внимательны при работе с null или переходите на Null Safety!

До связи 🤘

Что такое Webhook?

Webhook — это мощный и универсальный инструмент в области веб-разработки и API. Этот механизм позволяет одному веб-приложению уведомлять другое приложение о возникновении определенного события. Уведомление обычно имеет форму HTTP-запроса, отправляемого на конкретный URL-адрес, предоставленный принимающим приложением.

Использование вебхуков в API переводит взаимодействие между сервисами на новый уровень, предоставляя возможность получать обновления в реальном времени в противовес такому методом, как переодический полинг данных на предмет наличия изменений.

С технической точки зрения при работе с вебхуками всегда встает два важных вопроса - безопасность и надежность.

🔐 URL адрес принимающей стороны должен быть доступен в интернете, поэтому необходимо дополнительно позаботиться о безопасности. Для этого можно использовать разные подходы или их комбинации: принимать запросы только с разрешенных ip-адресов, использовать длинные рандомные токены, зашитые в URL или переданные в специальном заголовке, а так же подпись запросов с помощью, например, HMAC

🦾 При разработке систем вебхуков особое внимание нужно уделить обработке ошибок и переотправке запросов для того, чтобы обеспечить надежную коммуникацию между сервисами. Если по какой-то причине запрос не доходит до принимающей стороны или его обработка завершается ошибкой, запрос должен быть отправлен повторно. Политика переотправки запросов (временные задержки, количество попыток) должна быть понятной и четко регламентированной

А вот несколько примеров it-решений на базе webhook:
- Платежные шлюзы уведомляют сайты магазинов об успешной оплате или, наоборот, отклонении платежа
- Telegram использует вебхуки для отправки обновлений ботам
- Платформы CI/CD используют webhook для отправки информации о сломанных билдах или наоборот об успешно завершенных пайплайнах

Если вы разрабатываете публичное API, то ваши пользователи будут действительно рады появлению вебхуков 😍

До связи 🤘

Принципы разработки: DRY

Принцип DRY (Don't Repeat Yourself) - это один из основных принципов разработки программного обеспечения, который важен как для начинающих, так и для опытных разработчиков. Если переводить дословно, то это звучит как “Не повторяйтесь”, то есть призывает не дублировать код.

Давайте разберемся, что может дать следование принципу DRY:

✅ Переиспользование кода. Сознательное избавление от дублирования заставляет разработчика проводить более строгую декомпозицию кода на классы и/или функции для дальнейшего переиспользования.

✅ Меньше ошибок и проще поддерживать. Отсутствие дублирования так же упрощает процесс внесения исправлений, потому что не требует дополнительной работы от программиста по поддержке согласованности однотипных частей кодовой базы.

✅ Читаемость кода. Знакомство с кодом без дублирования обычно вызывает меньше вопросов при погружении для нового участника команды. Да и у старожил освежит в памяти все тонкости быстрее.

✅ Увеличение производительности. Отсутствие дублирования обычно приводит к уменьшению кодовой базы. Меньший объем кода означает более быструю загрузку и скорость выполнения приложения.

‼️ Но, к сожалению, все эти прелести мы получаем не бесплатно, а за счет больших временных затрат на проектирование и постоянный процесс декомпозиции тех участков, которые мы хотим в каком-то объеме переиспользовать, а не дублировать. Здесь важно найти золотую середину именно для вашего проекта.

До связи 🤘

Сетевые протоколы. DNS

Первые спецификации DNS (Domain Name System) появились в 1983 году, а в 1984 г. в Беркли была написана первая реализация DNS-сервера - BIND (остается одним из самых широко используемых DNS-серверов). На базе ДНС работает весь современный интернет, так как именно эта система служит для преобразования доменных имен в IP-адреса.

Для того, чтобы домен example.com ссылался на ваш IP-адрес необходимо создать A-запись. Так же часто используется CNAME - эта запись служит для создания переадресации или псевдонима. Например, очень часто www-домены указываются именно через CNAME на оригинальный домен (без www префикса).

При работе с DNS необходимо иметь ввиду следующие моменты:

✉️ DNS неразрывно связан с электронной почтой. Именно MX запись указывает, по какому адресу расположен почтовой сервер вашего домена.

TXT записи активно используются для хранения мета-информации, например, для подтверждения владения доменом или подписи для email.

DNS-сервера используют очень агрессивное кэширование. Время жизни записей начинается как правило от 5 минут и доходит до суток и более. Это приводит к тому, что изменения распространяются по сети очень долго 🐢.

🔐 Безопасность DNS - тема, важность который с годами только растет. Здесь стоит обратить внимание на DNS-over-HTTPS надстройку, которая не только обеспечивает подлинность, но и конфиденциальность.

Если говорить про сегодняшний день, то нельзя не упомянуть разработку под названием CoreDNS (написан на Go, более 11 тысяч звезд на Github). Отличительной особенностью этого DNS-сервера является расширяемость: даже базовая функциональность реализована с помощью плагинов и вы легко можете добавить свой.

Быстрого и бесперебойного разрешения имен 🚀

До связи 🤘

TCP-пакеты обычно гуляют по интернету, но и в реальную жизнь иной раз забегают 😆