Алгоритмы *

Разработка парсер генератора ISPA: что реализовано и какие планы на будущее.Гибкий парсер нового поколения с теми функциями, которых давно не хватает существующим решениям.

Как вы, наверно, знаете, из-за наличия в компьютере различных кэшей (L1, L2, L3...) и того, что операции с памятью выполняются с линиями кэша размером примерно 64 байт каждая, для обеспечения максимальной производительности мы должны писать программы, обеспечивающие локальность.

(Разумеется, диск здесь не показан)

Но насколько хорошо вы это осознаёте? Допустим, у нас есть массив чисел с плавающей запятой и массив индексов первого массива. Есть программа, складывающая числа из первого массива в порядке, определяемом вторым массивом. То есть в этом примере мы будем складывать ε + α + δ + ζ + β + γ в таком порядке:

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

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

2. Сколько в среднем тратится на каждый элемент в порядке от первого до последнего?

3. Насколько медленнее произвольный порядок последовательного в случае массивов, умещающихся в RAM?

4. Насколько медленнее произвольный порядок последовательного в случае массивов, не умещающихся в RAM?

5. Достаточно ли стандартного тасования Фишера-Йейтса для массивов перемешанных индексов для получения произвольного порядка?

6. Насколько медленнее порядок от первого до последнего в случае массивов, не умещающихся в RAM, при использовании файлов с отображением в память?

7. Максимально ли быстры файлы с отображением в память?

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

Почему при сложениии одинаковых чисел в разном порядке получаются разные результаты?
Как мининмизировать ошибки округления или избавиться от них совсем?

Интервалы, интервалы,‑ где тут лево, где тут право...

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

На практике однако встречаются и более сложные задачи. Допустим, например, что в некой гостинице есть два свободных номера. Но один свободен со 2-го по 5-е число, а второй - с 6-го по 10-е. Клиент интересуется, есть ли возможность поселения на 8 дней? Правильный ответ - "да, есть, но с переселением (лесенкой)". Для такого ответа программа должна уметь распознать, что интервалы [2, 5] и [6, 10] являются смежными , а значит, их можно сложить, получив общий доступный интервал [2, 10], длина которого (9) превышает запрашиваемый.

Другая более редкая, но и более интересная задача - определить область пересечения двух множеств интервалов. Сложность в том, что количество интервалов в сравниваемых множествах может быть произвольным. Программист, который умеет только в сравнения "на меньше/больше" (или даже в between), столкнется при реализации с трудностями формализации.

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

Привет, Хабр! В предыдущей части мы рассматривали базовые методы цифровой обработки изображений для задачи сегментации спутникового снимка.

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

Привет, Хабр! Мы – Даниил Соловьев и Михаил Никитин из команды направления распознавания лиц. Сегодня фокусируемся на задаче распознавания лиц на изображениях низкого разрешения (low resolution face recognition, low-res FR). Она актуальна в первую очередь при анализе данных видеонаблюдения, так что если перед вами сейчас стоит подобная задача (или просто интересно, как она решается) — статья для вас. Расскажем про проблемы и сложности распознавания лиц низкого разрешения, подходы к решению задачи, в том числе свежий PETALface с конференции WACV 2025. Также поделимся ссылками на исследования, которые подробнее освещают каждый подход.

Крупнейшие инвестиционные компании, успешные трейдеры, матерые волки с Уолл-Стрит и прочие серьезные участники рынков используют в торговле алгоритмы. В первом материале я приводил конкретные примеры, цифры, аргументы – если пропустили, почитайте, будет полезно. 

А если кратко, то суть в следующем: игроки, которые до сих пор торгуют на рынке исключительно «вручную» или при помощи готовых, общедоступных инструментов – неконкурентны. Хочется оставаться в игре? Придется подключать коды и роботов.

Собственно, моя серия материалов именно об этом. А цель – научить вас превращать свои торговые идеи в уникальные, рабочие алгоритмы. Даже если раньше вы не программировали.

Что, если навигатор перестанет упрямо твердить «Развернитесь!», когда  вы свернули с маршрута и предложит новый, более вам подходящий?

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

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

Времени мало, объема много, цели амбициозные - нужно научиться легко и быстро объяснять, но так же не лишая полноты!

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

Будет здорово получить ваши задачи и в следующих выпусках разобрать!

Мы продолжаем. Обязательно испытайте себя в предыдущей [1] части!

Недавно меня заинтересовала такая задача: как лучше всего определить, что в строке есть гласная?

Казалось бы, тривиальный вопрос, правда?

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

В этом посте я рассмотрю 11 способов обнаружения гласных, алгоритмический анализ, дизассемблирование байт-кода Python, реализацию CPython и даже исследую опкоды скомпилированного регулярного выражения. Поехали!

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

Что может заставить обратить внимание на красно-чёрные деревья, и как их реализовать? Статья ответит на оба эти вопроса. Бонусом будет показано, как на основе красно-чёрного сконструировать дерево интервалов.

В 2006 году АНБ скрыла в криптографическом стандарте Dual EC DRBG математический бэкдор. Агентство отрицало его наличие восемь лет. Затем утечки Сноудена подтвердили его существование.

Двойные эллиптические кривые (Dual Elliptic Curve) используются как безопасные генераторы случайных чисел (RNG). Математический бэкдор позволял правительству США расшифровывать SSL-трафик Интернета (Green 2013)¹.

Эта статья будет технически глубоким исследованием для программистов. Мы реализуем и исходную правительственную научную статью (SP 800-90 2006)², и бэкдор, обнаруженный исследователями Microsoft (Shumow & Ferguson 2007)³.

На моём домашнем компьютере для взлома 28 байт (не бит) при помощи этого бэкдора требуется 2 минуты. Представьте, какой объём Интернет-трафика правительство США могло расшифровывать при помощи суперкомпьютеров Министерства обороны.

Привет! Меня зовут Кирилл Хрыльченко. Я руковожу командой, которая занимается R&D для рекомендательных технологий в Яндексе. Одна из наших основных задач — развивать трансформерные технологии в контексте рекомендательных систем, и мы активно занимаемся этим уже примерно пять лет. Не так давно у нас произошёл новый виток в развитии рекомендательных технологий, которым мы хотим поделиться с вами в этой статье.

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

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

Привет, Хабр! Мы в команде «Вычислительная семантика» в AIRI сфокусированы на исследовании галлюцинаций и решении проблем доверительной генерации. Мы учимся находить галлюцинации и бороться с ними. Большие языковые модели (LLM) вроде GPT-4 стали незаменимыми помощниками в повседневной жизни — от генерации текстов до поддержки в кодинге и ответов на вопросы. Однако у них есть ахиллесова пята: они часто галлюцинируют.

В этом посте мы разберем нашу последнюю работу Will It Still Be True Tomorrow?, посвященную тому, как на надёжность моделей влияет феномен неизменного вопроса (evergreen question)  — то есть вопроса, ответ на который не зависит ни от времени, когда вы его задаёте, ни от места, вопроса про факт, который зафиксирован в истории и не меняется от обстоятельств.

В рамках этой работы мы совместно с MWS AI собрали датасет изменяемых и неизменных вопросов EverGreenQA (открытый доступ), обучили классификатор на базе многоязычного энкодера E5, и применили его для оценки собственных знаний модели. Наши результаты показывают, что большие языковые модели чаще всего правильно отвечают на неизменные вопросы, не прибегая к помощи RAG пайплайна.

Экстремальные погодные явления оказывают большое влияние на нашу жизнь. Это может проявляться в бытовых вещах, просто чтобы не попасть под сильный ливень или грозу. А ещё — в обеспечении бизнеса. Например, в прошлом году в Европе из‑за града погиб один из самых старых виноградников.

Именно поэтому мы решили улучшить наш прогноз экстремальных погодных явлений. Прежде всего мы сфокусировались на суперкраткосрочном прогнозе молний на карте осадков, также известной как наукаст, чтобы расширить нашу технологию прогнозирования погоды Meteum. Таким образом мы стали первыми в России, кто сделал карту наукаста гроз на ближайшие два часа с шагом 10 минут. Дело в том, что экстремальные погодные явления часто связаны с конвективными явлениями в атмосфере, которые сложно прогнозировать на долгий срок. То есть если в прогнозе есть гроза, то часто вместе с ней будет ожидаться сильный дождь и ветер, а в некоторых регионах и град.

Меня зовут Пётр Вытовтов. Я руководитель группы ML и качества прогноза в Яндекс Погоде. Сегодня я хочу рассказать вам о том, как мы добавляли прогноз молний в нашу модель наукаста с использованием данных со спутников, метеорологических радаров и применением трансформерных моделей.

Автор статьи Modern SAT solvers: fast, neat and underused утверждает, что SAT-солверы «преступно мало используются в нашей отрасли». [SAT — Boolean SATisfiability Solver, то есть солвер, способный находить присвоения, делающие истинными сложные булевы выражения. Более подробно я писал о них ранее.] Какое-то время назад я задался вопросом, почему: как получилось, что они настолько мощны, но ими никто не пользуется? Многие специалисты заявили, что причина в неудобстве кодирования SAT: они лучше предпочтут работать с инструментами, которые выполняют компиляцию в SAT.

Я вспомнил об этом, когда прочитал пост Райана Бергера о решении «задачи ферзей с LinkedIn» как задачи SAT.

Вкратце опишу задачу про ферзей (Queens). У нас есть сетка NxN, разделённая на N областей, и нам нужно разместить N ферзей так, чтобы в каждом столбце, строке и области находился ровно один. Ферзи могут находиться на одной диагонали, но не соседствовать по диагонали.

Распознавание дорожных знаков основывается на анализе изображений, полученных с камер, установленных на автомобиле. Эффективность работы такой системы зависит от корректной предварительной обработки изображений, в частности – от точного выделения области, содержащей дорожный знак. Основой этой процедуры выступает цветовая сегментация, поскольку большинство дорожных знаков обладают характерной цветовой окраской (например, красный, синий, жёлтый), позволяющей отличить их от фона.

На практике задача сегментации усложняется различиями в освещении, погодных условиях, наличием теней, бликов, а также загрязнением камеры. Это делает использование стандартного цветового пространства RGB неэффективным, поскольку оно неразрывно связано с яркостью. В связи с этим актуальной становится задача выбора более устойчивого цветового пространства – например, HSV, LAB или IHSL – для выделения дорожных знаков при помощи цветовой сегментации [1].

• Женатые и замужние — в топе: пока вы не уходите глубоко в анализ, этот быстрый фактор повышает ранг. Чем точнее ваша модель, тем меньше его вес.
• Английский — плохо: знание английского почему-то работало как антипаттерн, снижая релевантность.
• ОГУРЕЦ: кто-то зачем-то написал это слово в резюме. Оно попало в словарь модели и получило большой вес.
• Иксель — люди пишут Excel как угодно, и само слово в правильном написании оказалось снижающим оценку.
• К резюме может быть приложено много мусора. Самый эпичный пример: авиабилет Москва — Челябинск вместо резюме.