После большого перерыва продолжаем цикл о графических вероятностных моделях (часть 1, часть 2). Сегодня мы наконец-то от постановок задач перейдём к алгоритмам; поговорим мы о самом простом, но часто полезном алгоритме вывода на фактор-графах – алгоритме передачи сообщений. Или, как его ещё можно назвать, алгоритме правильной расстановки скобок.


by sergey-lesiuk

В последнее время набирает популярность семейство подходов и методологий обработки данных, объединенных общими названиями Big Data и NoSQL. Одной из моделей вычислений, применяемых к большим объемам данных, является технология Map-Reduce, разработанная в недрах компании Google. В этом посте я постараюсь рассказать о том, как эта модель реализована в нереляционной СУБД MongoDB.

Что касается будущего нереляционных баз вообще и технологии Map-Reduce в частности, то на эту тему можно спорить до бесконечности, и пост совершенно не об этом. В любом случае, знакомство с альтернативными традиционным СУБД способами обработки данных является полезным для общего развития любого программиста, так же как, к примеру, знакомство с функциональными языками программирования может оказаться полезным и для программистов, работающих исключительно с императивными языками.

Нереляционная СУБД MongoDB представляет данные в виде коллекций из документов в формате JSON и предоставляет разные способы обработки этих данных. В том числе, присутствует собственная реализация модели Map-Reduce. О том, насколько целесообразно применять именно эту реализацию в практических целях, будет сказано ниже, а пока ограничимся тем, что для ознакомления с самой парадигмой Map-Reduce эта реализация подходит как нельзя лучше.

Итак, что же такого особенного в Map-Reduce?

Недавно к нам обратился заказчик с просьбой помочь в организации небольшого Call-центр на 10 операторов. Ну конечно одно из главных требований – «подешевле».
Было предложено несколько решений, остановились на следующем, базирующемся полностью на VoIP технологии:

• 4 городских аналоговых линии принимаются голосовым шлюзом D-Link DVG-6004S
• в роли IP АТС и сервера с CRM-системой выступает сетевой накопитель D-Link DNS-325
• у старшего оператора IP-телефон D-Link DPH-400S с гарнитурой Plantronics HW111N
• у остальных операторов софтфон CounterPath X-Lite с гарнитурой Plantronics Blackwire C210
• сеть обслуживается коммутатором D-Link DES-1210-28

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

Вы могли и сами заметить, что игра крестики-нолики смертельно скучна. В ней нет места творческой идее или внезапному озарению. Хорошие игроки всегда играют вничью. Игра неизбежно идёт примерно так:



Но математики на пикнике играли в более изощренную версию игры. В каждой из клеток на квадратном поле они нарисовали поле поменьше:

Seam carving это алгоритм для изменения размера картинки, сохраняющий важный контент и удаляющий менее значимый. Он был описан в статье S. Avidan & A. Shamir. Он дает лучший результат, чем обычное растягивание изображения ввиду того, что не меняет пропорций значимых элементов изображения. Две фотографии ниже демонстрируют работу алгоритма – исходное изображение имеет размер 332x480, в то время как модифицированное seam carving'ом 272x400.


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

Не так давно мы начали рендерить 3D-модели на Гитхабе. Сегодня мы с удовольствием объявляем о новейшем прибавлении в семействе визуализаций — о геоданных. Любой файл .geojson в репозитории на Гитхабе теперь станет автоматически отображаться в качестве интерактивной карты (с возможностью листания), снабжённой вашими геоданными.



Люди ужé используют Гитхаб для хранения разных геоданных, от почтовых индексов Чикаго и до радиостанций сообществ да путей движения известных в истории ураганов, так что мы с нетерпением ожидаем увидеть дальнейшие плоды сотрудничества сообществ.

«Под капотом» мы используем Leaflet.js для отображения данных geoJSON поверх специальной версии базового слоя карты улиц MapBox — упрощённого, чтобы данные ваши на нём воссияли. Лучше же всего — то, что картооснова использует данные OpenStreetMap; так что, если пожелаете улучшить какой-либо участок её, редактируйте тотчас же.

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

Spatial hashing это простая техника, которая используется в базах данных, физических и графических движках, симуляциях частиц и вообще везде, где нужно быстро что-то найти. Если в кратце, то суть в том, что мы разбиваем пространство с объектами на ячейки и складываем в них объекты. Затем вместо поиска по значению очень быстро ищем по хэшу.

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

В продолжении статьи о кроссплатформенной и кросс-аппаратной оптимизации, на примере задачи поиска полным проходом по таблице из 5 полей и 10 000 000 строк, и неизбежности этой задачи даже при индексном поиске, я покажу как ускорить такой поиск в 3.5-5.3 раза с использованием C++ независимо от аппаратной платформы.
В предыдущей статье нам удалось ускорить поиск в 1.3 раза: GitHub.com
Мы не будем банально описывать конструкции языка, а покажем преимущества C++ при решении одного из этапов реальной задачи.
Мы по-прежнему пишем кроссплатформенно под MSVC11(MSVS2012) и GCC 4.7.2, и используем в них C и частично реализованный стандарт C++11.
Для упрощения понимания мы все ещё пишем без индексного поиска, но это решение в дальнейшем будет использоваться при индексном поиске.

Предметом внимания вчерашнего поста на Хабре стал фреймворк распределенных вычислений от Microsoft Research — Dryad.

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

В этой статье обсудим компонент верхнего уровня программного стэка фреймворка Dryad – язык запросов к распределенному хранилищу DryadLINQ.

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

Вас ждет много анализа и немного частных производных. Код прилагается.
Прошу под кат!

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

При этом большинство ну хотя бы минимально сложных и функциональных систем (во всяком случае, из тех, что встречались лично мне за 8 лет работы в банковской сфере), как правило, гетерогенны — состоят из множества функциональных блоков, как пёстро сшитое лоскутное одеяло, где каждый лоскуток выполняется разным приложением, зачастую даже на различных аппаратных платформах. Почему? Да просто это рационально и удобно. Каждый продукт хорош в своей области. Например, экономисты любят использовать Ms Excel для анализа и визуализации данных. Но мало кому в голову придёт использовать эту программу для обучения серьёзных искусственных нейросетей или решения дифференциальных уравнений в реальном времени — для этого зачастую приобретаются (или уже приобретены компанией) мощные универсальные пакеты, предлагающие гибкий API, или под заказ пишутся отдельные модули. Вот и получается, что результат считать выгоднее в том же Matlab, хранить в таблицах СУБД Oracle (запущенной на кластере Linux), а отчёт показывать пользователям в приложении Excel, работающем как OLE server на Windows. Причём связаны все эти компоненты одним из универсальных языков программирования.

Как выбрать оптимальную среду реализации для конкретной задачи?

В ходе разработки одного из наших проектов мы столкнулись с необходимостью отдавать в клиентском html большое количество графики. С точки зрения минимализации нагрузки на сервер, строить объёмную графику на стороне клиента — это единственное правильное решение. При поиске готовых и подходящих нам JS решений из этой области мы основательно подсели на JS библиотеку Raphael, которая позволяет легко прорисовывать векторную графику во всех актуальных на сегодня браузерах. Разобравшись в функционале и отладив несколько функций по созданию основных типов диаграмм, мы решили поделиться здесь своими наработками.



Итак. Описанный ниже пример создаёт средствами Raphael и PHP круговую диаграмму в формате SVG, представленную на изображении. Мы постарались максимально подробно описать исходный код, чтобы помочь всем тем, кто самостоятельно разобраться в этом не нашёл сил или времени.

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

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

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

В качестве иллюстрации поста приведу обложку другой манги из той же серии, что и книга о статистике:

В рамках своей научной активности реализовал так называемый Федеративный Фильтр Калмана (Federated Kalman Filter). В этой статье рассказывается о том, что такое «Федеративный ФК», чем он отличается от обобщенного, а также описывается консольное приложение, реализующее данный фильтр и генетические алгоритмы для подбора параметров его математической модели. Приложение было реализовано с использованием TPL (Task Parallel Library), поэтому пост будет интересен не только специалистам по цифровой обработке сигналов.

UPD1: после прочтения двух недавних статей решил тоже присоединиться к эксперименту/исследованию/авантюре (называйте как хотите). В конце статьи добавил еще один опрос — "Стали бы Вы поощрать рублем такие узко специализированные статьи на Хабрахабре?".

На днях мы открыли новый набор в Школу анализа данных. Чтобы стать её студентом, нужно ответить на вопросы в тесте, сдать экзамены и пройти собеседование. Занятия, как всегда, будут проходить в офисе Яндекса в Москве, а также в Екатеринбурге, Киеве и Минске. В Питере у ШАД есть отделение в Computer Science Center. Если вы живёте в других городах, то можете учиться у нас заочно: общаться с преподавателями по электронной почте и смотреть видеолекции. Обучение в Школе бесплатное.



В ШАД преподают ведущие российские ученые — и те, кто живет в России, и те, кто работает за рубежом. Например, теорию машинного обучения ведёт Алексей Червоненкис, профессор Лондонского университета и один из создателей отечественной школы анализа данных. Автор курса по анализу данных и научный руководитель ШАД — профессор Rutgers University Илья Мучник, который когда-то был научным руководителем Аркадия Воложа.

Twitter Bootstrap становится всё популярнее и популярнее, многие используют его в своих проектах, думаю еще больше людей используют для прототипирования интерфейсов. Я не исключение. И вот сегодня утром наткнулся на интересный сервис — LayoutIt. По сути LayoutIt — это онлайн редактор для создания интерфейсов с использованием Bootstrap. Редактор представляет собой Drag & Drop интерфейс.

Доброго времени суток.

Так случилось, что моя работа связана с написанием отчетов.
Этому я посвятил около 8 лет. Отчеты — это глаза бизнес-процесса и информация,
необходимая для принятия оперативных решений.

Вначале наш отдел делал отчеты,
— Принимая задачи по outlook
— Составляя sql-запрос
— Отправляя результаты заказчику в xls
— В лучшем случае, сохраняя sql-код куда-то в папку (а иногда и не сохраняя)

Но это было скучно и неинтересно. Так появилось простейшее приложение на PHP,
в котором каждый отчет был представлен в виде php-файла с одним классом, имеющим единственный (помимо конструктора) метод show()

В таком виде, система прожила 5,5 лет, за которые мной и еще одним человеком было написано более 500 различных отчетов.
В процессе появился опыт и стало понятно, что многое (если не все) сделано не так, да и PHP уже не устраивал.

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

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

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

Айра Гас Хант (Ira Gus Hunt), действующий Директор по технологиям ЦРУ, рассказывает о своем видении Big Data на службе ЦРУ, а также возникающие при этом задачи и методы их решения. Выступление состоялось на конференции GigaOM Structure:Data 2013, проходившей 20 марта в Нью-Йорке. Как говорят очевидцы это было одно из самых интересных и запоминающихся выступлений.

Друзья, мы наконец-то анонсировали конкурс для разработчиков Apps4Russia который мы проводим вот уже 3-й год и в этом году мы пришли к тому чтобы он был куда больше, лучше ещё полезнее для граждан и для разработчиков и для всех кто интересуется открытыми данными. Поскольку я не хочу говорить языком пресс-релизов — расскажу про конкурс как есть.

Что такое Apps4Russia?

Конкурс пропагандирует стандарты работы с open data, способствует созданию и становлению общественных, управленческих и бизнес проектов. Конкурс Apps4Russia проводится ежегодно с 2011 года и уже стал платформой для обмена ценными идеями и содержательного общения между талантливыми российскими разработчиками, ведущими экспертами в области WEB-разработок и инвесторами.

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

Номинации конкурса:

• Удобный город — инициативы и проекты, направленные на улучшение условий жизни людей в городе, повышение комфорта и пригодности среды для обитания,
• Безопасная страна — проекты, направленные на благо общества, и использующие разносторонний подход в решении вопросов обеспечения безопасности граждан и защиты их прав и свобод,
• Государство в кармане — инициативы и проекты, нацеленные на разработку мобильных приложений, для облегчения доступа граждан к важной и полезной информации о деятельности государства в привычном формате.

В этой статье я хочу рассказать о том, как реализовывал алгоритмы, связанные с базисами Грёбнера, на языке Haskell. Надеюсь, кому-нибудь мои идеи и объяснения окажутся полезными. Я не собираюсь вдаваться в теорию, так что читателю стоит быть знакомым с понятиями полиномиального кольца, идеала кольца и базиса идеала. Советую прочитать вот эту книгу МЦНМО, в ней подробно расписана вся необходимая теория.

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

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

Если вас заинтересовало, прошу под кат.