Алгоритмы *

В одном из предыдущих постов было сказано несколько слов о принципах подбора докладов Программным комитетом конференции HighLoad++, среди которых было и такое громкое заявление, как: «Демократия не работает».

Хотелось бы пояснить, что, конечно же, это не так.
Ещё как работает – секрет успеха в правильном приготовлении.

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

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

Существует множество книг и статей по данной теме. В этой статье я попробую понятно рассказать самое основное.

Бинарное дерево — это иерархическая структура данных, в которой каждый узел имеет значение (оно же является в данном случае и ключом) и ссылки на левого и правого потомка. Узел, находящийся на самом верхнем уровне (не являющийся чьим либо потомком) называется корнем. Узлы, не имеющие потомков (оба потомка которых равны NULL) называются листьями.


Рис. 1 Бинарное дерево

На днях столкнулся с интересной задачкой, которая показалась мне достойной аудитории данного ресурса. Условие ее следующее:

«Найти максимально допустимое отклонение массы конфеты при ее производстве, чтобы нетто коробки, состоящей из 12 штук их, не выходило за пределы 310±7 грамм в 90% случаев. Закон распределения считать нормальным.»

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

Я предложил читателям решить задачу самостоятельно и должен сказать, что они справились с этим лучше меня. В своем же решении я я сделал не верное допущение.

Примечания tsafin:

Перед публикацией своего цикла статей по MapReduce в Caché, мне показалось важным озвучить данную прошлогоднюю точку зрения из статьи Адама Дрейка «Command-line tools can be 235x faster than your Hadoop cluster». К сожалению оригинальная статья Тома Хайдена, на которую он ссылается стала уже недоступна на сайте Тома, но её, по-прежнему, можно найти в архивах. Для полноты картины предлагаю ознакомиться и с ней тоже.

Введение

Посещая в очередной раз свои любимые сайты, я нашел крутую статью Тома Хайдена об использовании Amazon Elastic Map Reduce (EMR) и mrjob для вычисления статистики отношения выигрыш/проигрыш в наборе данных со статистикой по шахматным матчам, которую он скачал с сайта millionbase archive, и c которой он начал играться используя EMR. Так как объем данных был всего 1.75GB, описывающий 2 миллиона шахматных партий, то я скептически отнесся к использованию Hadoop для данной задачи, хотя были и понятны его намерения просто поиграться и изучить плотнее, на реальном примере, утилиту mrjob и инфраструктуру EMR.

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

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

В общем случае решение задачи слежения содержит три основных этапа:
– выделение сегментов;
– установление соответствия между выделенными сегментами и отслеживаемыми объектами;
– уточнение или прогнозирование положения объектов интереса.

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

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

Всем привет! Навигация в приложении MAPS.ME является одной из главных особенностей, на которые мы делаем упор. Недавно мы рассказали вам про пешеходную навигацию. Сегодня я хочу вам рассказать о том, как мы отображаем навигационные данные в MAPS.ME. Под навигационными данными я подразумеваю линии маршрута, стрелочки для отображения маневров и положение пользователя на маршруте. Данный пост не коснется ни алгоритмов построения маршрутов по данным OSM, ни алгоритмов выделения маневров, а исключительно рендеринга. Заинтересовавшихся прошу под кат.

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

Но будем говорить немного о другом.

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

Когда категорийный менеджер или маркетолог торговой сети вплотную подходит к проведению АВС анализа у него неизбежно возникает целый ворох вопросов, колебаний и сомнений. Именно с ними мы и будем работать в данной статье!

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

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

Аннотация

1. Есть страдание.
2. Есть причина страдания.
3. Есть прекращение страдания.
4. Есть путь, ведущий к избавлению от страданий.

4 благородные истины буддизма

Настоящая статья содержит описание раннего прототипа, который вводит понятие реплицируемого объекта (replicated object) или сокращённо replob. Такой объект является дальнейшим переосмыслением борьбы со сложностью кода, возникающего при программировании распределённых систем. Replob устраняет зависимость от стороннего сервиса и реализует согласованное изменение любых пользовательских объектов, представляющих соответствующие данные и функциональность. Эта идея основана на использовании выразительности языка C++ и объектно-ориентированного подхода, что позволяет использовать сложную логику внутри распределённых транзакций. Это позволяет значительно упростить разработку отказоустойчивых приложений и сервисов. Последующие статьи будут более детально объяснять развиваемый подход.

Введение

ПРЕДУПРЕЖДЕНИЕ. Почти все методы, указанные в статье, содержат грязные хаки памяти и ненормальное использование языка C++. Так что, если вы не толерантны к таким извращениям, пожалуйста, не читайте эту статью.

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

Вопреки названию и первому впечатлению, которое возникает у большинства обывателей — «Big Data» не является просто «большими данными» и даже не объединяет под собой все массивы с неограниченными (или постоянно обновляющимися и расширяющимися) данными.

На самом деле «Big Data» — это в первую очередь подходы, инструменты и методы обработки непосредственно данных. Которые, в свою очередь, чаще всего не структурированы, многообразны и разнородны.

И, что наиболее важно, «Big Data» — это новая секция 2015 года в рамках программы HighLoad++, впервые предложенная, к слову, именно на встрече докладчиков. Первые, единичные, доклады, появились еще в прошлых годах:

Приходилось ли вам часами ходить по торговому центру в поисках вещи, которую вы уже видели в одном из магазинов, но не можете вспомнить, где именно? Или искать в музее самый интересный экспонат? Знакома ли вам ситуация, когда вы, выйдя из торгового центра, долгое время искали автомобиль на парковке?

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

Или, например, музеи – Большой Гатчинский дворец в пригороде Санкт-Петербурга.

В субботу, 19 сентября, состоялся финальный раунд RCC 2015. Победителем и обладателем главного приза в 300 000 рублей стал Петр Митричев, который уже завоевывал кубок RCC дважды: в 2011 и 2013 годах. Второе место и приз в 150 000 рублей получил победитель RCC прошлого года — Геннадий Короткевич. Третье место, как и в прошлом году, занял Егор Куликов. Его приз составил 90 000 рублей. Также призы по 30 000 рублей получили участники, занявшие с 4 по 10 места — Павел Марин, Владислав Епифанов, Сергей Копелиович, Юрий Писарчик, Константин Семенов, Михаил Тихомиров и Николай Калинин.

Герои раунда:

• Первым за 6 минут и 8 секунд решил задачу A (Сгибание ленточки) Геннадий Короткевич (tourist), он же раньше всех — за 45 минут и 29 секунд — справился с задачей D (Правильный сад).
• Финалист из Японии Kawai Ryuta (anta) раньше всех решил задачу B (Сбор монет) — за 16 минут и 20 секунд.
• Петр Митричев (Petr) первым решил задачу С (Топологическая сортировка и дети) — за 45 минут и 29 секунд.
• Задачу F (Робот на дереве) не смог решить ни один из финалистов.

Как мы говорили, в этом году финал проходил в уникальном для IT-чемпионата формате: он сопровождался четырёхчасовым онлайн-шоу, которое транслировалось на нашем сайте. Мероприятие в прямом эфире вели популярный российский шоумен Антон Комолов (выпускник МГТУ им. Баумана) и руководитель Центра олимпиадной подготовки программистов Саратовского Государственного Университета Михаил Мирзаянов. Гостями студии стали Николай Никифоров — министр связи и массовых коммуникаций РФ, представители ведущих IT-компаний и ключевые эксперты отрасли. Запись трансляции можно посмотреть на https://it.mail.ru/rcc/.

А теперь перейдем к разбору задач.

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

• гистограмма
• ящик с усами

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

Всё началось одним летним вечером, во время чтения книги эволюционного биолога Ричарда Докинза «Бог как иллюзия». Данная книга о религии, вере и атеизме, но автор кратко ссылается на другую книгу «Эгоистичный ген» и вводит одноимённое понятие. Меня долгое время восхищало изящество генетических алгоритмов. И вот, спустя месяц, в очередной раз пытаясь придумать какой-нибудь мини-проект, меня внезапно осенило – а что, если с помощью генетических алгоритмов симулировать эволюцию и посмотреть, что и как будет развиваться. Задача это сложная и на данном этапе развития IT, полагаю, нерешаемая, так что пришлось заняться чем-либо попроще. А именно, проверить гипотезу эгоистичного гена. Заинтересовавшихся, прошу под кат…

Третьего дня, во время сортировки старых закладок, попалась мне на глаза блок-схема с алгоритмом выбора STL-контейнера. «Почему же для контейнеров есть, а для стандартных алгоритмов нет? — подумал я. — Это необходимо исправить». Подумано — сделано. Сперва планировалось за пару часов нарисовать нечто простенькое, но в дальнейшем обнаружилось, что алгоритмы никак не хотят умещаться в простенькую схему. Я слегка увлекся, и спустя два вечера схема вобрала в себя 84 алгоритма, а также немного дополнительной информации. Под катом можно увидеть, что получилось в итоге.

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

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

Работая над статьей «Глубокое обучение на R...», я несколько раз встречал упоминание t-SNE — загадочной техники нелинейного снижения размерности и визуализации многомерных переменных (например, здесь), был заинтригован и решил разобраться во всем в деталях. t-SNE это t-distributed stochastic neighbor embedding. Русский вариант с «внедрением соседей» в некоторой мере звучит нелепо, поэтому дальше буду использовать английский акроним.