Алгоритмы *

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

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

«Три девицы под окном пряли поздно вечерком.»



Ну как пряли. Не пряли, конечно, а лайкали друг на друга. По условиям конкурса «мисс Салтан» девицы должны были выбрать меж собой лучшую.

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

Вскоре «в светлицу вошел царь — стороны той государь» (показан на рисунке). «Во все время разговора...», — ну понятно в общем.
«Собираем лайки нежности — формируем матрицу смежности», — бодро срифмовал он.
Девицы-красавицы с именами Алена, Варвара и Софья засмущались, но лайки (из балалайки) передали.

Вот что там было:

• Алена получила 1 лайк от Софьи и 2 лайка от Варвары.
• Варвара получила по лайку от Алены и Софьи.
• А Софья получила 2 лайка от Алены и 1 от Варвары.

Царь взял лайки, покрутил гайки, постучал по колесам, пошмыгал носом, причмокнул губами, поскрипел зубами, сгонял в палаты и объявил результаты.

Наибольший вес лайков (7 баллов) получила Софья, но титул «мисс Салтан» достался Алене (15 баллов).


После объявления результатов девицы бросились обратились к царю с просьбой рассказать,- откуда взялись эти странные цифры?

PHP имеет всего одну структуру данных для управления всем. array — сложный, гибкий, гибридный, сочетает в себе поведение list и linked map. Но мы используем его для всего, потому что PHP придерживается прагматичного подхода: иметь предельно правильный, здравый и реалистичный способ решения проблемы, исходящий из практических, а не теоретических рассуждений. array позволяет делать работу, хотя о нем и так много рассказывают на лекциях по информатике. Но, к сожалению, с гибкостью приходит и сложность.

Последний релиз PHP вызвал большое оживление в сообществе. Мы не могли дождаться того, чтобы начать использовать новые возможности и почувствовать вкус ~2х прироста производительности. Одна из причин, почему это случилось — структура array была переработана. Но массивы все также придерживаются принципа «оптимизировано для всего; оптимизировано для ничего», еще не все идеально, есть возможности для совершенствования.

А что насчет структур данных SPL?

К сожалению… они ужасны. Раньше, до PHP7, они предлагали _некоторые_ преимущества, но сейчас мы дошли до точки, когда использование SPL не имеет практического смысла.

Почему мы не можем просто поправить и улучшить их?

Да, мы могли бы, но я считаю, что их дизайн и реализация настолько бедны, что лучше бы найти более современную замену.

«SPL data structures are horribly designed.»
— Anthony Ferrara

---

Введение: php-ds — расширение для PHP7, добавляющее структуры данных. Этот пост кратко охватывает поведение, производительность и преимущества каждой из них. Также в конце вы найдете список ответов на ожидаемые вопросы.

Github: https://github.com/php-ds
Пространство имен: Ds\
Интерфейсы: Collection, Sequence, Hashable
Классы: Vector, Deque, Stack, Queue, PriorityQueue, Map, Set

Недавно столкнулся с такой задачей: «Объединить две очереди таким образом, чтобы суммарная очередь была отсортирована». Причём требование для сортировки такое: не использовать никаких промежуточных объектов, кроме одной переменной, каким бы медленным алгоритм ни был. Первые попытки составить алгоритм сортировки очереди приводили к вопросу о том, как выйти из бесконечного цикла, но в конечном итоге я получил необходимый алгоритм, о котором и пойдёт речь.

Привет, Хабр.

Итак, третий курс Школы Данных «Билайн» подходит к завершению и мы набираем четвёртый.

У нас 18 занятий, 36 часов, все основные темы машинного обучения и анализа данных, куча практики, куча домашек, два Kaggle соревнования, презентации и воркшопы от партнеров, возможность устройства в Билайн в команду BigData для лучших студентов, сокурсники из различных областей бизнеса, где применяется машинное обучение и много чего ещё.

А вот задачка на выходные! Она плохо подходит, чтобы спрашивать на собеседовании, потому что слишком уж на инсайт (пожалуйста, никогда не задавайте такие на собеседованиях), и слишком простая для соревнований. Как раз чтобы доставить тот самый satisfying click в мозгу, за который мы любим программирование. Итак:

Есть большой массив из N 32-битных чисел. Каждое число встречается два раза, а два числа -- по одному. Найти эти два числа за один проход по массиву с константными затратами памяти (то есть не зависящими от размера массива).

Не забывайте использовать тег <spoiler> для решений в комментариях!

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



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

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

Шел я как-то по дорожке и вяло размышлял на тему того, что опять придется или тащиться в обход, или пачкать обувь. С возмущения типа «вот же дураки это проектируют» мысль плавно перетекла на слышанную когда-то байку про некий наукоград, где дорожки во дворах сперва не сделали вовсе, а потом просто заасфальтировали протоптанные людьми тропинки, получив сеть удобных жителям маршрутов. А оттуда мысль перекочевала к идее «а почему бы не сделать то же самое, но на компьютере?». Разработать программу, которая по заданной карте предскажет, где люди будут топтать газоны и где неплохо бы сделать асфальтовое покрытие?

Под катом — описание алгоритма и пара примеров его работы для реальных питерских дворов.

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

Готовил я как-то тесты для системы, один из модулей которой помимо всего остального вычислял значение хеш-функции для загружаемого файла. В ТЗ был прописан и необходимый алгоритм — ГОСТ Р 34.11-94. За эталон я взял значение хеша, посчитанного сторонней утилитой Rhash.

f86c9ecfb6e63726b35ebc79528d013d52b781e06e29d7eb0c9d1cb256efb7c1

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

964ba8755ca782ec3c5e0f98c93347f9b96d9f39cf5c7fdef43a23273fe8868a

Кто не прав — разработчик модуля или утилиты?

В начале марта в офисе Mail.Ru Group прошла двухдневная конференция Data Fest², посвящённая всевозможным актуальным вопросам в сфере анализа данных, как практическим, так и теоретическим. Кроме того, в рамках конференции прошёл хакатон, участники которого пытались как можно точнее предсказать результаты турнира по Dota 2, а также питч-постер сессия для исследователей, на которой были представлены различные разработки и исследовательские проекты. Предлагаем вашему вниманию видеозаписи всех выступлений на Data Fest².

В последнее время, в связи с растущим трендом виртуальной реальности, все более актуальными становятся съемка/монтаж/обработка видео в формате «видео 360».

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

В предыдущей части статьи был разобран общий принцип работы системы: мы увидели, что двумя основными её блоками являются интерполятор и нумератор. Мы построили схему взаимодействия, а также полностью обсудили реализацию интерполятора. В этой части мы разберём реализацию нумератора: обратимой функции, переводящей набор значений ключевых полей в натуральное число (BigInteger) таким образом, что набор меньше набора с точки зрения СУБД тогда и только тогда, когда . Говоря проще — научимся интерполировать наборы значений и, что самое интересное, строки:

В нашем блоге мы пишем о разработке систем связи и о первых шагах на пути к продвинутому программированию.

Однако участием в олимпиадах активность студентов не ограничивается: сегодня мы поговорим о том, как работает Студенческое конструкторское бюро (Robotics engineering department или RED), созданное в рамках кафедры СУиИ (Систем Управления и Информатики) Университета ИТМО.

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

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



Все дело в том, что разработка ПО — это не просто алгоритмы или языки.

Известно, что дерево – довольно сложная структура. И если чтение успешно реализуется в том числе рекурсией (которая не лишена своих проблем), то с изменением дела обстоят совсем не хорошо.

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

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

Это образное объяснение, если поскрипеть мозгами, обычно, конечно же, понимается только отчасти. Далее зипперы откладываются в сторону, потому что «это непонятная какая-то функциональная заморочка, типа монад, потом разберусь».

У автора «потом» уже наступило. Эта статья – попытка дать альтернативное объяснение зипперов (не путать с объяснением для альтернативно одаренных, хотя…) такое, что позволит быстро понять и немедленно начать использовать зипперы в практических задачах.

Рассказывая о вероятностном программировании и Байесовской статистике, я обычно не уделяю особого внимания тому, как, на самом деле, выполняется вероятностный вывод, рассматривая его как некий «чёрный ящик». Вся прелесть вероятностного программирования заключается в том, что, на самом деле, для того, чтобы строить модели, не обязательно понимать, как именно делается вывод. Но это знание, безусловно, весьма полезно.

Как-то раз я рассказывал о новой Байесовской модели человеку, который не особенно разбирался в предмете, но очень хотел всё понять. Он-то и спросил меня о том, чего я обычно не касаюсь. «Томас, — сказал он, — а как, на самом деле, выполняется вероятностный вывод? Как получаются эти таинственные сэмплы из апостериорной вероятности?».

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

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

Часто появляются статьи вида «нужны ли программисту алгоритмы», и все они имеют примерно одинаковый шаблон. Автор статьи как правило пишет: «Я N лет пишу сайты/скрипты в 1С, и никогда не пользовался алгоритмами или структурами данных. Тут же приводятся в пример красно-чёрные деревья или какие-нибудь другие экзотические структуры, которые в области, в которой работает автор не часто увидишь, если увидишь вообще. Такие статьи сводятся к тому, что в конкретной области программисты не используют сложные структуры данных и не решают NP задач.

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

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

===> ===>

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