Алгоритмы *

Просматривая недавно соцсети, я наткнулся на этот скриншот. Разумеется, его сопровождало множество злобных комментариев, критикующих попытку этого новичка в программировании решить классическую задачу computer science: операцию деления с остатком.

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

Поэтому я решил изучить эту идею проверки чётности числа при помощи одних сравнений, чтобы понять, насколько хорошо она работает в реальных ситуациях. Я сторонник высокопроизводительного кода, поэтому решил реализовать это на языке программирования C, потому что он и сегодня остаётся самым быстрым языком в мире с большим отрывом от других (благодаря гению Денниса Ричи).

B-дерево — это структура, помогающая выполнять поиск в больших объёмах данных. Она была изобретена более сорока лет назад, однако по-прежнему используется в большинстве современных баз данных. Хотя существуют и более новые структуры индексов, например, LSM-деревья, B-дерево пока никто не победил в обработке большинства запросов баз данных.

После прочтения этого поста вы будете знать, как B-дерево упорядочивает данные и выполняет поисковые запросы.

$ echo "aaaaaaaa" > test.out
$ xxd test.out
00000000: 6161 6161 6161 6161 0a     aaaaaaaa.

$ gzip -1 test.out
$ xxd test.out.gz
00000000: 1f8b 0808 bf35 6a61 0403 7465 7374 2e6f  .....5ja..test.o
00000010: 7574 004b 4c84 002e 00b6 66d7 ad09 0000  ut.KL.....f.....
00000020: 00

Дисклеймер: эту статью я писал в целях обучения, так что мог допустить некоторые ошибки. Мне нравится заниматься низкоуровневым программированием, но моя основная деятельность сосредоточена на веб-разработке для Microsoft Teams.

Когда я был маленький, то на меня снизошла милость божЫя и ниспослала мне две книжки. Одна книжка была про бейсик для студентов каких-то там ВУЗов, а вторая - «Паскаль в иллюстрациях». По одному из абзацев первой книжки я в принципе научился программировать в пятом классе - там был мозголомающий отрывок с программой, заставляющей нолик летать по экрану, отталкиваясь от стенок. Вторая книжка, отданная мне соседом-алкашом, познакомила с алгоритмами. На дворе стояли 90-е — начало компьютерной эры человечества. Компьютера у меня при этом не было — я видел его пару раз в неделю на компьютерном кружке, ведущей которого была вчерашняя или даже сегодняшняя студентка, отпирающая и запирающая дверь — большего от неё нам и не требовалось.

В этой статье я хочу описать (часть) моего опыта взаимодействия со структурой, именуемой в дальнейшем «яндекс», с точки зрения работника. Опишу собеседования и этап «входа».

Да, уже были статьи про собеседование и даже в эту же структуру, некоторые из них я видел, но не во всём с ними согласен, к тому же конкретно С++ разработчиков я там не видел.

Традиционное определение для операции возведения в натуральную степень (или целую положительную) вводится примерно следующим образом:

Возведе́ние в сте́пень — арифметическая операция, первоначально определяемая как результат многократного умножения числа на себя.

Но более точная формулировка всё же другая:

Возведение числа X в целочисленную степень N — арифметическая операция, определяемая как результат многократного [N по модулю раз] умножения либо деления единицы на число X.

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

Я решил всерьёз выяснить, чему равна эта вероятность в зависимости от длины случайной строки? Можно ли получить явную математическую формулу для ответа? Что, если взять другое слово? Что, если взять другой алфавит?

Обо всём по порядку.

Прошу простить заранее за несколько кликбейтный заголовок )

Не так давно писал в соцсетях хейт‑пост по поводу «алгоритмических секций» при приёме на работу в Яндекс.

Да и многие другие софтверные компании это практикуют и считают навыки написания алгоритмов — чуть ли не самым важным навыком для программистов.

И ставят данной компетенции очень высокий приоритет при приёме на работу.

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

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

В 2020, когда случился локдаун, и к большому сожалению, появилось очень много свободного времени, мне захотелось познакомиться с Python. Начальный опыт c Pascal был еще со школы и универа, поэтому оставалось лишь придумать задачу и пойти её самоотверженно решать на питоне. Интересной задачей показалось смастерить игру змейку, прикрутить к ней мозги в виде перцептрона с парой скрытых слоёв, и путем кнута и яблока обучить цифровое животное выживать в жестоких реалиях двумерного мира :)                               

«У самурая нет цели, есть только путь»

Первый блин на производстве не отличается красотой, но опыт был получен. Наиболее привлекательным мне пришелся генетический алгоритм: отбор успешных змеек, скрещивание, частичная мутация генов и так тысячи раз до результата. Змейки, без указания им правил выживания, в тысячном поколении «понимали», что нужно стремиться съесть яблоко и никуда не врезаться, это вызывало ощущение прикосновения к чуду "It's Alive!!!"

Спустя пару лет, закончив курс по аналитике данных, появилось желание переписать проект, попрактиковаться в более серьезных разделах python и сделать тренажёр со сбором статистики.

В свободное время я восстанавливаю старенькую, но довольно известную игру Pharaoh. Это ситибилдер, выпущенный в прошлом веке и разработанный Impressions Games. Технология рендеринга в этой игре была значительным достижением для своего времени и способствовала созданию впечатляющей атмосферы Древнего Египта, которая погружает игрока в проработанное окружение, удивляет вниманием к мелким деталям и передает богатство и разнообразие древнеегипетских пейзажей. В этой статье я опишу алгоритм отрисовки города, зданий, объектов, анимации и формат карты оригинальной игры.

Планировщик движения беспилотного автомобиля — это алгоритм-помощник, который общается с другими участниками движения посредством манёвров. То есть он действует так, чтобы другим было понятно, куда поедет беспилотник, и сам по действиям других пытается определить, кто куда будет двигаться и почему.

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

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

▍ Введение

template <class ForwardIt, class T, class Compare>
constexpr ForwardIt sb_lower_bound(
      ForwardIt first, ForwardIt last, const T& value, Compare comp) {
   auto length = last - first;
   while (length > 0) {
      auto rem = length % 2;
      length /= 2;
      if (comp(first[length], value)) {
         first += length + rem;
      }
   }
   return first;
}

И это не пузырьковая, а нечто гораздо более тупое.

Как-то после обеда, стоя за чашечкой кофе, мне пришла в голову мысль. Что ведь для того чтобы убедиться что массив отсортирован, надо сделать `n-1` сравнение. Например для массива длины 4 таких сравнения будет 3: