Примечание переводчика: оригинальная статья опубликована в серии твитов

Вероятно, вы уже читали кучу объяснений, почему обработка связных списков — плохой вопрос для собеседования. Я же в первую очередь хочу объяснить, откуда он вообще взялся. Всем пристегнуться, погружаемся в теорию игр ИСТОРИЮ!

Хотя индустрия программного обеспечения процветала в 80-е годы, но действительно взлетела в 90-е. В это десятилетие число работников отрасли в США утроилось и превысило миллион человек. Со взрывным ростом пришла необходимость нанимать массу сотрудников и оценивать их.

Что нужно оценить? Ну, в первую очередь, знание языков. Согласно TIOBE, в 1986−2006 годы самым популярным языком в мире был C, далее следовал C++. К 2006 году Java вышла на первое место, но C остался рядом.

C работал близко к железу без лишних абстракций. Пустой словарь Python расходует аж 288 байт, то есть 5% всего объёма памяти первого поколения Apple II. Абстракции слишком дороги, слишком много накладных расходов. Если вам нужна сложная структура данных, вы должны построить её самостоятельно с помощью массивов, структур и указателей.

Изображения формата JPEG встречаются повсюду в нашей цифровой жизни, но за этим покровом осведомлённости скрываются алгоритмы, устраняющие детали, не воспринимаемые человеческим глазом. В итоге получается высочайшее визуальное качество при наименьшем размере файла – но как конкретно всё это работает? Давайте посмотрим, чего именно не видят наши глаза!

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

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

На Boosters.pro в течении двух месяцев с 18 февраля по 18 апреля проходило соревнование по построению рекомендательной системы на реальных данных одного из крупнейших российских онлайн-кинотеатров Okko. Организаторы преследовали цель улучшить существующую рекомендательную систему. На данный момент соревнование доступно в режиме песочницы, в которой вы можете проверить свои подходы и отточить навыки в построении рекомендательных систем.

Всем привет, я работаю программистом-исследователем в команде компьютерного зрения Mail.ru Group. Ко Дню Победы в этом году мы решили сделать проект по реставрации военных фотографий. Что такое реставрация фотографий? Она состоит из трех этапов:

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

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

Пролог

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

Умным данный парсер делает возможность извлечения чисел из текста с ошибками, допущенными в результате некорректного ввода или в результате оптического распознавания текста из изображения (OCR).

Для ленивых:
Ссылка на проект github: ссылка.

Дональд Кнут — учёный в области информатики, который настолько заботится о правильности своих книг, что предлагает один шестнадцатеричный доллар ($2,56, 0x$1,00) за любую найденную «ошибку», где ошибкой считается всё, что «технически, исторически, типографически или политически неправильно». Я очень хотел получить чек от Кнута, поэтому решил поискать ошибки в его выдающемся труде «Искусство программирования» (TAOCP). Удалось найти три. Верный слову, Кнут прислал чек на 0x$3,00.



Как видите, это не настоящий чек. Раньше Кнут отправлял реальные чеки, но прекратил в 2008 году из-за безудержного мошенничества. Теперь он рассылает «личные депозитные сертификаты» в банке Сан-Серрифф (BoSS). Он говорит, что готов выслать реальные деньги в случае необходимости, но, похоже, это слишком хлопотно.

Пришлось мне недавно решать задачку по оптимизации поиска дубликатов изображений.

Существующее решение работает на довольно известной библиотеке, написанной на Python, — Image Match, основанной на работе «AN IMAGE SIGNATURE FOR ANY KIND OF IMAGE» за авторством H. Chi Wong, Marshall Bern и David Goldberg.

По ряду причин было принято решение переписать всё на Kotlin, заодно отказавшись от хранения и поиска в ElasticSearch, который требует заметно больше ресурсов, как железных, так и человеческих на поддержку и администрирование, в пользу поиска в локальном in-memory кэше.

Для понимания того, как оно работает, пришлось с головой погружаться в «эталонный» код на Python, так как оригинальная работа порой не совсем очевидна, а в паре мест заставляет вспомнить мем «как нарисовать сову». Собственно, результатами этого изучения я и хочу поделиться, заодно рассказав про некоторые оптимизации, как по объёму данных, так и по скорости поиска. Может, кому пригодится.

В мире наступили восьмидесятые. IBM захватывал рынок профессиональных компьютеров своими PC и PC XT — родоначальниками всех современных настольных компьютеров. Джобс одну за другой выпускал новые модели Apple. Commodore 64 и ZX Spectrum гремели по миру. А в это время в советском блоке продолжали выпускаться Ascota 170 — механические компьютеры родом из начала пятидесятых. Почему-то, в рунете (да и в остальном интернете тоже) мало говорят об этих удивительных машинах, едва ли не единственных серийно (больше трёхсот тысяч с 1955 до 1983 годов) выпускавшихся Тьюринг-полных механических компьютерах. Я и сам о них узнал только тогда, когда Аскота случайно попала мне в руки.
Надеюсь, моя статья сможет изменить это.


Моя Аскота закончила считать квадратный корень из 2.

Привет.

Вы знали, что платформы для размещения объявлений часто копируют контент у конкурентов, чтобы увеличить количество объявлений у себя? Они делают это так: обзванивают продавцов и предлагают им разместиться на своей платформе. А иногда и вовсе копируют объявления без разрешения пользователей. Авито — популярная площадка, и мы часто сталкиваемся с такой недобросовестной конкуренцией. О том, как мы боремся с этим явлением, читайте под катом.

«Мы начинаем разработку новой игры, и нам нужна классная вода. Такую сможешь?»


, — cпросили меня. «Да не вопрос! Конечно, смогу», — ответил я, но голос предательски задрожал. «А, еще и на Unity?», — и мне стало понятно, что впереди очень много работы.

Вычисление ряда Фибоначчи — это классическая алгоритмическая задача, потому её нередко дают на собеседованиях, когда хотят проверить, что кандидат в принципе хоть как-то умеет в алгоритмы. Предположим, вы тот самый кандидат. Вам дали задание: на языке JavaScript написать функцию fib(n), возвращающую энное число Фибоначчи. Считаем, что нулевое число Фибоначчи — это нуль. Проверка корректности аргумента не требуется. Какие у вас есть варианты?

Введение

---

«Что получится, если мы заменим числа с плавающей запятой на рациональные числа и попытаемся отрендерить изображение?»

Такой вопрос я задал себе после размышлений над твитом исследователя и преподавателя компьютерной графики Моргана Макгвайра. Он рассуждал о том, насколько сильно студенты компьютерных наук удивляются, когда впервые узнают, что для хранения привычных нам чисел с плавающей запятой в современных компьютерах нужно идти на компромиссы. И эти компромиссы делают сложными простые задачи, например, проверку принадлежности точки треугольнику. Проблема, разумеется, заключается в том, что проверка нахождения четырёх точек в одной плоскости (копланарности) с помощью определителя или какого-нибудь векторного умножения (а на самом деле это одно и то же) никогда не даст значение, точно равное нулю, чего требуют эти математические методы. Даже если бы настоящие вычисления нахождения на одной плоскости были бы точны, те же компромиссы с точностью почти с вероятностью в 1,0 дали бы ответ, что сами четыре точки не копланарны.

Это зародило во мне мысль — если допустить, что все входящие данные рендерера (координаты вершин, 3D-преобразования и т.д.) были бы заданы как рациональные числа, то создавали бы все операции, от создания луча, обхода ускоряющей структуры и до пересечения лучей с треугольниками только рациональные числа? Если это было бы так, то мы бы смогли выполнять проверку копланарности совершенно точно! Возможно, вы зададитесь вопросом, почему 3D-сцена, выраженная в рациональных числах должна давать результаты тоже только в рациональных числах…


Простая сцена, трассировка пути в которой выполнена рациональной арифметикой. Здесь используется система чисел «с плавающей чертой дроби», а не числа с плавающей запятой.

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

Это продолжение первой статьи о LPCNet. В первом демо мы представили архитектуру, которая сочетает обработку сигналов и глубокое обучение для повышения эффективности нейронного синтеза речи. На этот раз превратим LPCNet в нейронный речевой кодек с очень низким битрейтом (см. научную статью). Его можно использовать на текущем оборудовании и даже на телефонах.

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

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

Если подходить к этим историям формально, то можно сказать что все они порождены тем что люди не учитывают ошибку второго рода. У Юдковского, с коим знакома четверть Хабра — эта ошибка обычно зовётся «Подтверждающее искажение».



Что это такое? В двух словах — «человек ищет подтверждение своей модели, а не её опровержение». Единственный шанс объяснить лучше, это примеры-примеры-примеры и опыт. Лишь так можно развить чувство что «что-то тут не так».

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

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

Классификация лабиринтов

Лабиринты в целом (а значит, и алгоритмы для их создания) можно разбить по семи различным классификациям: размерности, гиперразмерности, топологии, тесселяции, маршрутизации, текстуре и приоритету. Лабиринт может использовать по одному элементу из каждого класса в любом сочетании.

Привет Хабр.

Наверное многие, приобретающие часы или метеостанцию, видели на упаковке логотип Radio Controlled Clock или даже Atomic Clock. Это весьма удобно, ведь достаточно поставить часы на стол, и они через некоторое время автоматически настроятся на точное время.



Разберемся как это работает и напишем декодер на языке Python.

Не так давно я прочёл фантастический роман «Задача трёх тел» Лю Цысиня. В нём у одних инопланетян была проблема — они не умели, с достаточной для них точностью, вычислять траекторию своей родной планеты. В отличии от нас, они жили в системе из трёх звёзд, и от их взаимного расположения сильно зависела «погода» на планете — от испепеляющей жары до леденящего мороза. И я решил проверить, можем ли мы решать подобные задачи.

Введение

Умножение матриц — это один из базовых алгоритмов, который широко применяется в различных численных методах, и в частности в алгоритмах машинного обучения. Многие реализации прямого и обратного распространения сигнала в сверточных слоях неронной сети базируются на этой операции. Так порой до 90-95% всего времени, затрачиваемого на машинное обучение, приходится именно на эту операцию. Почему так происходит? Ответ кроется в очень эффективной реализации этого алгоритма для процессоров, графических ускорителей (а в последнее время и специальных ускорителей матричного умножения). Матричное умножение — один из немногих алгоритмов, которые позволяет эффективно задействовать все вычислительные ресурсы современных процессоров и графических ускорителей. Поэтому не удивительно, что многие алгоритмы стараются свести к матричному умножению — дополнительная расходы, связанные с подготовкой данных, как правило с лихвой окупаются общим ускорением алгоритмов.

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

Процесс изложения будет вестись ввиде шагов с примерами по последовательному ускорению алгоритма. Я старался писать максимально упрощая задачу, но не более того. Надеюсь у меня получилось…

Буквально пару дней назад компания Aurorai передала в опытную эксплуатация систему распознавания дефектов и контроля состояния тележек для локомотивов Ермак. Задача нетривиальная и очень интересная, первым этапом которой было предложено оценить состояние тормозных колодок и ширины бандажа. Нам удалось решить задачу с точность до 1мм при скорости локоматива до 30 км/ч! Хочу отметить, что благодаря специфики можно было использовать “TTA (test-time augmentation)” – яркий пример kaggle-style хака из соревнований, который плохо ложится на прод и семантическую сегментацию на базе se_resnext50 encoder, которая даёт поразительный по точности результат в предсказании маски.