Алгоритмы *

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

Сама идея не то что бы новая, но качественно никем не реализованная. На рынке уже несколько лет есть проект 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 таких алгоритмов.

В этой статье предлагаются правила для двумерного клеточного автомата, который, с одной стороны очень похож на игру Жизнь Джона Конвея (Conway’s Game of Life), а с другой — обладает существенными отличиями. Прежде всего, его отличает увеличенное до трех количество состояний клеток, повышенная способность к самоорганизации, неограниченное время активной эволюции и неограниченное количество движущихся конфигураций.

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

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


[00] Пример движущейся конфигурации, генерирующей поток степперов

Человек любит играть с цифрами или цифры с человеком? В классическом среднем образовании есть забавный парадокс: школьников натаскивают зазубривать правила и случаи их применения, но чем больше ученик знает правил и исключений, тем чаще имеет возможность совершить ошибку. В диктанте, сотканном из текстов классической русской литературы, изобилие запятых уточняющего характера, приводит к мысли, что именно не поставленная запятая является ошибкой. Следовательно, грамотная работа – это сочинение с большим количеством запятых. Проблема причинно-следственной связи, не так ли? Может быть, если вы хороший писатель, вы используете много запятых уточняющего характера, но это не тот случай, когда количество запятых делает вас хорошим писателем…

Интерпретация запятых в классической русской литературе – это пример плохого анализа данных, построенного на отсутствии любознательности и понимания математической статистики. Эти факторы + страстное желание развиваться в области информационных технологий – ключевые в понимании специальности «учёного по данным».

Пусть мы хотим вычислить десятимиллионное число Фибоначчи программой на Python. Функция, использующая тривиальный алгоритм, на моём компьютере будет производить вычисления более 25 минут. Но если применить к функции специальный оптимизирующий декоратор, функция вычислит ответ всего за 18 секунд (в 85 раз быстрее):


Дело в том, что перед выполнением программы интерпретатор Python компилирует все её части в специальный байт-код. Используя метод, описанный хабрапользователем SkidanovAlex, данный декоратор анализирует получившийся байт-код функции и пытается оптимизировать применяющийся там алгоритм. Далее вы увидите, что эта оптимизация может ускорять программу не в определённое количество раз, а асимптотически. Так, чем больше будет количество итераций в цикле, тем в большее количество раз ускорится оптимизированная функция по сравнению с исходной.

Эта статья расскажет о том, в каких случаях и каким образом декоратору удаётся делать подобные оптимизации. Также вы сможете сами скачать и протестировать библиотеку cpmoptimize, содержащую данный декоратор.

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