Алгоритмы *

Привет! Меня зовут Brent «Brentmeister» Randall (Брент Рэндалл). Я — инженер из команды Gameplay Integrity, которая занимается игрой VALORANT. В сферу нашей ответственности входит система сборки игры, фреймворки, используемые для автоматизации различных задач, производительность игрового клиента и серверов. Именно последнему пункту этого списка и посвящена данная статья. Я поделюсь с вами историей поиска подходов, позволивших вывести производительность наших серверов на оптимальный уровень.

На самых ранних этапах разработки проекта мы уже знали о том, что VALORANT отличается весьма жёсткими требования к производительности игровых серверов. Надеюсь, мне удастся дать вам некоторое представление о том, почему это так, и о том, как были достигнуты наши амбициозные цели. В самом начале серверный кадр (server frame, цикл обработки данных на сервере) длился 50 мс. А после завершения оптимизации нам удалось сократить это время до менее чем 2 мс. Всё это сделано благодаря анализу и оптимизации кода проекта, а так же — благодаря подстройке «железа» и тюнингу ОС.

2ГИС с самой первой версии навигатора умеет строить разные виды маршрутов — автомобильные, пешеходные, маршруты на общественном транспорте — на мобильных устройствах без доступа к интернету, но только внутри городов.

С 2019 года 2ГИС также умеет строить маршруты между городами, но только при наличии интернета.

Уже давно наши пользователи просили дать возможность строить междугородние маршруты без доступа к сети. И вот, мы наконец сделали это.

Большинство SIMD инструкций узконаправленны, например применяют бинарную операцию параллельно для нескольких чисел, упакованных в длинный регистр. Применение таких операций прямолинейно и в большинстве случаев компилятор сам оптимизирует код с использованием таких инструкций. Например компилятор легко соптимизирует таким образом проверку несложного предиката на массиве или например суммирование элементов массива. Есть однако и более универсальные инструкции, в частности довольно много всякого рода манипуляций с битами внутри регистра. В этой статье хочу рассказать о двух таких инструкциях: уже давно присутствующей PSHUFB и довольно новой GF2P8AFFINEQB, расскажу как с их помощью делать побайтовую обработку общего вида и приведу пару примеров с известными операциями такими как popcount, подсчет четности, разворот битов числа.

Первая часть статьи

В первой части мы обсудили философские основы и принципы работы рейтинговой системы, где у каждого человека разная сила голоса, отражающая его полезность для конкретного сайта (офелократия). Теперь перейдём к техническим деталям реализации на MySQL.

Disclaimer: это перевод статьи, основанной на видеоэссе.

Автор — Томас Флайт

Не знаю, как у вас, но когда я натыкаюсь на заполонившие интернет изображения и видео, которые были созданы ИИ, у меня возникает очень странное чувство. Это своего рода инстинктивное ощущение, что с этими изображениями что‑то не так.

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

Или это инстинктивное чувство, что что‑то «не так» с «искусством», созданным ИИ, указывает на нечто более глубокое и истинное? Не сообщает ли оно нам что‑то важное о том, что такое искусство для нас, для людей? О том, что, каким бы ни было искусство, попытка создать его с помощью ИИ — это своего рода насилие?

Как-то раз моя пятилетняя дочка, вернувшись домой из детского садика, сообщила мне и моей жене, что математика — тупая штука (!). С тех пор мы не покладая рук работаем (пока что успешно), стараясь увлечь её всевозможными математическими интересностями, а теперь ещё и гордимся её успехами в математике. Одна из наших наиболее удачных находок привела к тому, что теперь дочь очень интересуется фракталами вообще. Особенно ей нравится смотреть видеоролики, где с увеличением показаны множества и оболочки Мандельброта, а вдобавок есть капусту романеско. Благодаря этому увлечению дочери, я стал больше задумываться о фракталах, а также о том, как они соотносятся с особенно волнующей меня темой — искусственными нейронными сетями.

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

Да, я знаю, тема кажется избитой. Но когда я впервые осознала, что одни и те же принципы работают на всех уровнях, от крошечного L1-кэша до распределенного Redis-кластера — это было похоже на инженерное просветление. Предлагаю и вам пройти этот путь вместе со мной.

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

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

В этой статье я расскажу про свой эксперимент: я создал в Unity симуляцию радиоуправляемых машинок, которые эволюционируют. «Мозгом» каждой машинки является электронная схема. Я заставил эти схемы мутировать(случайно меняться) и скрещиваться(обмениваться частями), чтобы создавать новые модели машин и улучшать их. Его «интеллект» и поведение меняются в зависимости от того, сколько блоков онa успешно поднимает.

Недавно мы переделали наши внутренние инструменты, визуализирующие компиляцию JavaScript и WebAssembly. При работе оптимизирующего компилятора Ion мы теперь можем генерировать интерактивные графы, демонстрирующие, как конкретно обрабатываются и оптимизируются функции.

Вы можете сами поэкспериментировать с этими графами в оригинале статьи. Просто введите какой-нибудь код на JavaScript в функцию test, и наблюдайте за созданием графа. Также там можно щёлкать и перетаскивать граф, менять масштаб при помощи колеса мыши с зажатым Ctrl и перетаскивать ползунок вниз, чтобы изучить процесс оптимизации.

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

Разумеется, мы не первые, кто начал визуализировать внутренние графы компиляторов, и не первые, кто сделал их интерактивными. Но меня не устраивали результаты работы популярных инструментов наподобие Graphviz и Mermaid, поэтому я решил создать алгоритм специально под наши потребности. Получившийся алгоритм прост, быстр, создаёт на удивление высококачественный вывод и его можно реализовать в менее чем тысяче строк кода. В этой статье я объясню алгоритм и конструкторские решения, лежащие в его основе.

Эпоха больших языковых моделей (LLM, Large Language Model) снова и снова ставит перед нами вопрос о том, что отличает великую прозу от просто хорошей.

Отвечая на этот вопрос, обычно довольно расплывчато рассуждают о «стиле»: о неуловимом, мистическом качестве, которое свойственно таким людям, как Хемингуэй, Вулф или Вудхаус. Это — как один судья сказал о порнографии: мы узнаём её, когда видим. Мы способны узнать стиль текста, мы даже можем его сымитировать. Но можем ли мы его измерить? Можем ли мы создать для него производственную функцию?

Большинство современных LLM выдаёт хорошие тексты. Даже — грамотные. Но — тексты это стандартные. Стилистически безвкусные. И что — так будет всегда? Этот вопрос меня тревожит с тех самых пор, как я начал пользоваться LLM. Они созданы из слов, и при этом не могут как следует словами пользоваться. Почему мы не способны создать ИИ, который пишет хорошие тексты?

Тут совершенно естественным образом возникает такой вопрос: можем ли мы задать какие-то (или хоть какие-нибудь) количественно измеримые, эмпирические «сигнатуры» хороших текстов? Если это возможно — значит такие вот «характеристики» можно использовать для обучения моделей, которые смогут лучше писать. Так случилось, что этот вопрос завёл меня, так сказать, в кроличью нору, породив проект, который я называю Horace.

Я выдвинул гипотезу, в соответствии с которой, приближённо говоря, волшебство текстов, написанных людьми, уместно сравнивать не с понятием «статистическое среднее», а с понятием «дисперсия». Полагаю, эту мысль нельзя назвать строгим правилом, но она, как мне кажется, ближе к истине, чем альтернативные идеи. Магия человеческих текстов заключается в осознанном, целенаправленном отступлении от ожидаемого. Речь идёт о ритме (rhythm), о темпе (pace), о музыкальности (cadence) текста.

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

В каждом моём профессиональном и личном проекте рано или поздно требовался diff для визуализации изменения или применения патча. Однако меня никогда не устраивала ни одна из свободно доступных библиотек diff. В профессиональной деятельности это никогда не вызвало особых проблем, но в личных проектах я копировал и модифицировал из проекта в проект собственную библиотеку. Однажды я рассказал об этом коллеге, и тот наставил меня на путь публикации моей библиотеки на Go (порта библиотеки на C++, которую я раньше копировал и модифицировал). И оказалось, что я сильно недооценивал то, насколько близка моя библиотека к возможности публикации!

Как бы то ни было, я опубликовал её и узнал много нового об алгоритмах diff. Библиотеку можно найти по адресу znkr.io/diff, а в этой статье я расскажу о своих открытиях. Я ещё не завершил освоение, поэтому планирую дополнять статью в процессе изучения.

Автор: Шерстнев Павел

Что если модель могла бы проектировать саму себя? Подбирать архитектуру, параметры, операторы — без эксперта, без ручного тюнинга и десятков итераций? Эволюционные алгоритмы позволяют это сделать. Я собрал их в рабочую технологию — Thefittest — open-source проект, где эволюция используется для построения и оптимизации моделей машинного обучения.

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

Всё было сделано на хранимых процедурах MySql и работает как часы без всякого обслуживания уже 14 лет.

Все знают о Leetcode — его можно любить, ненавидеть, презирать или даже бояться, но равнодушным точно не останется никто.

Эта статья — впечатления о моём 600-дневном марафоне на этой платформе, динамике моих скилов и ответе на главный вопрос «надо ли решать там задачи?».

Все было спокойно, пока мы с другом не заключили спор — сможем ли мы решить 100 задач до конца 2023 года? А это было 50 задач всего за 1 месяц — декабрь.

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

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

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

24 февраля 2024 в течении недели Leetocde предлагал неплохие и не очень сложные задачи на дейли челлендже, и у меня случайно получился стрик в районе 10 дней подряд.

Сбивать стрик было как‑то жалко — это же целых 10 дней. Так и началась долгая история в 600 дней...

1 августа 2012 года, торговая фирма Knight Capital развернула новую версию торгового ПО SMARS. Из‑за ошибки при развертывании на одном из восьми серверов осталась старая тестовая версия кода, из‑за чего торговый робот начал неконтролируемо рассылать миллионы ошибочных заявок на покупку и продажу акций. Этот процесс длился около 45 минут и привел к убыткам в размере примерно 440 миллионов долларов — почти весь капитал компании.

​Ключевая проблема мониторинга состояла в том, что система PMON (Position Monitor) полностью полагалась на ручной мониторинг: она не генерировала автоматических оповещений и не выделяла превышение лимитов. Трейдеры Knight видели аномальную активность в логах, но не понимали контекст:

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

Привет, Хабр!

Меня всё также зовут Андрей Гринблат. В прошлых материалах я рассказывал о построении фотореалистичных изображений трёхмерных фракталов (часть 1 и часть 2). Это — завершающая статья цикла, в ней я разберу визуализацию оболочки Мандельброта, четырёхмерных аналогов множеств Мандельброта и Жюлиа, и рассмотрю гибридные фракталы.

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

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

в github, vscode и windows абсолютно каждое обновление уже несколько лет связано только с "ИИ", при этом ни один реальный показатель этих программ не стал лучше. В каждый поисковой запрос встроен ИИ, а качество поиска в гугле стало хуже (считал ли кто-то, сколько электричества ушло на это?)

Компилятор go переписывают на go, JavaScript существует больше 20 лет, появился TypeScript, но он... Всё также компилируется в обычный JavaScript, даже более объёмный, чем написанный вручную. До сих пор все оптимизации передачи джаваскрипта по сети не пошли дальше удаления пробелов из исходного текста, хотя на поверхности лежит трансляция TypeScript в бинарный JS, который позже напрямую быстрее интерпретируется и тратит в разы меньше сетевого трафика

Недавно я зашёл в браузер хром и решил поискать небольшую фразу в довольно объёмном файле.