Это, пожалуй, самый болезненный отчет об ошибке, который я когда-либо читал. Он красочно описывает шаги, которые привели к потере 465 миллионов долларов компанией Knight Capital в связи с ошибкой программного обеспечения, проявившейся в прошлом году и обанкротившей компанию.

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

Вступление

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

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

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

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

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

Я надеюсь, что эта статья станет началом цикла заметок о lock-free структурах данных. Я хочу поделиться с хабрасообществом своим опытом, наблюдениям и размышлениями о том, что такое lock-free структуры данных, как их реализовывать, подходят ли концепции контейнеров стандартной библиотеки STL к lock-free контейнерам, и когда стоит (и стоит ли вообще) применять lock-free структуры данных.

Сегодня в реестр запрещенных сайтов был добавлен крупнейший мировой порно-ресурс redtube.com (96-й по популярности сайт сети).

Этот случай примечателен тем, что по информации от сайта antizapret.info, причиной блокировки стал ролик с изображением несовершеннолетних персонажей в порнографическом мультфильме (хентай). До конца не ясно, как определялся возраст нарисованных актеров и какие последствия это принесет другим художественным материалам, однако не так давно сообщалось о том, что Роскомнадзор собирается блокировать подобный контент.

На данный момент сайт уже заблокирован некоторыми провайдерами.

Использовать шаблонные шаблонные параметры С++ довольно сложно. Хочу продемонстрировать силу boost::mpl и показать трюк, позволяющий описывать шаблоны, полностью отказавшись от шаблонных шаблонных параметров.
Продемонстрирую проблему. Есть класс, принимающий тип объекта и тип контейнера для этого объекта.

template <typename T, typename Container>
struct A
{
  typedef Container<T> type;
};

Так писать нельзя, вы должны использовать шаблонные шаблонные параметры, чтобы указать, что Container сам по себе является шаблоном.

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

Я расскажу о следующем:

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

Оригинальный pdf (на английском)
Переведённый pdf (на русском)

Abstract: использование cgroups для ограничения прожорливости компилятора по процессору и диску.

Лирика

Дано:
программист 1шт,
ноутбук с ноутбучным диском на 5200 rpm — 1шт,
исходных файлов на хаскеле 300 шт
Файлы coffee-script (будущий JS) — 300 шт
время компиляции — 40 минут.

Задача: компилировать в бэкграунде не ставя всю систему в состояние «ад и погибель». Можно даже ценой увеличения времени сборки до 50-60 минут.

Решение?

cgroups

Эта статья рассказывает о времени выполнения и о расходе памяти большинства алгоритмов используемых в информатике. В прошлом, когда я готовился к прохождению собеседования я потратил много времени исследуя интернет для поиска информации о лучшем, среднем и худшем случае работы алгоритмов поиска и сортировки, чтобы заданный вопрос на собеседовании не поставил меня в тупик. За последние несколько лет я проходил интервью в нескольких стартапах из Силиконовой долины, а также в некоторых крупных компаниях таких как Yahoo, eBay, LinkedIn и Google и каждый раз, когда я готовился к интервью, я подумал: «Почему никто не создал хорошую шпаргалку по асимптотической сложности алгоритмов? ». Чтобы сохранить ваше время я создал такую шпаргалку. Наслаждайтесь!

Просто хотел Вас предупредить: С++14 не будет обратно совместим с C++11 в одном аспекте constexpr функций.

В С++11, если Вы определите constexpr функцию-член, то она неявно получит спецификатор const:

// C++11
struct NonNegative
{
  int i;
  constexpr int const& get() /*const*/ { return i; }
  int& get() { return i; }
};

Первое объявление функции get получит спецификатор const, даже если мы не укажем это явно. Следовательно, эти две функции являются перегруженными: const и не-const версии.

В С++14 это будет уже не так: оба объявления будут определять одиннаковую, не-const версию функции-члена с различающимися возвращаемыми значениями — это приведет к ошибке компиляции. Если Вы уже начали использовать constexpr функции и надеетесь на неявный спецификатор const, то я советую Вам начать добавлять его явно, чтобы Ваш код продолжал компилироваться, если Вы решите перейти на компиляторы С++14.