23 июня 2018 года состоялся финал ML-Блица, конкурса по машинному обучению, организованного Яндексом. Ранее мы анонсировали его на Хабре и рассказывали, какие примерно задачи могут встретиться на реальном соревновании.

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

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

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

Все мои решения доступны на GitHub

Совсем недавно вернулся с очередной рабочей встречи с уважаемым Заказчиком, на которой мы долго и чрезвычайно увлекательно дискутировали о необходимых затратах и, соответственно, стоимости небольшого подпроекта. На встрече было человек шесть с достаточно высокими грейдами, развитыми навыками коммуникации, ведения переговоров и большим опытом аргументации своей позиции. Встреча затянулась, стороны были настойчивы и в результате сошлись на компромиссном результате – Заказчик получил скидку, сравнимую со стоимостью потраченного времени на ее выбивание. То есть в финансовом выражении результат встречи близок к нулю, потраченное время уже никогда не восполнить, но при этом удалось приблизиться к завершению и передаче Заказчику требуемой ценности. И всю дорогу обратно я задавался вопросом – а можно было бы решить задачу более эффективно? Можно ли было сохранить время и ресурсы, свои и заказчика, но при этом добиться того же результата? Где та точка роста, которая позволит решать задачи быстрее, а тратить меньше?

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

Мне нужен был инструмент. Острый, практичный, универсальный. Отвечающий всем моим требованиям и расширяемый по моему желанию.



Но простой и удобный. Тут надо отметить, что на основной работе я не разработчик, поэтому постоянной среды программирования на рабочем компе не имею и, когда это требуется, пишу на чем придется — bat, JScript, VBA в MSOffice (да, это Windows, корпоративные системы, тут нет bash и perl «из коробки»), макросы в разном ПО и т.д. Все это помогает решить текущую задачу, но уровень и возможности маленько не те, что хотелось бы иметь.

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

Вы скажете, что сейчас есть инструменты на любой вкус и цвет, только выбирай. Лягушка aka TOAD под Oracle, SoapUI для шины и продукты GNU и Apache для всего остального.
Но проблема в том, что все они они специализированы под одну какую-то деятельность, а с другой стороны слишком универсальны — можно сделать многое, но многими действиями. А если возможность в продукте отсутствует, то добавить ее нельзя. Либо продукт закрытый, либо нужно разрабатывать/покупать плагин, либо качать исходники и в них разбираться. А мне нужен был инструмент, в котором простые действия делаются просто, а на сложные сначала тратится немного времени и дальше опять все просто.

Привет, Хаброжители! Данная книга — руководство по самым разным вычислительным и статистическим методам, без которых немыслима любая интенсивная обработка данных, научные исследования и передовые разработки. Читатели, уже имеющие опыт программирования и желающие эффективно использовать Python в сфере Data Science, найдут в этой книге ответы на всевозможные вопросы, например: как считать этот формат данных в скрипт? как преобразовать, очистить эти данные и манипулировать ими? как визуализировать данные такого типа? как при помощи этих данных разобраться в ситуации, получить ответы на вопросы, построить статистические модели или реализовать машинное обучение?

Ниже под катом обзор книги и отрывок «Гистограммы, разбиения по интервалам и плотность»

Bash-скрипты: начало
Bash-скрипты, часть 2: циклы
Bash-скрипты, часть 3: параметры и ключи командной строки
Bash-скрипты, часть 4: ввод и вывод
Bash-скрипты, часть 5: сигналы, фоновые задачи, управление сценариями
Bash-скрипты, часть 6: функции и разработка библиотек
Bash-скрипты, часть 7: sed и обработка текстов
Bash-скрипты, часть 8: язык обработки данных awk
Bash-скрипты, часть 9: регулярные выражения
Bash-скрипты, часть 10: практические примеры
Bash-скрипты, часть 11: expect и автоматизация интерактивных утилит

Сегодня поговорим о bash-скриптах. Это — сценарии командной строки, написанные для оболочки bash. Существуют и другие оболочки, например — zsh, tcsh, ksh, но мы сосредоточимся на bash. Этот материал предназначен для всех желающих, единственное условие — умение работать в командной строке Linux.

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

Постановка задачи поиска в строке

Часто приходится сталкиваться со специфическим поиском, так называемым поиском строки (поиском в строке). Пусть есть некоторый текст Т и слово (или образ) W. Необходимо найти первое вхождение этого слова в указанном тексте. Это действие типично для любых систем обработки текстов. (Элементы массивов Т и W – символы некоторого конечного алфавита – например, {0, 1}, или {a, …, z}, или {а, …, я}.)

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

Поиск строки формально определяется следующим образом. Пусть задан массив Т из N элементов и массив W из M элементов, причем 0<M≤N. Поиск строки обнаруживает первое вхождение W в Т, результатом будем считать индекс i, указывающий на первое с начала строки (с начала массива Т) совпадение с образом (словом).
Пример. Требуется найти все вхождения образца W = abaa в текст T=abcabaabcabca.

Образец входит в текст только один раз, со сдвигом S=3, индекс i=4.

По просьбам трудящихся выкладываю описание и доказательство алгоритма Укконена.

Описание задачи

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

Бор для произвольного набора строк строится за O (суммы длин этих строк). Очевидно, что сумма длин всех суффиксов строки пропорциональна квадрату длины самой строки. Таким образом, построение суффиксного дерева тривиальным алгоритмом работает за O(N²). И тут возникает резонный вопрос, можно ли построить суффиксное дерево быстрее?

На самом деле можно.

Суффиксное дерево – мощная структура, позволяющая неожиданно эффективно решать мириады сложных поисковых задач на неструктурированных массивах данных. К сожалению, известные алгоритмы построения суффиксного дерева (главным образом алгоритм, предложенный Эско Укконеном (Esko Ukkonen)) достаточно сложны для понимания и трудоёмки в реализации. Лишь относительно недавно, в 2011 году, стараниями Дэни Бреслауэра (Dany Breslauer) и Джузеппе Италиано (Giuseppe Italiano) был придуман сравнительно несложный метод построения, который фактически является упрощённым вариантом алгоритма Питера Вейнера (Peter Weiner) – человека, придумавшего суффиксные деревья в 1973 году. Если вы не знаете, что такое суффиксное дерево или всегда его боялись, то это ваш шанс изучить его и заодно овладеть относительно простым способом построения.

Здравствуйте, уважаемое сообщество! Думаю, многим знакома такая структура данных как суффиксное дерево. На Хабре уже было описание как его построить и зачем. Если вкратце, то оно нужно тогда, когда надо много раз искать какие-то произвольные образцы X_i в заранее заданном тексте A, а строится такое дерево мучительно с помощью алгоритма Укконена (есть и другие варианты, но они предполагают еще большее количество страданий). Общее наблюдение при работе с алгоритмами таково, что деревья — это, конечно, хорошо, но на практике их лучше избегать из за серьезных оверхэдов по памяти и не очень оптимального (с точки зрения эффективности оперирования данными компьютером) расположения. Кроме того, именно в таком дереве есть еще более существенная неприятность, а именно алфавитнозависимость структуры. Для решения этих проблем был придуман суффиксный массив. О том как его строить и как использовать и пойдет в этой статье.

Материал статьи предполагает знание понятий суффикса и префикса строки, а также знание того, как работает бинарный поиск. Надо также представлять, что такое стабильная сортировка и поразрядная сортировка, а также понимание, что имеется ввиду под стабильной сортировкой подсчетом. Для некоторых частей нам понадобится знание задачи о минимуме на отрезке — Range Minimum Query (RMQ). Ну, в общем, вас предупредили: никто не говорил, что будет просто.

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

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

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

Введение

Алгоритмы нечеткого поиска (также известного как поиск по сходству или fuzzy string search) являются основой систем проверки орфографии и полноценных поисковых систем вроде Google или Yandex. Например, такие алгоритмы используются для функций наподобие «Возможно вы имели в виду …» в тех же поисковых системах.

В этой обзорной статье я рассмотрю следующие понятия, методы и алгоритмы:

• Расстояние Левенштейна
• Расстояние Дамерау-Левенштейна
• Алгоритм Bitap с модификациями от Wu и Manber
• Алгоритм расширения выборки
• Метод N-грамм
• Хеширование по сигнатуре
• BK-деревья

А также проведу сравнительное тестирование качества и производительности алгоритмов.

Я часто собеседую разработчиков и часто задаю им простой, как кувалда, вопрос — как внутри работает JOIN в SQL? В ответ я обычно слышу бессвязное мычание про волшебные деревья и индексы, которые быстрее. Когда-то мне казалось, что каждый программист специалист должен знать то, с чем работает. Впоследствии жизнь объяснила мне, что это не так. Но мне все еще не понятно, как можно годами теребить базёнку, даже не догадываясь, а что там у нее «под капотом»?

Давайте проведем ликбез и вместе посмотрим, как же работают эти джойны, и даже сами реализуем парочку алгоритмов.

Реляционные базы данных (РБД) используются повсюду. Они бывают самых разных видов, от маленьких и полезных SQLite до мощных Teradata. Но в то же время существует очень немного статей, объясняющих принцип действия и устройство реляционных баз данных. Да и те, что есть — довольно поверхностные, без особых подробностей. Зато по более «модным» направлениям (большие данные, NoSQL или JS) написано гораздо больше статей, причём куда более глубоких. Вероятно, такая ситуация сложилась из-за того, что реляционные БД — вещь «старая» и слишком скучная, чтобы разбирать её вне университетских программ, исследовательских работ и книг.

На самом деле, мало кто действительно понимает, как работают реляционные БД. А многие разработчики очень не любят, когда они чего-то не понимают. Если реляционные БД используют порядка 40 лет, значит тому есть причина. РБД — штука очень интересная, поскольку в ее основе лежат полезные и широко используемые понятия. Если вы хотели бы разобраться в том, как работают РБД, то эта статья для вас.

Некоторое время назад в московский офис Яндекса приезжал Игорь Пак — ученый с множеством научных работ, выпускник мехмата МГУ и аспирантуры Гарварда. Сейчас Игорь работает в Калифорнийском университете. Его лекция в Яндексе была посвящена различным классам последовательностей и перестановкам. В том числе прямо по ходу лекции он представил выкладки, опровергающие гипотезу Нунана и Зайлбергера — одну из ключевых в области перестановок.



Под катом — подробная текстовая расшифровка и большинство слайдов.

У нас, как и во многих других организациях, проводится тестирование соискателей при поступлении их на работу. Основу тестирования составляет устное собеседование, но в некоторых случаях, даются также практические задания. Несколько дней назад, Руководство попросило меня подготовить набор задач на знание SQL.

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

Несколько месяцев назад один из наших конкурентов начал делать странное – предлагать нашим клиентам сравнение своей системы рекомендаций с Retail Rocket через АБ-тесты в формате «пари» с обязательством заплатить 100 000 рублей в случае проигрыша.

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

Первый тест с Rees не заставил себя ждать, но в ходе его проведения мы столкнулись с довольно странными результатами, которые вылились в серьезное исследование. То, что мы обнаружили в итоге, удивило нас так сильно, что мы хотим поделиться деталями этого исследования и вынести его результаты на суд IT-сообщества и индустрии электронной коммерции в России.

Введение

В мае далёкого 2015 года я заканчивал бакалавриат факультета общей и прикладной физики МФТИ. В основном я занимаюсь квантовой теорией поля, но в тот момент я решил, что хотелось бы больше вникнуть в современный мир компьютерных наук, что можно попробовать совместить МФТИ с ШАД Yandex (две магистратуры). ШАД тогда уже был у всех на слуху, вокруг только и твердили, какой там жёсткий курс алгоритмов, мне понравился сайт (лол), тематика курсов, и я решился поступать.

В этом посте я хотел бы рассказать о том, как происходило моё поступление в ШАД, рассказать своё решение экзаменационного варианта (разборов ШАДовских заданий на просторах рунета не очень-то много) и поговорить о том, что понравилось / не понравилось в этом замечательном заведении.

При поступлении в ШАД проверяются знания в рамках общей программы, включающей базовые разделы высшей алгебры, математического анализа, комбинаторики, теории вероятностей, а также основы программирования. Под катом подробно разобраны задачи вступительного экзамена в ШАД 2014 года. Внимание! Пост довольно объёмный, поэтому устраивайтесь поудобнее, вооружайтесь карандашом, если нужно, доставайте чай с печеньем. Убедитесь, что сделали все дела на вечер! Велика вероятность, что рассматриваемые ниже задачи поглотят ваш разум на несколько часов, а кому-то помешают вовремя лечь спать. Во всяком случае сегодняшний вечер обещает быть интересным. Добро пожаловать под кат ↓