Алгоритмы *

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

Многие слышали о классической игре сокобан, а кто-то наверняка играл в "Мудрого крота" из Роботландии. В этой части мы будем двигать ящики по складу, используя возможности json[b] и геометрического типа point.

ML‑модели применяются в сервисах Яндекса уже много лет, мы накопили большой опыт в их обучении. Статьи об этом коллеги регулярно публикуют, в том числе на Хабре. Но сегодня хочу обсудить другую не менее важную задачу — ускорение инференса (процесса работы на конечном устройстве) моделей. Скорость зависит от разных условий, главным образом от архитектуры и железа, но есть множество интересных способов повлиять на неё. Особенно актуальна проблема тяжёлого инференса при использовании больших языковых моделей (LLM) — на то они и large!

Для команды YandexGPT, в которой я и тружусь вместе со своими коллегами, тема инференса LLM находится в разряде вечных вопросов. С предыдущей статьи прошёл уже почти год, опыта у нас стало больше — получилось протестировать новые подходы, которыми и хочется поделиться сегодня.

Когда говорят о прогнозах погоды, вспоминается история нобелевского лауреата по экономике Кеннета Эрроу, рассказанная Питером Бернштейном в книге «Против богов. Укрощение риска». Во время Второй мировой войны Кеннет Эрроу был синоптиком ВВС США, которому было поручено делать прогнозы на следующие несколько месяцев. Эрроу быстро понял, что долгосрочные прогнозы бесполезны и предложил прекратить их делать, но последовал ответ: «Командующий хорошо понимает, что точность прогнозов крайне низкая. Однако они нужны ему для целей планирования».

Прогнозирование погоды прошло долгий путь. В 650 г. до н. э. вавилоняне пытались предсказать погодные условия, основываясь на характере движения облаков. Три столетия спустя Аристотель написал «Метеорологику», рассуждая о таких явлениях, как дождь, град, ураганы и молнии. Многое из этого оказалось неверным, но это одна из первых попыток подробно объяснить погоду.

Лишь в 1859 году Метеорологическая служба Великобритании выпустила свой первый прогноз погоды для судоходства. Два года спустя служба опубликовала свой первый публичный прогноз погоды. Хотя метеорологические измерения со временем улучшились, масштабные изменения в прогнозах произошли с использованием компьютерного моделирования. Это началось столетие спустя, в 1960-х годах.

С тех пор прогнозы значительно улучшились.

Метеорологическое бюро заявляет, что его четырехдневные прогнозы сейчас так же точны, как и однодневные прогнозы 30 лет назад.

Национальный центр ураганов США публикует данные об «ошибке отслеживания» ураганов и циклонов — ошибке в том, где обрушивается ураган. Это показано на диаграмме ниже, начиная с 1960-х годов.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

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

Вопрос

Я знаю, как декодировать UTF-8 с помощью битовой математики и таблиц поиска (см. https://github.com/skeeto/branchless-utf8), но если я хочу преобразовать кодовую точку UTF-8, то можно ли сделать это без ветвлений?

Для начала, можно ли как-то написать эту функцию на C, которая возвращает количество байтов, необходимых для хранения байтов UTF-8 кодовой точки, без использования ветвления? Или для этого потребуется огромная таблица поиска?

В 1987 году вышла дебютная научно-популярная книга Джеймса Глика «Хаос. Создание новой науки», впервые опубликованная на русском языке в переводе издательства «Амфора» и выложенная здесь. Эта книга оживила интерес к теории самоорганизующихся систем, сформулированной в середине XX века в работах Германа Хакена (1927-2024) из Штутгартского университета, посвящённых синергетике. Смежные исследования по физике неравновесных систем принадлежат Илье Романовичу Пригожину (1917 - 2003),  франко-американскому физику российского происхождения. В основе этих работ лежит идея о том, что существуют такие системы, нарастающая энтропия в которых постепенно выравнивается, и общая структура системы остаётся относительно неизменной, несмотря на то, что в отдельных частях системы энтропия продолжает нарастать. В том же 1987 году появилось удивительное исследование Пера Бака, Чао Танга и Курта Визенфельда, в котором они описали модель песчаной кучи.    

Феномен связан с изучением и моделированием самоорганизующихся систем и их устойчивости, а также смыкается с исследованием фракталов, степенных рядов и клеточных автоматов. В контексте фракталов эту тему рассматривал на Хабре уважаемый Андрей Заболотский @Browning в статье «Фракталы в песках или больше трёх не собираться». Если желаете вместо моего текста почитать строгое, но вполне популярное и увлекательное изложение данной темы — отсылаю вас к статье уважаемого Никиты Калинина «Песочная модель», размещённой на сайте МФТИ. Под катом я расскажу, как эта модель работает и какие неожиданные вопросы подбрасывает.

Давным‑давно, когда мир ML состоял из бустингов, линейных моделей и статистических подходов, перед нашей командой API Яндекс Карт стояла задача сделать качественный Геокодер. Это алгоритм, который конвертирует текстовые запросы пользователей в поисковой строке карт в координаты и обратно. Он нужен, когда люди вводят адреса с ошибками, опечатками или народными наименованиями, например «Мяснитская 8». Геокодер должен понять, что имелось в виду «улица Мясницкая, дом 8/2», и вернуть на карте отметку с точной локацией и координатами.

Разработанный для России Геокодер отлично справлялся, но мы хотели найти способ быстро адаптировать это решение к адресным системам других стран. Технологические ограничения не позволяли быстро адаптировать решение, поскольку для каждой страны требовалась разработка собственных правил геокодирования, которые бы учитывали различия и языковые особенности. Однако появление и развитие алгоритмов deep learning открыло новые горизонты: методы active learning, аугментации данных и contrastive learning позволяют значительно улучшить итоговое качество геокодирования и учитывать нюансы различных адресных систем.

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

const fizzbuzz = (n: number)=>`${n%3 ? '' : 'Fizz'}${n%5 ? '' : 'Buzz'}`;

Как создать быстрый код на C++? Мы будем разбираться в современных техниках оптимизации: кэш-локальности, кастомных аллокаторах и многопоточности. Практические примеры и результаты тестов.

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части совсем простая идея по одновременному решению систем линейных уравнений "пачками".

Вы когда-нибудь хотели узнать, как работала предварительно вычисленная видимость в Quake? Я хотел, поэтому написал программу vis.py, воссоздающую этот алгоритм на Python. В этой статье представлена вся информация, необходимая для понимания vis, — инструмента, применявшегося в Quake, Half-Life и играх на Source Engine.

В процессе разработки Quake возникла проблема перерисовки (overdraw), то есть многократной записи одного и того же пикселя во время рендеринга кадра. Видимым остаётся лишь последний цвет, а все предыдущие записи оказываются лишней тратой ресурсов. Это плохо, если в вашей игре используется программный рендеринг, и так выжимающий последние соки из компьютера середины 90-х годов.

Как снизить объём перерисовки? Давайте начнём с высокоуровневого обзора возможных решений.

В современном мире данных нагрузка на базы данных стремительно растёт. Когда один сервер перестаёт справляться с объёмом запросов, встаёт вопрос о масштабировании: как эффективно распределить нагрузку, сохранив высокую производительность и доступность?

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

Привет, Хабр! Эта статья посвящена тестированию точности библиотек математических функций (libm). Мы обсудим, где эти библиотеки используются, почему они должны быть не только высокопроизводительными, но и высокоточными. Поймем, откуда в корректных, на первый взгляд, вычислениях берутся ошибки и как их избежать. Узнаем, как устроено большинство тестов в стандартных математических библиотеках и почему они не всегда работают. И наконец, ответим на вопрос, как одним тестом полностью покрыть код математической функции. Без воды, регистрации и громоздких формул.

Всё началось в далёком 2004 году, когда я учился в СПб ГУ ИТМО на кафедре Прикладной и компьютерной оптики (ПиКО). Однажды на лекции по "Основам оптики" преподаватель рассказал о голографии. Эта тема меня сразу увлекла, и, несмотря на то, что многое тогда было непонятно, проявленный интерес не угас до сих пор. Помню, как лектор объяснял свойства голограмм, а так же привел схему связывающую параметры записи с типом получаемых голограмм: Габора, Лейта и Упатниекса, Денисюка и другие (рис. 1). Это был тот не редкий момент, когда: «Очень интересно и ничего не понятно»

В этой челлендж-серии статей попробуем использовать PostgreSQL как среду для решения задач Advent of Code 2024.

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

В этой части используем двойную рекурсию для "раскраски" регионов на карте.

Привет! Меня зовут Павел Астахов, я работаю в департаменте системного анализа SM Lab. Сегодня расскажу про проектировочную документацию и её стандартизацию в нашей компании.

Причины внедрения стандартизации

Причина 1. Сотрудники

Департамент системного анализа появился в 2020 году: на тот момент нас было 50 человек в 20 командах; к 2024 году мы сильно разрослись и нас стало уже 260 системных аналитиков, которые трудились в 85 командах. Рост и увеличение масштаба департамента выявили проблемы, которые ранее не были видны и постепенно стали выходить на первый план.

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

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

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

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