Cache-Conscious Binary Search

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/dotnet/cache-conscious-binary-search/.

---

Рассмотрим простую задачу: есть некоторый достаточно большой неизменный набор чисел, к нему осуществляется множество запросов на наличие некоторого числа в этом наборе, необходимо максимально быстро эти запросы обрабатывать. Одно из классических решений заключается в формировании отсортированного массива и обработке запросов через бинарный поиск. Но можно ли добиться более высокой производительности, чем в классической реализации? В этой статье мне хотелось бы рассказать про Cache-Conscious Binary Search. В данном алгоритме предлагается переупорядочить элементы массива таким образом, чтобы использование кэша процессора происходило максимально эффективно.

Переписываем список коммитеров в Git

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/git/rewrite-commiter-list/.

---

Иногда возникает потребность переписать коммитеров в Git-репозитории. Задача достаточно редкая, но иногда всё-таки приходится ей заниматься. Давайте разберёмся в ситуации подробней. Прежде всего, взглянем на текущий список коммитеров:

$ git log --pretty=format:"%an <%aE>" | sort -u

Допустим, мы получили следующий список:

Ivan <ivan@gmail.com>
Ivan <ivan.ivanov@gmail.com>
Ivan <ivan-ivan@gmail.com>
Ivan Ivanov <ivan.ivanov@gmail.com>
Vanya Ivanov <ivan.ivanov@gmail.com>
Vanya <ivan.ivanov@gmail.com>

Наблюдаем следующую проблему: некий Иван Иванов делал коммиты, указывая каждый раз разную информацию об имени пользователя и почтовом адресе. Для начала нужно дать по рукам Ивану и сказать, чтобы больше так не делал. Лучше всего использовать для всех коммитов одинаковую учётную информацию (например, Ivan Ivanov <ivan.ivanov@gmail.com>). Проблема может встать особенно остро, если в проекте используются дополнительные сервисы, которые работают с репозиторием (code review system, build server и т.п.). Ну, а пока Иван размышляет над своим поведением, мы займёмся переписыванием истории.

Jon Skeet's Quiz

Блог переехал. Актуальная версия поста находится по адресу: http://aakinshin.net/ru/blog/dotnet/jon-skeet-quiz/.

---

Однажды Джона Скита попросили сформулировать три интересных вопроса на знание C#. Он спросил следующее (оригинал вопросника, перевод статьи):

Q1. Вызов какого конструктора можно использовать, чтобы следующий код вывел True (хотя бы в реализации Microsoft.NET)?

object x = new /* fill in code here */;
object y = new /* fill in code here */;
Console.WriteLine(x == y);

Учтите, что это просто вызов конструктора, вы не можете поменять тип переменных.

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

void Foo()
{
    EvilMethod<string>();
    EvilMethod<int>();
    EvilMethod<int?>();
}

Q3. Как заставить следующий код выбросить исключение во второй строчке с помощью локальной переменной (без хитрого изменения её значения)?

string text = x.ToString(); // No exception
Type type = x.GetType(); // Bang!

Вопросы показались мне интересными, поэтому я решил обсудить их решения.