Обновить
198.78

Алгоритмы *

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

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

Как Яндекс применил генеративные нейросети для поиска ответов

Время на прочтение11 мин
Количество просмотров71K


Только что мы представили новую версию поиска Y1. Она включает в себя комплекс технологических изменений. В том числе улучшения в ранжировании за счёт более глубокого применения трансформеров. Подробнее об этом направлении мой коллега Саша Готманов уже рассказывал в нашем блоге. В новой версии модель стала мощнее: количество параметров возросло в 4 раза. Но сегодня мы поговорим о других изменениях.

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

Сегодня мы поделимся опытом создания и внедрения технологии YaLM (Yet another Language Model), которая теперь готовит ответы для Поиска и Алисы. В этом мне помогут её создатели — Алексей Петров petrovlesha и Николай Зинов nzinov. Эта история основана на их докладе с Data Fest 2021 и описывает опыт внедрения модели в реальные продукты, поэтому будет полезна и другим специалистам в области NLP. Передаю слово Алексею и Николаю.

Процессор, эмулирующий сам себя — может быть быстрее самого себя

Время на прочтение1 мин
Количество просмотров38K

Современный мир ПО содержит настолько много слоёв, что оптимизации могут быть в самых неожиданных местах. Знакомьтесь - год 2000, проект HP Dynamo. Это эмулятор процессора PA-8000, работающий на этом же процессоре PA-8000, но с технологией JIT. И реальные программы, запускающиеся в эмуляторе - в итоге работают быстрее, чем на голом процессоре.

td;dr - всё сказано в заголовке

Читать далее

Гексагональные тайловые миры

Уровень сложностиСложный
Время на прочтение32 мин
Количество просмотров40K

Тайловость в играх – очень распространенное явление, особенно в играх инди сегмента. Чаще всего используют квадратные тайлы – в них проще всего задать необходимые данные, будь то карта уровня или инвентарь. Однако на квадратных и прямоугольных формах возможности подобной системы не ограничиваются.

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

Читать далее

Прямоугольные тайловые миры

Уровень сложностиСредний
Время на прочтение17 мин
Количество просмотров29K

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

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

Читать далее

Тихая революция и новый дикий запад в ComputerVision

Время на прочтение7 мин
Количество просмотров36K

Казалось бы, революция с Computer Vision уже была. В 2012 году выстрелили алгоритмы основанные на сверточных нейронных сетях. Года с 2014 они дошли до продакшна, а года с 2016 заполонили все. Но, в конце 2020 года прошел новый виток. На этот раз не за 4 года, а за один. поговорим о Трансформерах в ComputerVision. В статье будет обзор новинок, которые появились в последний год.

Читать далее

Создание образа Мона Лизы в Игре «Жизнь»

Время на прочтение10 мин
Количество просмотров11K

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

Серебряная пуля для кремлевского демона

Время на прочтение5 мин
Количество просмотров81K

image


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

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

Математик-пенсионер, «хакнувший» лотерею

Время на прочтение11 мин
Количество просмотров124K

Любитель головоломок


Джеральд Селби всегда любил загадки: там, где другие видели лишь шум, он стремился найти порядок и гармонию. Работая на фабрике Kellogg's по производству овсяных хлопьев, он занимался анализом материалов для увеличения срока годности продукции. Однажды, изучая хлопья других компаний, Джерри наткнулся на странную последовательность символов на обороте коробки General Mills. Вместо даты и фабрики-производителя там был отпечатан загадочный код. Джерри решил расшифровать его: взяв несколько коробок завтраков Kellogg's и General Mills, он начал сравнивать их влажность, сообразив, что хлопья с примерно одинаковой влажностью должны иметь близкие даты производства. Делая записи на бумаге, он выявил некоторые закономерности. Вскоре ему удалось расшифровать всё, что позволило определить место, дату и время изготовления. В более агрессивной сфере бизнеса «взлом» секретов конкурентов мог бы обернуться огромной выгодой, но не в производстве овсяных хлопьев, поэтому руководство восприняло его открытие без энтузиазма.
Читать дальше →

Трюк с XOR для собеседований и не только

Время на прочтение8 мин
Количество просмотров142K


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

Хоть и непривычно ожидать решения с XOR на собеседованиях, довольно забавно разбираться, как они работают. Оказывается, все они основаны на одном фундаментальном трюке, который я постепенно раскрою в этом посте. Далее мы рассмотрим множество способов применения этого трюка с XOR, например, при решении популярной задачи с собеседований:

Дан массив из n — 1 целых чисел, находящихся в интервале от 1 до n. Все числа встречаются только один раз, за исключением одного числа, которого нет. Найдите отсутствующее число.

Разумеется, существует множество прямолинейных способов решения этой задачи, однако есть и довольно неожиданный, в котором применяется XOR.
Читать дальше →

Генератор неслучайных чисел

Время на прочтение4 мин
Количество просмотров21K
Этот код напечатает случайную последовательность латинских букв, так ведь?

import java.util.Random;

class WTF {
    public static void main(String[] args) {
        Random r = new Random(76880392499L<<11);
        String alphabet = " abcdefghijklmnopqrstuvwxyz";
        int n;
        while ((n = r.nextInt(alphabet.length())) > 0)
        	System.out.print(alphabet.charAt(n));
    }
}

Можете проверить; вывод кажется совсем не случайным. Как же так вышло?

Прежде всего: какой шанс, что из всех последовательностей латинских букв напечатается именно эта? Сгенерировано 10 случайных чисел, каждое выбиралось из 27 вариантов, значит всего вариантов было $27^{10} \approx 2.06\cdot10^{14}$. Если считать, что все варианты равновероятны, то нам выпал один шанс из двухсот миллионов миллионов! Ух!
Читать дальше →

Разработана опенсорсная утилита Depix для восстановления паролей с размытых скриншотов

Время на прочтение6 мин
Количество просмотров19K
Разработана опенсорсная утилита Depix для восстановления паролей с размытых скриншотов


Результат работы программы Depix (исходный код)

В голливудских фильмах любят преувеличивать. Они зуммируют фотографии в миллион раз — и выводят цифры из одного пикселя.

Хотя это невероятно, но научные исследования в этой области идут давно. Ещё в 90-е годы были опубликованы теоретические работы и PoC с восстановлением текста из размытых изображений. В 2012 году Владимир Южиков писал на Хабре о своей программе SmartDeblur для восстановления смазанных и расфокусированных снимков.

Несмотря на достаточно хорошее развитие науки в данном направлении, до сих пор не было специализированного инструмента конкретно для восстановления паролей (текста) после пикселизации. Программа Depix — первый такой инструмент.
Читать дальше →

Некоторые математические задачи нерешаемы, и это не так уж плохо

Время на прочтение7 мин
Количество просмотров16K

Постройте выпуклый восьмиугольник с четырьмя прямыми углами.

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

Потом у них возникают подозрения и они начинают задавать вопросы. «Вы сказали о прямых углах. Может, на самом деле вы имели в виду три угла?», «Вы точно имели в виду выпуклый многоугольник?», «Четыре прямых угла, по сути, образуют прямоугольник. Как мы можем получить ещё четыре стороны в восьмиугольнике?» Я внимательно слушаю, киваю, подтверждая их догадки.
Читать дальше →

Сверхдлинное преобразование Фурье на FPGA

Время на прочтение13 мин
Количество просмотров21K
Всем привет!

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

В этой статье показана невозможность реализации «классической» схемы очень длинного БПФ даже на самых современных кристаллах ПЛИС и предложен алгоритм, позволяющий это сделать. Также пошагово рассмотрена основная идея алгоритма: от математической составляющей до создания законченного решения на базе ПЛИС с использованием внешней DDR-памяти. Статья затронет тонкости проектирования многоканальных систем обработки для подобного класса задач и, в частности, опишет мой практический опыт.


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

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

Точные и быстрые вычисления для чисел с плавающей точкой на примере функции синуса. Введение и часть 1

Время на прочтение6 мин
Количество просмотров29K
Внимательно прочитал очень хорошие статьи от ArtemKaravaev по сложению чисел с плавающей точкой. Тема очень интересная и хочется её продолжить и показать на примерах, как работать с числами с плавающей точкой на практике. В качестве эталона возьмём библиотеку GNU glibc (libm). А чтобы статья не была уж скучной, добавим соревновательную составляющую: попробуем не только повторить, но и улучшить код библиотеки, сделав его более быстрым/точным.

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

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

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

О талантах, деньгах и алгоритмах сжатия данных

Время на прочтение16 мин
Количество просмотров47K


Алгоритмы сжатия — это очень коварная тема, привлекающая многих новичков. Это правда! Часто человеку кажется, что его осенила божественная идея, как сильно сжать данные. Любые, кстати! Без потерь! Рекурсивно! А поскольку данные — это хранение информации и передача, то если хотя бы на единицы процентов результат улучшить — это миллиарды долларов (смотрим экономию всех провайдеров на передаче и хранении, всех дата-центров компаний, всех домашних пользователей, перемножаем… аж дух захватывает)! И люди пишут письма:
«Обращаюсь к вам, как «создателю и демиургу проекта ;) compression». Мной придуман алгоритм, основанный на простом рассуждении – если файл условно несжимаемый, есть вероятность что, часть файла имеет избыточность и файл можно сжать частично. …» 
«Обращаюсь к Вам, как к одному из главных специалистов в области сжатия информации. Предлагаю Вам ознакомиться с изобретением в области сжатия информации. [...] По мнению автора, основным достоинством данного «Способа кодирования информации» является способность одинаково хорошо сжимать без потери качества информацию любого типа (видео, аудио, текст, архив и т.д.). Помимо этого «Способ» позволяет проводить процесс кодирования (сжатия) повторно....» 

Бывает даже так:
«Мне, для начала, нужно 30–60 минут общения с Вами по Скайпу.
Вопрос: каково Ваше вознаграждение и куда его отправить?» 

И если вы думаете, что обращения типа последнего — мои любимые, то реакция ровно обратная («Боже, дай мне терпения!»). Ибо по опыту в последнем случае люди наиболее настойчивые… Кстати, это могут быть не только авторы, но и инвесторы, о которых ниже тоже будет. 

Кому интересно, в чем же таки коварство алгоритмов, есть ли у нас таланты, и где же, наконец, деньги — добро пожаловать под кат! (Талантливые авторы алгоритмов могут сразу переходить в раздел «Про деньги»).
Читать дальше →

Можно ли сложить N чисел типа double наиболее точно?

Время на прочтение13 мин
Количество просмотров29K

В предыдущих сериях…


Прошлая статья рассказала о двух способах сложения двух двоичных чисел с плавающей запятой без потери точности. Чтобы добиться этого, мы представили сумму c=a+b в виде двух чисел (s,t)=a+b, причём таких, что s — наиболее близкое к a+b точно-представимое число, а t=(a+b)-s — это отсекаемая в результате округления часть, составляющая точную погрешность. У читателей был вопрос: а можно ли достаточно точно сложить массив чисел типа double? Оказывается, можно! Но только, вероятно, не всегда и не абсолютно… и не алгоритмом Кэхэна, который тогда вспоминали в комментариях. За подробностями прошу под кат, где мы и найдём приложение тому, о чём я рассказал в прошлый раз.


Браузер и числа с плавающей запятой

Время на прочтение12 мин
Количество просмотров16K

Изображение — www.freepik.com

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

Часть 1: нереальные ожидания


Баг назывался «JSON некорректно парсит 64-битные Integer»; поначалу это непохоже на проблему с плавающей запятой или браузером, но его отправили на crbug.com, поэтому меня попросили взглянуть. Проще всего воссоздать его, открыв инструменты разработчика Chrome (F12 или Ctrl+Shift+I) и вставив в консоль разработчика следующий код:

json = JSON.parse(‘{“x”: 2940078943461317278}’); alert(json[‘x’]);

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

Сложение двух чисел с плавающей запятой без потери точности

Время на прочтение9 мин
Количество просмотров83K
Здравствуйте, друзья, как вы думаете, если мы напишем такой код:

s = a+b;
z = s-a;
t = b-z;

то не кажется ли вам, что в результате его выполнения получится, что t=0? С точки зрения привычной математики действительных чисел это и правда так, а вот с точки зрения двоичной арифметики с плавающей запятой в переменной t будет кое-что другое. Там будет то, что спасает нас от потери точности при сложении чисел $a$ и $b$. Кого интересует данная тема, прошу под кат.

Фильтр Калмана — это легко

Время на прочтение18 мин
Количество просмотров104K


Много людей, в первый раз сталкивающихся в работе с датчиками, склонны считать, что получаемые показания — это точные значения. Некоторые вспоминают, что в показаниях всегда есть погрешности и ошибки. Чтобы ошибки в измерениях не приводили к ошибкам в функционировании системы в целом, данные датчиков необходимо обрабатывать. На ум сразу приходит словосочетание “фильтр Калмана”. Но слава этого “страшного” алгоритма, малопонятные формулы и разнообразие используемых обозначений отпугивают разработчиков. Постараемся разобраться с ним на практическом примере.
Читать дальше →

Как генерируются UUID

Время на прочтение7 мин
Количество просмотров145K

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

Современную реализацию UUID можно проследить до RFC 4122, в котором описано пять разных подходов к генерированию этих идентификаторов. Мы рассмотрим каждый из них и пройдёмся по реализации версии 1 и версии 4.
Читать дальше →

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