Введение

Этот текст можно рассматривать как обзор библиотеки Strutext, задуманной автором как набор эффективных алгоритмов лингвистической обработки текста на языке C++. Код библиотеки находится в репозитории на Github. Библиотека имеет открытый исходный код и поставляется под лицензией Apache License 2.0, т.е. может быть использована совершенно бесплатно без каких-либо существенных ограничений.

Одна из величайших шахматных партий всех времен и народов — это, вне всяких сомнений, сражение Гарри Каспарова и суперкомпьютера Deep Blue от IBM, в 1997 году. Это была уже вторая игра Каспарова с суперкомпьютером, матч-реванш машины.

Первая партия в игре была очень сложной и напряженной, у Каспарова было поначалу преимущество, но, начиная с 44 хода, он перестал понимать логику игры машины, и, в итоге, проиграл весь матч. Спустя некоторое время Каспаров даже обвинил инженеров IBM в «читерстве»: манипуляциях с ПО машины, которые и привели к поражению. Спустя 17 лет ситуация прояснилась — Каспаров проиграл из-за сбоя в алгоритме работы компьютера в самой первой партии всего сражения.

Привет, меня зовут Михаил Ройзнер. Недавно я выступил перед студентами Малого Шада Яндекса с лекцией о том, что такое рекомендательные системы и какие методы там бывают. На основе лекции я подготовил этот пост.

План лекции:

1. Виды и области применения рекомендательных систем.
2. Простейшие алгоритмы.
3. Введение в линейную алгебру.
4. Алгоритм SVD.
5. Измерение качества рекомендаций.
6. Направление развития.

Данная публикация — это реальный кейс от Datawiz.io, в котором мы расскажем, как найти товары и категории с большими колебаниями продаж, и как колебания продаж влияют на поведение клиентов.

Производя анализ данных для торговой сети, мы столкнулись с проблемой: при почти равных количествах продаж в день в двух магазинах сети, оборот в одном магазине «Shop1» увеличивался, а в магазине «Shop2» — снижался.

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

Сама идея не то что бы новая, но качественно никем не реализованная. На рынке уже несколько лет есть проект www.snapfashion.co.uk, но релевантность его поиска очень низкая, подбор происходит в основном по определению цвета изображения. Например, красное платье он сможет найти, но платье с определенным фасоном или рисунком уже нет. Аудитория этого проекта, к слову, не растет, мы это связываем с тем, что поиск определенно низкой релевантности и, по сути, ничем не отличается, если вы выберете на сайте магазина цвет при поиске по их каталогу.

В 2013 году появился проект www.asap54.com, и здесь поиск чуть лучше. Упор стоит на цвет и некоторые небольшие опции, указываемые вручную из специального каталога (короткое платье, длинное платье, платье средней длинны). Этот проект, столкнувшись с трудностями визуального поиска, слегка завернул в сторону социальных сетей, где модники могут делиться своими «луками» в одежде, из «шазама для одежды» в «инстаграм для модников».

Несмотря на то, что проекты в этой области существуют, определенно остается непокрытой потребность поиска по картинке, очень актуальная сегодня. И решение данной проблемы созданием мобильного приложения, как это сделали SnapFashion и Asap54, наиболее отвечает тенденциям e-commerce рынка: по различным прогнозам доля мобильных продаж в США с 11% в 2013 году может вырасти да 25-50% в 2017. Такой стремительный рост мобильной торговли предвещает и рост популярности самых разных приложений, помогающих совершать покупки. И скорее всего магазины будут сами вкладываться в разработку, продвижение подобных приложений, а также активно сотрудничать с ними.

Проанализировав конкурентов, мы решили, что нужно попробовать самим разобраться с этой темой и запустили проект Sarafan www.getsarafan.com.

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

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

Эта статья для всех, кто хранит данные клиентов и хочет решить одну из следующих задач:

1. убедиться, что адрес существует, чтобы не отправить посылку или письмо в никуда;
2. разбить адрес на компоненты, чтобы понять, где идут лучше продажи;
3. дополнить адрес недостающей информацией, чтобы оптимизировать план работы курьеров;
4. стандартизовать адреса, чтобы найти дублирующие записи одного и того же клиента;
5. актуализировать и привести адреса к формату справочника, чтобы пройти проверки регуляторов.

Задача автоматического разбора почтовых адресов кажется довольно простой на первый взгляд — бери да сопоставляй адресному справочнику (например, ФИАСу) слова из входной строки. Но все, кто за неё берутся, утопают в большом количестве особенностей адресов…

Шёл уже последний час этого воскресенья, я уже думал идти спать, но добрый sourcerer прислал мне картинку с моего заброшенного сайта, которую можно увидеть ниже, и текст «красиво!». Эти картинки я рисовал лет пять назад, с помощью т. н. алгоритма времени убегания, но для применимости данного алгоритма, нужно уметь для заданного набора преобразований разбивать плоскость на регионы, тогда я не придумал, как это сделать, и больше к этому алгоритму не возвращался. Но сейчас я сразу сообразил, что делать, и написал Диме: «Сначала Random IFS, потом kNN, а затем Escape-Time Algorithm!»



Под рукой у меня был только старый нетбук, который мне дали друзья на время, пока мой ноутбук в ремонте. Дима мне ещё что-то говорил, я ему что-то отвечал, но у меня уже в голове писался код, и я искал на нетбуке хоть какой-нибудь компилятор или интерпретатор и нашёл C++ Builder 6! После этого я понял, что утро я встречу наедине с борландовским компилятором. Через пять часов я отправил Диме новых картинок, но он, как нормальный человек, давно спал…

Пример анализа данных на основе продуктового магазина от Datawiz.io.

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

Зачастую потери в продажах случаются из-за недостаточного количества заказанного товара. Также часто товар, имеющийся на складе, не выставляется на полки. Ежедневный анализ данных помогает своевременно обнаружить такой «провал» в продажах. Далее, устраняем проблему — контролируем работу отдела закупок, оптимизируем поставки, контролируем работу торгового персонала.

Осторожно, персистентность

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

Большинство разработчиков воспринимают сборку мусора (garbage collection) как нечто само собой разумеющееся. Это стандартный процесс, который периодически освобождает память, удаляя ненужные объекты. А вот американский программист Кен Фокс (Ken Fox) захотел досконально разобраться и заглянуть «под капот» современных сборщиков мусора.

Кен «поигрался» с пятью разными алгоритмами сборки мусора и опубликовал маленькие анимации, которые наглядно демонстрируют их работу.

Анимации большего размера выложены на github.com/kenfox/gc-viz.

снизу фотографии настоящих жуков, сверху — моя реализация

Продолжение предыдущей статьи, на этот раз пишем шейдер.

Расскажу о различных реализациях эффекта размытия на GLSL.

Пост написан под влиянием поста пользователя pchelintsev_an.

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

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

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

Также, я расскажу, как мы иногда можем существенно облегчить этот процесс, используя уже собранные геномы близкородственных организмов. Этой задачей я занимался в рамках написания своей магистерской диссертации в Санкт-Петербургском Академическом Университете, а обучение проходило совместно с Институтом Биоинформатики. Поскольку получившийся алгоритм достаточно специфичен, я начну с описания проблемы в целом, дам обзор некоторых «хардварных» методов ее решения, а затем немного расскажу о том, что же получилось у меня.

Добрый день, уважаемые хаброжители!

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

Поиск выдал мне всего одну статью на Хабре по схожей тематике — «Талмуд по формулам в Google SpreadSheet». В ней дано хорошее описание базовых вещей для работы в excel (хотя он и не 100% про сам excel).

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

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

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

Добрый день!

Cybercortex.org — open source проект. Находится на этапе старта и видится как возможность сконцентрировать и скоординировать усилия компаний и разработчиков для решения задач по развитию интеллекта человека. Для внедрения в быт новых форм усиления мышления и ускорения продуктивной коммуникации. Поэтому все, кто так или иначе заинтересован в вопросе, приглашаются к сотрудничеству.

Ниже представлено описание первого модуля алгоритма Cybermean, «ядра» Cybercortex. Если описанная ниже логика будет представляться хабравчанам адекватной, то можно было бы продолжить описание и обсуждение модулей Cybermean и Cybercortex в целом. Также, в конце поста, помимо логики первого модуля, приводится изображение связи интерфейсов в рамках Cybercortex, в качестве дополнительного наглядного материала, характеризующего тематику проекта.

Folly — это открытая С++ библиотека, разрабатываемая Facebook и используемая им во внутренних проектах. С целью оптимизации расходов памяти и процессорных ресурсов библиотека включает собственные реализации некоторых стандартных контейнеров и алгоритмов. Одной из них является folly::fbvector — замена стандартного вектора (std::vector). Реализация от Facebook полностью совместима с оригинальным интерфейсом std::vector, изменения всегда не-негативны, почти всегда измеримы, часто — существенно, а иногда даже грандиозно влияют на производительность и\или расход памяти. Просто включите заголовочный файл folly/FBVector.h и замените std::vector на folly::fbvector для использования его в своём коде.

Пример

folly::fbvector<int> numbers({0, 1, 2, 3});
numbers.reserve(10);
for (int i = 4; i < 10; i++) {
  numbers.push_back(i * 2);
}
assert(numbers[6] == 12);

Мотивация

std::vector — устоявшаяся абстракция, которую многие используют для динамически-аллоцируемых массивов в С++. Также это самый известный и самый часто используемый контейнер. Тем большим сюрпризом оказывается то, что его стандартная реализация оставляет достаточно много возможностей по улучшению эффективности использования вектора. Этот документ объясняет, как реализация folly::fbvector улучшает некоторые аспекты std::vector. Вы можете воспользоваться тестами из folly/test/FBVectorTest.cpp чтобы сравнить производительность std::vector и folly::fbvector.

Поиск оптимального маршрута юнита к цели на неизвестной карте — одна из самых сложных задач при разработке игры. К счастью, существует некоторое количество алгоритмов, которые решают эту задачу. Есть и отличная библиотека PathFinding.js с поддержкой 11 таких алгоритмов.