Алгоритмы *

Fizz Buzz — это игра с числами, которая стала неожиданно популярной в мире компьютерного программирования в качестве простой проверки базовых навыков. Правила игры просты: игроки вслух произносят по порядку числа, начиная с единицы. Если число делится на 3, игрок должен сказать вместо него «Fizz». Если число делится на 5, он должен сказать «Buzz». Если оно делится и на 3, и на 5, игрок говорит «FizzBuzz». Вот типичная программа на Python, выводящая нужную последовательность:

for n in range(1, 101):

if n % 15 == 0:

print('FizzBuzz')

elif n % 3 == 0:

print('Fizz')

elif n % 5 == 0:

print('Buzz')

else:

print(n)

А вот её вывод: fizz-buzz.txt. Можно ли усложнить эту программу? Слова «Fizz», «Buzz» и «FizzBuzz» повторяются в этой последовательности периодически. А что ещё у нас есть периодического? Тригонометрические функции! Возможно, нам удастся при помощи этих функций закодировать все четыре правила последовательности в выражении в аналитическом виде. Именно эту задачу мы и исследуем в статье, получив в конце дискретный ряд Фурье, который может получить любое целочисленное n и выбрать для печати соответствующий текст.

В программировании мы привыкли торговаться временем против памяти, но есть ещё один, менее очевидный, компромисс — между тем, что система в принципе умеет выражать, и тем, что о ней потом вообще можно строго сказать. Машины Тьюринга, PDA и DFA, Rust и Python, SAT и SMT, системы типов, макросы и метапрограммирование — всё это разные точки в одной и той же решётке «выразительность против разрешимости», просто по разным осям.

В статье разберемся, почему достаточно «мощные» модели и языки неизбежно становятся плохо анализируемыми, почему это не линейный спектр, а набор пересекающихся измерений, и как этот компромисс проступает в очень практичных вещах — от систем типов и статанализа до архитектурных решений в реальных проектах.

Недавно встретилась по работе интересная задача, прямо на те самые презираемые на интервью алгоритмы. Очередное доказательство, что, по крайней мере, в Гугле алгоритмы нужны. А значит и интервью у них вообще-то не оторваны от реальности.

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

В статье описано как эту задачу решать действительно быстро - за линейную сложность.

Скорее всего, вам доводилось слышать о градиентном шуме, вернее, о той его версии, которая называется шум Перлина и описывает одну конкретную реализацию, сопряжённую с различными оптимизациями на уровне ЦП. Поскольку это невероятно мощный инструмент для творческой работы, он используется практически везде: при создании визуальных эффектов, видеоигр, процедурно-математического искусства и т.д. Да, как следует настроить его — порой тонкая работа, и неисправная реализация на первый взгляд всё равно может выглядеть хорошо или интересно. В конце концов, «смотрится неплохо, а я художник, я так вижу».  

Чтобы глубже и результативнее понять градиентный шум, мы сначала изучим его одномерную версию (в литературе этот случай обычно не рассматривается), а затем медленно пойдём вверх по лестнице измерений в сторону усложнения задачи. Эту тему мы будем рассматривать с точки зрения графического процессора (GPU), а не с точки зрения обычного ЦП. Все примеры кода и анимации, приведённые в этой статье, реализованы на WebGL2/GLSL (надеюсь, это будет не слишком сильно сказываться на производительности). Примеры должны работать на большинстве современных устройств.

Сейчас в открытом доступе мало крупных датасетов сервисов коротких видео, но это уникальный формат для рекомендательных алгоритмов. В отличие от музыки или длинных видео они не могут потребляться в фоновом режиме, а каждый показанный ролик получает от пользователя реакцию. Даже если он не оставит лайк, досмотр видео до конца или пропуск уже считаются обратной связью. Именно поэтому мы выложили в открытый доступ датасет VK-LSVD. С его помощью инженеры и ученые смогут развивать и совершенствовать рекомендательные алгоритмы.

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

Что если есть архитектура, где этого узкого места нет? RISC-V предоставляет гетерогенность принципиально нового уровня, объединяя ключевые компоненты устройства на одном кристалле, что снимает одно из главные ограничений производительности в ML. Но одних процессоров здесь мало — нужна еще экосистема библиотек.

Всем привет, меня зовут Алексей Чубуков. Я аналитик из команды поиска и назначений водителей в Яндекс Такси. В нашей команде мы оптимизируем алгоритмы, которые помогают находить водителей на заказы оптимальным способом, чтобы пользователи быстрее получали машины, а водители бóльшую долю времени проводили с пассажирами. 

В статье я расскажу про виртуальную очередь заказов, которую мы сделали в приложении Яндекс Go. Напомню кратко, как устроен поиск водителей в Такси, поговорим про предпосылки внедрения очереди, посмотрим на то, как устроена очередь и, наконец, обсудим результаты. 

Обожаю игры серии GTA (все, кроме четвертой части). Я бы даже сказал, что многое в них прекрасно: разнообразие сюжетных миссий, выбор транспорта, классные диалоги, тонкая ирония, саркастичный юмор, высмеивание проблем общества, свобода действий, возможность устроить локальный апокалипсис. Однако все это портит поведение ботов-водителей, которые словно намеренно бросаются наперерез игроку, чтобы усложнить ему жизнь. Но так ли это? Действительно ли поведение NPC на дорогах GTA заскриптовано так, чтобы мешать геймерам? Прошу под кат — в поисках правды будем подглядывать за ботами и залезать туда, куда Рокстары не хотят нас пускать.

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

В этой статье я расскажу основные особенности очистки памяти и рассмотрю, как она взаимосвязана с командой TRIM. Детали под катом.

Краткое введение в графы: их устройство, основные типы и способы хранения в программе. Всё изложено просто и по делу — для тех, кто хочет быстро разобраться в теме.

Этот пост станет глубоким разбором того, как мы снизили задержки P95 конечной точки API с 5 до 0,3 секунды при помощи нишевого трюка computer science под названием «фильтр Блума».

Мы расскажем о том, почему конечная точка была медленной, о решениях, которые мы рассматривали для повышения её скорости, и о критериях выбора между ними. Также мы объясним, как всё это устроено внутри.

Привет, Хаброжители!

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

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

Привет! Меня зовут Коля, я руковожу группой разработки геосервисов автономного транспорта. Одно из наших направлений деятельности — разработка инструментов картографии. Обычная дорожно‑уличная сеть подходит людям и приложениям вроде навигаторов, но роботам этого мало: им необходимы HD‑карты, способные описывать окружающий мир с десятками слоёв атрибутов и точностью до сантиметров. Такие карты кладут в основу алгоритмов локализации, навигации и поведения, и именно от их качества зависит безопасность и эффективность автономного транспорта.

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

В этой статье мы разберём, как устроен один из ключевых инструментов — map‑editor, обеспечивающий создание и развитие HD‑карт для роботов, какие технические вызовы встречаются по пути и как мы с ними справляемся. Среди наших технологий — FastAPI и C++ для серверной логики, PostgreSQL с PostGIS для работы с геометрией, интеграция с облачными хранилищами и распределёнными вычислениями, а также элементы автоматизации на базе ML.

Давайте продолжим обсуждение самой неоптимизированной в мире 32-битной библиотеки для работы с плавающей запятой TinyFloat. Библиотека написана на C++ и намеренно избегает встроенных типов плавающей запятой, полагаясь исключительно на 32-битные целые числа. Цель состоит в том, чтобы сделать код максимально читабельным — без бит-хаков и хитроумных уловок.

Библиотека пишется в рамках борьбы с неграмотностью населения, поэтому, я хочу иметь подробную документацию о том, что происходит «под капотом». Оказалось, что лучший способ документировать код C++ — это полностью переписать его на Python :-)

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

Не так давно довелось спонтанно поучаствовать в активности от T‑банка. Кроме всяких «интересных» заданий, там были задачки и на кодинг. Критерием победы в задачах «Стековки» были не O(n), не микросекунды, а краткость кода, твёрдо измеренная в символах, что тоже по своему интересно. «Как написать решение используя минимальное число символов?».

С одной стороны это были задания на компактный алгоритм, с другой стороны — на знания возможностей языка. Я к такому родам задачам не готовился, но по ходу дела мне показалось, что приёмы, которые можно придуматьприменить при таких метриках, вполне стоило бы обобщить, структурировать, и применять уже с меньшими когнитивными нагрузками. Заинтересовало? Добро пожаловать за странными конструкциями и хацкер-бонусом.

В статье разбираются три практических способа интеграции C кода с Python для ускорения вычислений, а так же поясняется причина по которой не используется NumPy. Каждый метод рассматривается с примерами кода и бенчмарками.

Устал от однообразных каруселей? В статье показываю, как шаг за шагом собрать 3D-таймлайн-слайдер с перспективной сеткой, плавной прокруткой и переключением категорий на чистом TypeScript и CSS.

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

Введение

Приготовьтесь, мы совершим путь от единственного кубика до целого воксельного движка! Нам понадобится следующее:

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

API рендеринга! Выбирайте что угодно, эта статья — не туториал по рендерингу.

Если в процессе у вас возникнут вопросы, можете связаться со мной на моём сервере Discord или написать на contact@daymare.net.

У Контура более 10 тыс сотрудников и очень-очень много групповых встреч: около 30 тыс ежемесячно, мы считали. 👀 И бывает так, что нужно собрать сразу нескольких ребят в наиболее удобное для всех время. И начинается вот это вот: зайти на страницу человечка > посмотреть, какое время у него свободно > сопоставить со своим > проверить, а могут ли в это время остальные участники > обнаружить, что нет, и идти заново по кругу смотреть другие слоты, забывая, чё там у кого. 🙄 Да блин!

Мы решили остановить эту котовасию ✋🚫 и добавить в наш внутренний портал (в Контуре используется Стафф) рекомендацию свободных слотов для всех участников встречи. Рассказываем и показываем, как реализовали это.

Откройте любой пулл‑реквест в проекте с любой «чистой архитектурой» и вы скорее всего увидите не обсуждение бизнес‑логики, а срач. «Это нельзя класть в UseCase, это логика домена!», «Зачем тут еще один DTO, мы же просто поле прокидываем!», «Этот интерфейс не нужен, у нас никогда не будет другой реализации!». Полагаю, очень много людей с таким сталкиваются.

Эта статья — о том, почему архитектура из спасения превратилась в тонны говнокода. И, что самое главное, — как прекратить этот хаос и, наконец, начать просто писать код, который работает, а не «следует всем концепциям».