Вступление

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

Начальное описание

Алгоритм Ахо-Корасик реализует эффективный поиск всех вхождений всех строк-образцов в заданную строку. Был разработан в 1975 году Альфредом Ахо и Маргарет Корасик.
Опишем формально условие задачи. На вход поступают несколько строк pattern[i] и строка s. Наша задача — найти все возможные вхождения строк pattern[i] в s.

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

Хабр, я понимаю, что сегодня еще далеко не пятница — но увиденное при себе держать нет сил.

Танцующий Бендер Родригес на чистом CSS3

Создан или вручную, или при помощи Sencha Animator.

Для всех, кому понравится: вот более сложные примеры того, что может быть сделано при помощи CSS3 (и рассказ о них с концеренции CSSConf.eu).

В сырцах разных авторов видел я разные варианты вечного цикла. Чаще всего мне встречались следующие:

while (true) {
...
}

и

for (;;) {
...
}

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

Привет, Хабр!

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

Все в одном: планшет Nokia Lumia 2520

Представляем вам свой первый планшет — Nokia Lumia 2520, работающий на ОС Windows 8.1 RT.

От переводчика

Оригинал этой статьи вышел первого ноября прошлого года. Меньше чем через неделю издательство THQ потеряло половину своей капитализации, а к рождественским праздникам и вовсе объявило о банкротстве. Почему? Что ж, возможно, здесь есть часть ответа. Итак, друзья, печальная и страшная история про ААА-геймдев и тех, кто варится в его котле. Надеюсь, вам понравится.

Как плохой менеджмент, некомпетентность и гордость убили принадлежавшую THQ Kaos Studios.

Это случилось на рождественской вечеринке, хотя вряд ли можно было назвать радостным хоть кого-то из разработчиков Kaos или их коллег. Конец декабря 2010 оказался мимолётной передышкой посреди жестокого кранча, во время которого студия отчаянно пыталась закончить Homefront, самую амбициозную попытку издательства THQ отхватить свой кусок от соблазнительно доходного рынка военных шутеров ААА-класса.

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

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

Что же всё-таки можно нарисовать с помощью всего двух треугольников? Квадрат? Фрактал? Полёт сквозь мегатонной мощности взрыв в центре города? Есть ли предел безумию, где заканчивается реальность и начинается явь? Как правильно ухаживать за лучами, чем их кормить и обо что отражать вы узнаете во внезапном продолжении цикла статей про демомейкинг!

Зачастую, создавая less-файлы (что, впрочем, касается и других препроцессоров css), мы гонимся за красотой и элегантностью less-кода, когда как частенько забываем про скомпилированный css-код. Иногда это влечет за собой критичные последствия, когда объем конечного css возрастает в раз, а код становится совершенно нечитаемым.

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

Введение

Деревом называется неориентированный связный граф из N вершин и N-1 ребер. Из любой вершины до любой другой существует ровно один простой путь.
Корнем дерева будет называться такая вершина, от которой задано направление движения по дереву при его обходе.
Наименьшим общим предком двух вершин u и v будет называться такая вершина p, которая лежит на пути из корня и до вершины v, и до вершины u, а также максимально удаленная от него.

Пять дней назад вышел релиз 13.10 «Saucy Salamander». 4 дня назад Nvidia объявила о переходе на светлую сторону начале всесторонней поддержки операционной системы ядра Линукс. А два дня назад Ubuntu отметила свой девятый день рождения. Первая версия дистрибутива Ubuntu 4.10 под кодовым именем «Warty Warthog» вышла в свет 20 октября 2004.

Всего на свет появилось 20 релизов, из них 5 — с длительным периодом поддержки.

Это просто праздничный марафон какой-то… Убунтоводы, поздравляю!

Под катом инфографика

В данном посте я расскажу о наиболее интересных командах, которые могут быть очень полезны при работе в консоли. Однозначных критериев определения какая команда лучше другой — нет, каждый сам для своих условий выбирает лучшее. Я решил построить список команд на основе наиболее рейтинговых приемов работы с консолью от commandlinefu.com, кладовой консольных команд. Результат выполнения одной из таких команд под Linux приведен на картинке. Если заинтересовало, прошу под кат.

Компания Nvidia, крупнейший дизайнер графических чипов, передав часть документации по видеокартам команде nouveau, решила не останавливаться на достигнутом.

На днях, в рамках стратегии по расширению возможностей разработчиков игр, компания представила новую платформу — GameWorks. Платформа направлена на упрощение разработки игр и улучшение качество игрового опыта ПК-геймеров. Создатели игр получат в свое распоряжение библиотеки, документацию и SDK для более чем 300 визуальных эффектов, разработанных Nvidia.

Самое интересное в том, что Тони Тамаси (старший вице-президент Nvidia по контенту и технологиям) подтвердил информацию о доступности инструментов GameWorks и для Linux-платформ. Это произойдет в день официального выхода SteamOS.

When SteamOS ships, we’ll have tools that support SteamOS. — Tony Tamasi, SVP of Content and Technology, NVIDIA

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

Рассмотрим ранее опубликованные решения, затем сделаем обзор методов консоли с помощью перевода недавней статьи Axel Rauschmayer-а, разработчика и консультанта с более чем 15-летним стажем, затем я опубликую некоторые свои решения, которые оказались удачными в процессе эволюции и отладки на ряде проектов.
UPD 2015: обновление таблицы команд до актуального состояния, Github (ru, en; разворачивание на javascript).

Доброго времени суток, уважаемые хабравчане.

Мы, погромпрограммисты, очень часто сталкиваемся с одной и той же проблемой при изучении нового языка X или фреймворка Y — что писать после вступительного туториала Yet Another Hello World? Что-нибудь, что сможет показать какие-то преимущества и недостатки X/Y, но при этом не заняло бы много времени.

Мы с товарищами часто задавались подобным вопросом. В итоге родилась простая мысль — напиши RSS читалку. Тут тебе и работа с сетью, и XML парсер, и БД можно подключить, поглядеть на шаблонизатор. Да мало ли.

Итак, здесь начинается увлекательное путешествие в стек Play Framework 2.2 + Scala + MongoDB на бэкэнде и AngularJS + CoffeeScript на фронтенде.

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

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

Agile движение имеет свой взгляд на спецификации. Наиболее экстремальное крыло выражает свои взгляды так:

В жопу спецификации!

В указанном судебном разбирательстве по обвинению семьи Лопуховых, мы столкнулись с весьма непростой фабулой. Впервые в России осудили людей за использование торрент-трекера и размещение ссылок в Интернете.

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

Нам известно, что указанное дело было возбуждено ангажированными следователями (к слову говоря оба следователя, которые начинали работу над делом к настоящему моменту уволены из следственных органов) с подачи крупнейших транснациональных медиакорпораций, которые являются членами Российского антипиратского общества (РАПО). Так, в 301 докладе Комиссии США по Торговым Аспектам (которая является органом Госдепартамента США) говорится, что «США  выражает одобрение в связи продвижением дела, связанного с уголовным преследованием сайта interfilm.ru».

Я думаю, почти любого Java разработчика когда-то спрашивали на собеседовании: «Какие есть методы у класса Object?»
Меня, по крайней мере, спрашивали неоднократно. И, если в первый раз это было неожиданностью (кажется, забыл про clone), то потом я был уверен, что уж методы Object'а-то я знаю;)

И каково же было мое удивление, когда спустя несколько лет разработки я наткнулся на собственное незнание сигнатуры метода getClass()

Под катом пара слов про Class, .class, .getClass и, собственно, сюрприз, на который я наткнулся.

Здесь нету примеров идеального кода, пяти шагов «как получить сертификат с вероятностью 100%, гарантия». Нету даже фотографий котиков :/

Про язык Go от команды Google слышали, наверное, все. А вот пробовали далеко не все, и очень зря — общение с сусликами Go это море удовольствия, в чем я недавно убедился на собственном опыте.
Начинать знакомство с новым языком забавнее всего на жизненном примере, поэтому я, не долго думая, взял первую попавшуюся задачу “из жизни, самой первостепенной важности”:

Есть в интернете сайт http://vpustotu.ru на котором любой желающий может анонимно высказаться о наболевшем. Все высказывания (в дальнейшем буду называть их “цитатами”) сначала попадают в модерацию (аналог “бездны” башорга), где посетители могут оценить полет мысли и проголосовать за цитату в стиле “Ого!” или “Ерунда!”. На странице модерации (http://vpustotu.ru/moderation/) нам показывают случайную цитату, ссылки голосования и ссылку “Еще”, которая ведет на эту же страницу. Пощелкайте, это все очень просто.

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

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

Таким образом нужна программа, которая:

• Должна последовательно обновлять и парсить (разбирать) страницу, записывая цитату.
• Должна уметь отбрасывать дубликаты.

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

• Должна останавливаться не только по команде, но и по достижению определенного числа “повторов”, например 500!
• Так как это, скорее всего, займет некоторое время: необходимо уметь продолжить “с места на котором остановились” после закрытия.
• Ну и раз уж все-таки это надолго – пусть делает свое грязное дело в несколько потоков. Хорошо-бы в целых 4 потока (или даже 5!).
• И отчитывается об успехах в консоль каждые, скажем, 10 секунд.
• А все эти параметры пускай принимает из аргументов командной строки!

Ну, вроде все понятно. Пусть программа ведет два файла – с цитатами и с некими хешами этих цитат, чтобы не повторяться, и перечитывает файл в начале каждого запуска. Ну а дальше в цикле разбирает страницу, выдергивая все новые и новые откровения, пока не получит ctrl-c по лбу или же не встретит определенное количество повторов. Задача ясна, план есть – поехали!

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

# Весь код в статье написан на языке Python

Основы

Пожалуй, лучшее описание динамики в одно предложение, которое я когда либо слышал:

Динамическое программирование — это когда у нас есть задача, которую непонятно как решать, и мы разбиваем ее на меньшие задачи, которые тоже непонятно как решать. (с) А. Кумок.

Сегодня обнаружил на сайте ОАО «РЖД» весьма занятную ошибку:



Да, в феврале 2013 года у них 29 (!) дней. Хуже всего что наличие дополнительного дня «смещает» все остальные месяцы по дням недели на один день вперёд.

Интересно, что творится с сервисом заказов и с АСУ «Экспресс-3» в целом. Если через пару дней не поправят, то люди, заказывающие билеты на 1 марта будут неприятно удивлены.

Об ошибке написал на ticket@rzd.ru.

UPD: С ticket@rzd.ru довольно оперативно пришел ответ — "Информация передана в ответственное подразделение. Благодарим Вас за проявленную бдительность."

UPD 2 by zotov: на самом деле дни недели при заказе правильные, ошибка, очевидно, в виджете календаря.

UPD 3: Ошибку исправили!