Алгоритмы *

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

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

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

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

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

Так вышло, что спустя более чем 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:

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

С тех пор у меня накопилось более 400 решённых задач на LeetCode. Теперь я уверена, что такие платформы как LeetCode, HackerRank или CodeWars, при правильном подходе, способны поднять профессиональные навыки любого разработчика на новый уровень.

Ресурсы

• Build Your Own Text Editor — наверно, самый фундаментальный пост о создании текстового редактора с нуля, который я видел. Это превосходный туториал на случай, если вы хотите начать писать собственный текстовый редактор. Стоит заметить, что в редакторе из этого туториала в качестве внутренней структуры для текста используется, по сути, вектор строк.
• Text Editor: Data Structures — отличный обзор множества структур данных, которые можно использовать при реализации текстового редактора. (Спойлер: как минимум одна из них будет рассмотрена в моём посте)
• Плейлист Ded (Text Editor) на YouTube — это потрясающая серия, в которой @tscoding фиксирует процесс создания с нуля текстового редактора. Эти видео стали для меня источником вдохновения.

Зачем?

1. Я хотел заняться проектом, непохожим ни на один свой прошлый.
2. Я хотел создать инструмент, которым смогу пользоваться.
3. Мне всегда хотелось глубже разобраться с созданием собственных структур данных.

То, что ChatGPT может автоматически генерировать что-то, что хотя бы на первый взгляд похоже на написанный человеком текст, удивительно и неожиданно. Но как он это делает? И почему это работает? Цель этой статьи - дать приблизительное описание того, что происходит внутри ChatGPT, а затем исследовать, почему он может так хорошо справляться с созданием более-менее осмысленного текста. С самого начала я должен сказать, что собираюсь сосредоточиться на общей картине происходящего, и хотя я упомяну некоторые инженерные детали, но не буду глубоко в них вникать. (Примеры в статье применимы как к другим современным "большим языковым моделям" (LLM), так и к ChatGPT).

17 октября 2014 года в мотеле маленького городка Хаммонд, Индиана, был обнаружен труп 19 летней Африки Харди. Вызванные на место полицейские почти сразу пришли к выводу, что это было убийство. На поиски убийцы ушло меньше суток — его обнаружили по записям камер наблюдения, установленных возле мотеля, а также по анализу телефонных разговоров жертвы (в номере был найден её телефон).

43-летний Даррен Ванн был арестован уже 18 октября и, как ни странно, совсем не был удивлён появлению полиции. Когда наручники защёлкнулись на его запястьях, Даррен повернулся и сказал полицейскому: «Наконец-то вы меня поймали». Так попался серийный убийца, жертвами которого стали ещё минимум шесть женщин. Но как полагали детективы, на самом деле счёт приближался к 20. 

Примечательно в этой истории то, что полиция могла бы поймать Даррена Вана ещё за 4 года до этого. Но никто не хотел слушать Томаса Харгроува — бывшего журналиста, который помогает искать маньяков с помощью собственного алгоритма, о котором и пойдёт далее речь.

На Хабре можно найти немало статей, посвящённых оптимизациям поиска кратчайшего пути на графе. Я расскажу ещё про еще один подход. Речь пойдёт о распараллеливании алгоритма A* и исполнении его на двух потоках, а также о сложностях, с которыми я столкнулся при реализации, и их преодолении.