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


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

Про мотивацию и эффективность (или неэффективность) работы написано уже огромное количество статей. Попробуем взглянуть на это по-новому. Более научно и в то же время практично.


Начнём с очевидных фактов. Итак:

• Мозг у нас один.
• Мозг работает по-разному, в зависимости от того, чем вы занимаетесь.
• Есть «приятные» процессы (например, привычные действия, общение с доброжелательно настроенными людьми или что-то, связанное с умеренной физической активностью).
• Есть «неприятная» активность мозга, вызывающая почти болезненные ощущения (например, начальный период изучения совершенно нового для вас иностранного языка или языка программирования).
• Мы стремимся минимизировать неприятные ощущения.
• Мечты и «хотелки» в основном являются стремлением к определённым формам работы мозга и состояниям сознания, а вовсе не ситуативными достижениями (хотя мы обычно думаем иначе).

Многие программисты утверждают, что знают С. Ну что ж, у него самый известный синтаксис, он существует уже 44 года и он не захламлен непонятными функциями. Он прост!

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

Если вы думаете что он прост — пройдите этот тест. В нем всего 5 вопросов. Каждый вопрос в принципе одинаковый: какое будет значение возврата?

Статистика приходит к нам на помощь при решении многих задач, например: когда нет возможности построить детерминированную модель, когда слишком много факторов или когда нам необходимо оценить правдоподобие построенной модели с учётом имеющихся данных. Отношение к статистике неоднозначное. Есть мнение, что существует три вида лжи: ложь, наглая ложь и статистика. С другой стороны, многие «пользователи» статистики слишком ей верят, не понимая до конца, как она работает: применяя, например, тест Стьюдента к любым данным без проверки их нормальности. Такая небрежность способна порождать серьёзные ошибки и превращать «поклонников» теста Стьюдента в ненавистников статистики. Попробуем поставить точки над i и разобраться, какие модели случайных величин должны использоваться для описания тех или иных явлений и какая между ними существует генетическая связь.

При съемке книжного разворота с помощью камеры мобильного устройства неизбежно возникают некоторые из нижеперечисленных дефектов (а возможно, что и все сразу):

• цифровой шум,
• тени и блики,
• расфокусировка и смаз,
• перекос,
• перспективные искажения,
• кривые строки,
• лишние объекты в кадре.

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

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

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

Многие студенты, впервые сталкиваясь с описанием какой-нибудь хитроумной штуки, вроде алгоритма Кнута – Морриса – Пратта или красно-чёрных деревьев, тут же задаются вопросами: «К чему такие сложности? И это, кроме авторов учебников, кому-нибудь нужно?». Лучший способ доказать пользу алгоритмов – это примеры из жизни. Причём, в идеале – конкретные примеры применения широко известных алгоритмов в современных, повсеместно используемых, программных продуктах.



Посмотрим, что можно обнаружить в коде ядра Linux, браузера Chromium и ещё в некоторых проектах.

Я уверен, что многим программистам знакома формула:


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

Вычисляет она относительную яркость цвета (relative luminance или в некоторых контекстах luma; не путать с lightness и brightness) и широко применяется для преобразования цветного RGB-изображения в Grayscale и связанных с этим задач.

Формула растиражирована и процитирована в тысячах статей, форумных обсуждений и ответов на StackOverflow… Но дело в том, что единственно-правильное её место — на свалке истории. Использовать её нельзя. Однако же используют.

Но почему нельзя? И откуда же взялись именно такие коэффициенты?

Недавно на isocpp.org была опубликована ссылка на статью Eli Bendersky «Perfect forwarding and universal references in C++». В этой небольшой статье есть простой ответ на простой вопрос — для решения каких задач и как нужно использовать rvalue-ссылки.

Как известно, в современных архитектурах x86(_64) и ARM виртуальная память процесса линейна и непрерывна, ибо, к счастью, прошли времена char near* и int huge*. Виртуальная память поделена на страницы, типичный размер которых 4 KiB, и по умолчанию они не отображены на физическую память (mapping), так что работать с ними не получится. Чтобы посмотреть текущие отображённые интервалы адресов у процесса, в Linux смотрим /proc/<pid>/maps, в OS X vmmap <pid>. У каждого интервала адресов есть три вида защиты: от исполнения, от записи и от чтения. Как видно, самый первый интервал, начинающийся с load address (соответствующий сегменту .text у ELF в Linux, __TEXT у Mach-O в OS X), доступен на чтение и исполнение — очень логично. Ещё можно увидеть, что стек по сути ничем не отличается от других интервалов, и можно быстро вычислить его размер, вычтя из конечного адреса начальный. Отображение страниц выполняется с помощью mmap/munmap, а защита меняется с помощью mprotect. Ещё существуют brk/sbrk, deprecated древние пережитки прошлого, которые изменяют размер одного-единственного интервала «данных» и в современных системах эмулируются mmap’ом.

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

• оптимально управляет уже выделенной памятью;
• значительно уменьшает количество обращений к ядру (ведь mmap / sbrk — это syscall);
• вообще абстрагирует программиста от виртуальной памяти, так что многие пользуются malloc’ом, вообще не подозревая о существовании страниц, таблиц трансляции и т. п.

Довольно теории! Будем щупать malloc на практике. Проведём три эксперимента. Работа будет возможна на POSIX-совместимых операционках, в частности была проверена работа на Linux и на OS X.

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

В этом посте мы попробуем применить технику символьного выполнения на примере символьной ВМ KLEE для решения простого ASCII-лабиринта. Как вы думаете, сколько верных решений мы сможем найти?

Развлекаемся, «распутывая» код на языке Си

Вызов: Прежде чем лезть под кат, скомпилируйте в голове заголовок статьи, что он дает на выходе?


Когда я в очередной раз просматривал книгу «Expert C programming», я вдруг наткнулся на раздел «light relief» в международном конкурсе на самый запутанный код на Си (IOCCC). Это соревнование по написанию как можно более нечитабельного кода. То, что такие конкурсы устраиваются для Си, наверное, говорит что-что об этом языке. Мне хотелось увидеть работы участников этого соревнования. Не найдя никакой информации в интернете, я решил поискать их самостоятельно.

IOCCC был придуман Стивеном Борном, когда он решил использовать препроцессор Си и написать Unix shell как бы на языке Си, но больше похожем на язык Algol-68, с его явными окончаниями операторов, например:

if
  ...
fi 

Он добился этого, сделав:

#define IF if(
#define THEN ){
#define ELSE } else {
#define FI ;}

Что позволило ему писать так:

IF *s2++ == 0
THEN return(0);
FI

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

Предыстория и проблематика

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

Получилось похоже на MS Visio с определенной степенью кастомизации и плагинизации. Никаких технических сложностей здесь нету, однако есть ряд особенностей.

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

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

В-третьих, когда я сделал все, что хотел, и показал результаты другу (который даже не программист), то он потыкал и сказал, что неплохо бы сделать Ctrl+Z. Я загорелся идеей, но вот реализовать это оказалось не такой тривиальной задачей. В этой статье я опишу, к чему пришел в итоге.

В сети огромное количество площадок формата Q&A где задаются вопросы из разряда:

• Предложите С++ логер? (C++ logging framework suggestions)
• Какой наиболее эффективный потоко-безопасный С++ логер? (What is the most efficient thread-safe C++ logger)
• Библиотека логирования для игр (Logging library for c games)
• Асинхронный потоко-безопасный С++ логер? (Asynchronous thread-safe logging in C++)

Люди делятся своим опытом и знаниями, но формат таких площадок позволяет лишь показать личные предпочтения отвечающего. К примеру, одним из самых производительных логеров чаще всего называют Pantheios, который даже по тестам производителя тратит больше 100 секунд на запись 1M строк лога, на современном железе это около 30 секунд, быстро ли это?

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

В процессе подготовки задачи для вступительного испытания на летнюю школу GoTo, мы обнаружили, что на русском языке практически отсутствует качественное описание основных метрик ранжирования (задача касалась частного случая задачи ранжирования — построения рекомендательного алгоритма). Мы в E-Contenta активно используем различные метрики ранжирования, поэтому решили исправить это недоразуменее, написав эту статью.

Все фотографии в этой статье взяты из трилогии Кристофера Нолана «Тёмный рыцарь». Это всё же Бэтмен!

Давайте сыграем!

При подготовке вы хорошо поработали с телефоном. Интервью в офисе этим утром проходили занятно. После общего обеда сотрудник отдела кадров сел за стол напротив вас. Он спросил: «Какую зарплату вы бы хотели?».

Что вам делать? Что же вам делать?!

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

Или, возможно, он попробует другой подход, чтобы подтолкнуть вас назвать цифру: «Какая зарплата у вас сейчас?».

Этот вопрос звучит вполне резонно. Разве не надо отвечать на этот вопрос?

Написать этот пост меня вдохновила замечательная статья в блоге Gaffer on Games «Reading and Writing Packets» и неуёмная тяга автоматизировать всё и вся (особенно написание кода на C++!).

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

• Выбор формата. Если бы мы писали простенькую игру на JavaScript, нас бы устроил JSON или любой его самописный родственник. Но мы пишем серьёзную многопользовательскую игру, требовательную к трафику; мы не можем позволить себе отправлять ~16 байт на float вместо четырёх. Значит, нам нужен «сырой» двоичный формат. Однако, двоичные данные усложняют отладку; было бы здорово, если бы мы могли менять формат в любой момент, не переписывая целиком все наши функции чтения/записи.
• Проблемы безопасности. Первое правило сетевой игры: не доверяй данным, присланным клиентом! Функция чтения должна уметь оборваться в любой момент и вернуть false, если что-то пошло не так. При этом использовать исключения считается неважной идеей, поскольку они слишком медленные. Мамкин хакер пусть и не сломает ваш сервер, но вполне может ощутимо замедлить его беспрерывными эксепшнами. Но вручную писать код, состоящий из if'ов и return'ов, неприятно и неэстетично.
• Повторяющийся код. Функции чтения и записи похожи, да не совсем. Необходимость изменить структуру пакета приводит к необходимости поменять две функции, что рано или поздно приведёт к тому, что вы забудете поменять одну из них или поменяете их по-разному, что приведёт к трудно отлавливаемым багам. Как справедливо замечает Gaffer on Games, it is really bloody annoying to maintain separate read and write functions.

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

1. Части I, II (синглплеер с авторитарным сервером)
2. Часть III (Появление врага)
3. Часть IV (Хэдшот!)

Как повесить идеальный хэдшот если у тебя пинг 2 секунды? Вы узнаете в этой статье.

Текущий алгоритм работы мультиплеера

• Сервер получает команды с клиентов и времена их отправления
  
• Сервер обновляет состояние мира
  
• Сервер с некоторой частотой отправляет свое состояние всем клиентам
  
• Клиент отправляет команды и локально воспроизводит их результат
  
• Клиент получает обновленные состояния мира и:
  • Применяет состояние от сервера
  • Заново применяет все свои команды, которые сервер не успел применить.
  • Интерполирует предыдущие состояния других игроков
• С точки зрения игрока, есть два серьезных последствия:
  • Игрок видит себя в настоящем
  • Игрок видит других в прошлом.

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

Поиск работы – задача не из простых, особенно в текущих неблагоприятных экономических условиях. Европейский ресурс Tech.eu в честь запуска своего сервиса по поиску работы подготовил список из десяти сайтов, которые помогут вам подыскать себе место под европейским солнцем, если вы, по какой-либо причине, желаете уехать на заработки в ЕС.