Обновить
274.54

Алгоритмы *

Все об алгоритмах

Сначала показывать
Порог рейтинга
Уровень сложности

Дело о несрабатывающем тайм-ауте. Проблемы гистограмм Prometheus

Уровень сложностиСредний
Время на прочтение20 мин
Охват и читатели2K

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

Читать далее

Go 1.24: принципы работы и преимущества обновленной map

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели9.3K

В феврале 2025 года разработчики Go выпустили версию 1.24, в которой значительно улучшили производительность языка. Одно из ключевых изменений коснулось структуры map — встроенного типа данных, предназначенного для хранения и быстрого поиска значений по уникальному ключу. Новая реализация повысила эффективность работы map, оптимизировала использование памяти и ускорила операции поиска, вставки и удаления элементов. 

Привет, Хабр. Мы backend-разработчики SimbirSoft Павел и Алексей. В этой статье подробно разберём, как именно изменился механизм работы map и какие преимущества это даёт.

Go🚀

Магия персональных рекомендаций, или как нейросеть Яндекс Карт подбирает места под интересы пользователей

Время на прочтение9 мин
Охват и читатели4K

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

Меня зовут Владимир Жуков, я руководитель группы магии рекомендаций Карт (да, это официальное название), и в этой статье я расскажу, чем наша рекомендательная система отличается от технологий других сервисов, по каким метрикам мы измеряем её качество и как обучаем нейросеть находить тот самый ресторан, музей или парк, который надолго останется фаворитом.

Читать далее

Проектируем веб-страницу, отображающую миллион элементов

Уровень сложностиПростой
Время на прочтение7 мин
Охват и читатели4.2K

Может ли браузер справиться с миллионом элементов? Если вы когда-нибудь пробовали рендерить в браузере миллион элементов <div>, то знаете, что происходит — он вылетает, зависает и перестаёт реагировать.

Недавно мы выпустили фичу, привлёкшую большое внимание — загрузку и визуализацию до миллиона спанов на нашей странице детализации трассировок. Это вызвало любопытство у пользователей и разработчиков, поэтому многие начали задавать вопрос: как нам это удалось?

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

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

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

Читать далее

JavaScript: структуры данных и алгоритмы. Часть 10

Уровень сложностиСредний
Время на прочтение30 мин
Охват и читатели1.5K


Привет, друзья!


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


Сегодня мы продолжим разбирать алгоритмы для работы с графами.


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


Структуры данных и алгоритмы на MyJavaScript.


Интересно? Тогда прошу под кат.

Читать дальше →

Плавающие запятые и ящики

Уровень сложностиСредний
Время на прочтение15 мин
Охват и читатели1.5K

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

Читать далее

Искусственный интеллект и алгоритмы в энергетике: применение, преимущества, перспективы

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели5.8K

Энергетические системы — одни из самых сложных инженерных систем современности. С развитием возобновляемых источников и увеличением нагрузок их управление становится все более трудоемким. Традиционные методы расчета и планирования начинают уступать место интеллектуальным алгоритмам. Искусственный интеллект (ИИ) и продвинутые алгоритмы позволяют анализировать огромные массивы данных и принимать решения быстрее и точнее, чем было возможно раньше. Уже сегодня исследователи и инженеры применяют машинное обучение, нейросети и методы оптимизации для прогнозирования потребления, планирования сетевой инфраструктуры и автоматизации управления энергосистемами. Например, переход к углеродно-нейтральной энергетике и распределенной генерации приводит к такой сложности режимов работы сетей, с которой традиционные методы не справляются.

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

Читать далее

Книга: «System Design: пережить интервью»

Время на прочтение3 мин
Охват и читатели8.9K
Привет, Хаброжители!

Собеседования по проектированию систем — это боль. Даже опытные разработчики спотыкаются о бесконечные open-ended вопросы и доску, на которой нужно за 45 минут набросать архитектуру, способную пережить апокалипсис.

Хорошая новость: наша новинка поможет успешно пройти интервью.

Книга Чжиюна Таня «System Design: пережить интервью» — это гайд по выживанию. В ней нет воды, только практика: как разбирать задачи, выбирать решения и уверенно их продавать эксперту. Автор знает, о чем говорит — его подход помог разработчикам попасть в Amazon, Apple, ByteDance, PayPal и Uber.
Читать дальше →

JavaScript: структуры данных и алгоритмы. Часть 9

Уровень сложностиСредний
Время на прочтение44 мин
Охват и читатели2.3K


Привет, друзья!


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


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


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


Интересно? Тогда прошу под кат.

Читать дальше →

NVIDIA cuDF и 100-кратное ускорение чтения данных формата JSON Lines в pandas

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели1.2K

JSON — это широко распространённый формат, применяемый для хранения информации, основанной на обычном тексте. Он поддерживается самыми разными системами, обеспечивая их взаимодействие. Чаще всего это — веб-приложения и большие языковые модели (Large Language Model, LLM). Хотя JSON-данные удобны для восприятия человеком, их сложно обрабатывать, используя инструменты из сфер Data Science (наука о данных) и Data Engineering (инженерия данных).

JSON-данные часто существуют в виде JSON-строк (формат JSON Lines), отделённых друг от друга символами перевода строки (NDJSON, Newline-Delimited JSON). NDJSON используется для представления записей, входящих в состав набора данных. Часто первым этапом обработки данных является чтение файлов формата JSON Lines и преобразование их в объекты DataFrame (датафрейм).

В это материале мы сравним производительность и функционал API, доступных в Python и применяемых для преобразования формата JSON Lines в датафреймы.

Читать далее

Библиотека для кэширования Caffeine: анализ кода

Время на прочтение18 мин
Охват и читатели3.5K

То и дело, прожигая время за чтением reddit, я натыкаюсь на очередной пост, в котором упоминается метод S3 FIFO и говорится, что он лучше LRU (вытеснение реже всего используемых значений) — потому, что даёт более низкий процент промахов кэша. Видные компании, в частности, RedPandas, Rising Wave и Cloudflare уже внедрили S3 FIFO у себя на различных мощностях, что только подогрело мой интерес к нему. Кэши — чертовски интересная тема, а по работе мне приходится сильно полагаться на работу с кэшами при обслуживании нескольких сервисов. Так что я был уверен, что рано или поздно мне потребуется протестировать S3 FIFO или, как минимум, удостовериться, что я понимаю ключевые идеи, заложенные в этой технологии.

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

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

Читать далее

Более быстрые хеш-таблицы: претенденты на место SwissTable

Уровень сложностиСредний
Время на прочтение11 мин
Охват и читатели9.8K

24 ноября 2021 года на сайте ArXiv.org была опубликована научная статья «Крошечные указатели» (Tiny Pointers) с описанием новой структуры данных — «крошечных» указателей, которые указывают путь к фрагменту хранимых данных и занимают меньше памяти, чем традиционные указатели.

Осенью 2021 года эту статью заметил Андрей Крапивин (Andrew Krapivin), студент Ратгерского университета в Нью-Джерси, и не придал ей особого значения, пишет Quanta Magazine, журнал о последних достижениях в математике (перевод статьи на Хабре). Только через два года он нашёл время, чтобы внимательно ознакомиться с материалом. И понял, насколько это прорывное изобретение, если применить его для оптимизации хеш-таблиц.

Данная тема уже упоминалась на Хабре, но заслуживает более подробного обсуждения.
Читать дальше →

SQL HowTo: работаем с массивами (Advent of Code 2024, Day 23: LAN Party)

Уровень сложностиПростой
Время на прочтение7 мин
Охват и читатели1.2K

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

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

Применяем простые операции над массивами, чтобы определить связность графов.

Читать далее

Ближайшие события

Закрытие уязвимости Spectre в режиме безопасных вычислений на Эльбрусе

Уровень сложностиСредний
Время на прочтение9 мин
Охват и читатели1.6K

Приветствуем!

Уязвимость Spectre обнаружили ещё в 2017 году. С тех пор разработчики Intel, AMD и ARM пытаются её закрыть программными средствами. Пока не очень удачно — программные заплатки не защищают полностью, а производительность процессоров снижается. Разберемся, есть ли уязвимость Spectre на российских процессорах Эльбрус и что с ней делать.

Читать далее

SQL HowTo: оконные функции (Advent of Code 2024, Day 22: Monkey Market)

Уровень сложностиПростой
Время на прочтение10 мин
Охват и читатели1.6K

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

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

Используем оконные функции, чтобы вычислить "третью производную".

Читать далее

Упрощать сложно. История одного провала

Уровень сложностиПростой
Время на прочтение13 мин
Охват и читатели6K

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

В общем, проблема оказалась отнюдь не мала

Три теоремы о сортировках

Уровень сложностиСредний
Время на прочтение12 мин
Охват и читатели9.3K

Я знаю многих программистов и руководителей в IT компаниях, которые недолюбливают математиков и в частности считают их далёкими от жизни идиотами из-за их утверждений в духе "нельзя отсортировать последовательность быстрее, чем за nlogn" -- ведь это очевидным образом неверно, есть же сортировка подсчетом и radix sort. Нюанс в том, что описанное выше -- это распространённая некорректная трактовка одной из ключевых теорем об алгоритмах сортировок, корректное утверждение выглядит так: "не существует алгоритма, который бы гарантированно находил перестановку n элементов, приводящую к возрастающему порядку, быстрее чем за nlogn используя только операции попарного сравнения". В этом утверждении больше слов, оно более сложно в плане когнитивного восприятия, ключевой момент обозначил жирным шрифтом, чувствуете разницу?

В статье хочу рассказать об этой теореме и ещё о двух, на которые я наткнулся когда вел занятия по информатике в 9-11 классах будучи студентом старших курсов. Эти теоремы для меня были удивительным открытием, радовался вне себя когда вывел сам одну из них - её я не встречал ни в одном учебнике по информатике. В последствии все три теоремы были найдены в недрах Кнута, но чёрт побери, их поиск был сложнее, чем вывод!

Если я ещё не убедил Вас прочитать статью, то вот моя последняя попытка: в статье объясню почему пузырёк -- это бесполезная фигня, но внезапно практически также работающая сортировка вставками -- это супер важная сортировка, являющаяся частью std::sort в MSVC, GCC и Clang. Расскажу, каким интересным свойством оптимальности обладает сортировка выбором, являющаяся в теории такой же неэффективной как пузырёк.

Читать далее

Процедурная генерация двухмерной полигональной карты

Время на прочтение14 мин
Охват и читатели4.5K

Привет Хабр ! Это моя первая статья на тему процедурной генерации. Здесь я рассмотрю конкретную задачу по генерации, её решение и опишу ключевые использованные принципы. Пишу эту статью для того, чтобы поделиться идеями и опытом, которых мне не хватало, когда я взялся за дело две недели назад. Я не буду делать полный разбор проекта, а лишь опишу и визуализирую принцип.

Читать далее

Разгон Мандельброта: SIMD с бубнами, OpenMP и CUDA

Уровень сложностиСредний
Время на прочтение16 мин
Охват и читатели2.4K

Построение множества Мандельброта — классический пример чрезвычайно параллельной задачи (embarrassingly parallel problem).

На первом курсе я впервые столкнулся с такой проблемой: тогда мы изучали SIMD-инструкции в курсе архитектур вычислительных систем. Эта тема сразу меня увлекла, и я захотел углубиться в дальнейшие оптимизации, но в течение семестра мне не хватало ни времени, ни знаний. Спустя год я решил восполнить этот пробел.

Вначале мы разберем наивную реализацию, поиграемся с интринсиками (intrinsics) и, не теряя переносимости, заставим компилятор генерировать нам SIMD-инструкции. Далее добавим многопоточность и в заключение обесценим все наши старания несколькими строчками на CUDA.

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

Читать далее

Дедупликация объявлений: как мы боремся с одинаковыми размещениями

Уровень сложностиСложный
Время на прочтение13 мин
Охват и читатели1.9K

Привет! Меня зовут Кирилл Сергеев, я ML-инженер в Циане. В этой статье я расскажу, как мы решили задачу дедупликации объявлений о недвижимости, разработав систему на основе трёх моделей. Эта система автоматически находит и объединяет дублирующиеся объявления, помогая пользователям видеть только актуальную и уникальную информацию.

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

Читать далее

Вклад авторов