Алгоритмы *

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

Вот первичный анонс о внедрении нового сборщика, датированный августом 2015-го:

В Go создаётся сборщик мусора (GC) не только для 2015 года, но и для 2025-го, и ещё дальше… Сборщик в Go 1.5 возвещает о наступлении будущего, в котором паузы на сборку больше не являются барьером для перехода на безопасный язык. Это будущее, в котором приложения без труда масштабируются вместе с оборудованием, и по мере роста мощности оборудования сборщик мусора больше не является сдерживающим фактором при создании более качественного, масштабируемого ПО. Go — хороший язык для использования как минимум в ближайший десяток лет.

Создатели утверждают, что они не просто решили проблему пауз на сборку мусора, а пошли куда дальше:

Одним из высокоуровневых способов решения проблем с производительностью является добавление GC-настроек (knobs), по одной на каждую проблему. Программист может менять их, подбирая наилучшую комбинацию для своего приложения. Недостатком этого подхода является то, что при внедрении каждый год одной-двух новых настроек через десять лет придётся законодательно регулировать труд людей, которые будут менять эти настройки. Go не пошёл по этому пути. Вместо кучи настроек мы оставили одну и назвали её GOGC.

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

Не сомневаюсь, что многие пользователи Go были просто счастливы получить новый подход к runtime’у в Go. Но у меня есть претензии к этим заявлениям: они выглядят как недостоверный маркетинговый булшит. А поскольку они раз за разом воспроизводятся в Сети, пришло время подробно с ними разобраться.

Привет, Хабр! Меня зовут Дичковский Алексей, и я хочу вам рассказать о том, как я потратил полтора месяца своей жизни на написание бота для упрощённой версии DotA.

Ежегодно компания Mail.ru проводит онлайн-чемпионат по программированию игровых стратегий (Russian AI Cup 2016). Я принимал участие в данном соревновании в 2012 году (СodeTanks) и, совсем немного, в 2013 (СodeTroopers). В этом году, изрядно наевшись веб разработкой, я решил попробовать принять участие ещё раз. Я изначально не надеялся (но, конечно же, очень хотел) занять какое-либо призовое место и в целом для меня это был скорее тест, насколько я ещё могу реализовать нечто интересное. О том, что из этого получилось, можно прочитать под катом.

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

Самый простой способ разобраться во всех деталях — изучить открытые исходники. Я взялся изучать Verilog исходники FPGA-майнера. Это не единственный такой проект, есть еще несколько примеров на github, и все они, хоть и разных авторов, похоже работают приблизительно по одной схеме. Вполне возможно, что автор то у них всех изначально был один, просто разные разработчики адаптируют один и тот же код под разные чипы и разные платы… По крайней мере мне так показалось…

Вот и я, поизучав исходники Verilog, адаптировал проект с github к плате Марсоход3 на основе ПЛИС Altera MAX10, 50 тыс. логических элементов. Я смог запустить свой майнер и даже смог запустить процесс вычисления биткоинов, но бросил это дело через пол часа из-за бесперспективности. Слишком медленно по нынешним временам работает мой FPGA майнер. Ну и пусть.

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

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

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



Правила против статистики

Машинный перевод, то есть автоматический перевод с одного человеческого языка на другой, зародился в середине прошлого века. Точкой отсчета принято считать Джорджтаунский эксперимент, проведенный 7 января 1954 года, в рамках которого более 60 фраз на русском языке были переведены компьютером на английский. По сути, это был вовсе и не эксперимент, а хорошо спланированная демонстрация: словарь включал не более 250 записей и работал с учетом лишь 6 правил. Тем не менее результаты впечатлили публику и подстегнули развитие машинного перевода.

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



Под катом я расскажу о том, что такое наукастинг и как мы над ним работали.

В начале ноября в американском городе Иссакуа завершилась встреча международной рабочей группы WG21 по стандартизации C++ в которой участвовали сотрудники Яндекса. На встрече «полировали» C++17, обсуждали Ranges, Coroutines, Reflections, контракты и многое другое.

Заседания, как обычно, занимали целый день + решено было сократить обеденный перерыв на полчаса, чтобы успеть побольше поработать над C++17.

Несмотря на то, что основное время было посвящено разбору недочётов черновика C++17, несколько интересных и свежих идей успели обсудить, и даже привнести в стандарт то, о чём нас просили на cpp-proposals@yandex-team.ru.

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

Курс ведет Сергей Бабичев, доцент кафедр информатики и вычислительной математики, а также теоретической и прикладной информатики в МФТИ. Под катом вас ждет восемь лекций:

• Лекция 1. «Введение. Исполнители. Абстракции интерфейсов. Рекурсия»
• Лекция 2. «Жадные алгоритмы»
• Лекция 3. «Сортировки»
• Лекция 4. «Поиск. Списки»
• Лекция 5. «Деревья»
• Лекция 6. «Хеш-таблицы»
• Лекция 7. «Динамическое программирование»
• Лекция 8. «Алгоритмы на графах»

Содержание

1. Введение в Computer Science
2. Структуры данных и Алгоритмы
3. Системное программирование
4. Распределенные системы
5. Базы данных
6. Объектно-ориентированный дизайн и разработка софта
7. Искусственный интеллект
8. Машинное обучение
9. Веб-разработка и интернет-технологии
10. Concurrency
11. Компьютерные сети
12. Разработка мобильных приложений
13. Математика для программистов
14. Теория информатики и языки программирования
15. Архитектура компьютера
16. Безопасность
17. Компьютерная графика
18. Работа с изображениями и компьютерное зрение
19. Интерфейс Человек-Компьютер
20. Вычислительная биология
21. Прочее

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


Под катом — расшифровка лекции и часть слайдов Сергея.

Седьмого ноября стартует Russian AI Cup 2016. Это ежегодный чемпионат по программированию искуственного интеллекта, организуемый Mail.Ru Group. Russian AI Cup проводится в форме игры, чтобы получилось наглядно, понятно и просто. Вкратце: участники создают алгоритм, который описывает игровую стратегию. Получившийся бот сражается с другими такими же, а лучший из них побеждает в раунде. Таким образом, из серии раундов организуется турнир, проходящий в несколько этапов.

С одной стороны, основная механика игры довольно проста и минимально рабочую стратегию реально написать за пару часов (для быстрого старта в чемпионате можно заглянуть сюда, там же можно найти небольшой tutorial). С другой же — в игре получилось много нюансов, и оттачивать стратегию, поднимаясь вверх по турнирной таблице, можно до бесконечности. В этом году предлагаем вам на месяц стать магом и сразиться на средневековом поле боя в MOBA-игре CodeWizards. Впрочем, обо всем по порядку.

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

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


Под катом — расшифровка и большинство слайдов.

Глобальное освещение, динамический свет и декали (да, есть такое слово :) ) в действии.

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

Голуби дают людям фору в решении дилеммы Монти Холла, что могло бы позволить им успешно выступать на одноименном ток-шоу. Это закономерность может, в свою очередь, излить свет на то, почему людям так трудно она дается.

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

Когнитивный психолог Massimo Piattelli-Palmarini заметил по этому поводу: Ни одна статистическая задача даже рядом не стоит по способности дурачить всех людей и во все времена.

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

Недавно в Москве прошла конференция Data Fest, организованная сообществом Open Data Science и Яндексом. Этой публикацией мы открываем серию расшировок докладов с Data Fest. Автор первого доклада — доктор наук, признанный специалист по машинному обучению и преподаватель Школы анализа данных Константин Вячеславович Воронцов.


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

«Андрей (Ершов), представь, как было бы здорово организовать что-то вроде паломничества, где программисты со всего мира могли бы приехать в Хорезм и отпраздновать рождение этого понятия.»
— Дональд Кнут уговаривает Ершова организовать международный симпозиум

Кнут и Ершов

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

— Я думаю, я собираюсь стать программистом.
— О, так ты занимаешься численным анализом?
— Не совсем.
— Аааа, искусственный интеллект.
— Нет, и не искусственный интеллект.
— Тогда должно быть ты занимаешься языками программирования?

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

Итак, считаем, что мы уже нашли на фотографии линию корешка, воспользуемся этим знанием, чтобы определить ваниш-точки для страниц разворота (vanishing point). Ваниш-точки – это точки схождения параллельных прямых в перспективной проекции книги на плоскость изображения. Они обе должны располагаться на продолжении этой линии, но для каждой из страниц положение точки может быть свое. Схематически это показано на следующей иллюстрации (на самом деле, это лог для отладки). Линия корешка выделена красным, линии, пересекающиеся в ваниш-точках, – зеленым.

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

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


Ну а под катом — лекция Петра Попова и часть слайдов.

Это будет длиннопост. Я давно хотел написать этот обзор, но sim0nsays меня опередил, и я решил выждать момент, например как появятся результаты ImageNet’а. Вот момент настал, но имаджнет не преподнес никаких сюрпризов, кроме того, что на первом месте по классификации находятся китайские эфэсбэшники. Их модель в лучших традициях кэгла является ансамблем нескольких моделей (Inception, ResNet, Inception ResNet) и обгоняет победителей прошлого всего на полпроцента (кстати, публикации еще нет, и есть мизерный шанс, что там реально что-то новое). Кстати, как видите из результатов имаджнета, что-то пошло не так с добавлением слоев, о чем свидетельствует рост в ширину архитектуры итоговой модели. Может, из нейросетей уже выжали все что можно? Или NVidia слишком задрала цены на GPU и тем самым тормозит развитие ИИ? Зима близко? В общем, на эти вопросы я тут не отвечу. Зато под катом вас ждет много картинок, слоев и танцев с бубном. Подразумевается, что вы уже знакомы с алгоритмом обратного распространения ошибки и понимаете, как работают основные строительные блоки сверточных нейронных сетей: свертки и пулинг.

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



Очень скоро мы поняли, что тут мог бы здорово помочь общий высокоуровневый язык запросов, который бы предоставлял единообразный доступ к уже имеющимся системам, а также избавлял от необходимости заново реализовывать типовые абстракции на низкоуровневых примитивах, принятых в этих системах. Так началась разработка Yandex Query Language (YQL) — универсального декларативного языка запросов к системам хранения и обработки данных. (Сразу скажу, что мы знаем, что это уже не первая штука в мире, которая называется YQL, но мы решили, что это делу не мешает, и оставили название.)

В преддверии нашей встречи, которая будет посвящена инфраструктуре Яндекса, мы решили рассказать о YQL читателям Хабрахабра.

На Хабре уже как минимум дважды упоминался новый отечественный стандарт блочного шифрования ГОСТ Р 34.12 2015 «Кузнечик», ru_crypt в своем посте рассмотрел основные механизмы и преобразования нового стандарта, а sebastian_mg занимался пошаговой трассировкой базового преобразования. Но многие вопросы остались без ответа. Насколько быстр новый ГОСТ? Можно ли его оптимизировать, эффективно реализовать, ускорить аппаратно?