В этот раз мы решили вновь взяться за перевод статьи про D. И если быть до конца честными, то идея перевести эту статью возникла у нас достаточно давно и импульс для публикации перевода возник у нас весьма внезапно, когда один из авторов блога читал Habr и встретил отсылку к той статье, которую мы бы хотели сегодня представить.
Итак, в гостях у нас сегодня автор статьи под названием «Beautiful binary search in D» за авторством Алекса Мускара, которая была опубликована 18 февраля 2023 года в его блоге muscar.eu. Если вы готовы то добро пожаловать под кат этой статьи. Статью мы постарались перевести максимально близко к оригиналу.
28 февраля 2023 года. Пользователь @tgehr опубликовал версию алгоритма с нулевой базой. Он также указал на то, что мой первоначальный код передавал статические массивы по значению. Я обновил код в статье, чтобы использовать ref для параметров массива, а также оператор возведения в степень D, ^^ . Версия @tgehr также возвращает первую позицию элемента, если есть несколько экземпляров, в то время как тот, который представлен в этой статье, возвращает последний. Благодарю за рекомендации!
18 февраля 2023 года. Пользователь @schveiguy указал на то, что первоначальный подход к определению размера статического массива был чрезмерно сложным. Я обновил код, чтобы включить его предложение. Спасибо!
Недавно, когда я читал «Написание эффективных программ«, я наткнулся на прекрасную вариацию бинарного поиска и его реализацию. В этой статье я буду использовать возможности метапрограммирования D для реализации обобщенной версии алгоритма.
Я буду предполагать, что вы знакомы с бинарным поиском и его наиболее распространенной реализацией — методом бисекции с использованием двух указателей.
Красивый алгоритм
Существует множество способов реализации бинарного поиска. Самым распространенным, вероятно, является «бисекционный поиск», где мы отслеживаем подинтервалы с помощью двух указателей, один из которых движется слева направо, а другой — справа налево.
Другой вариант — «равномерный поиск», где вместо использования двух указателей мы используем только один указатель и «скорость изменения», то есть начало и размер подинтервалов. Это более тонкий вариант, чем бисекционный поиск, который кстати, также не является тривиальным.
Как выразился Кнут:
«Это возможно, но только если к деталям уделяется крайне внимание, […]. Более простые подходы обречены на провал.»
С другой стороны, равномерный поиск имеет свои преимущества. Одним из них является то, что скорости изменения могут быть предварительно рассчитаны и сохранены в побочной таблице. Если мы правильно рассчитываем скорость изменения — что является тонкой частью — алгоритм поиска проще, чем его аналог с использованием двух указателей.
Одной из вариаций равномерного поиска является алгоритм Шара, который устраняет побочную таблицу и использует размеры интервалов равных степени двойки.
Он начинается с сравнения ключа, который мы ищем, K, с Ki, где i = 2k, k = ⌋lgN⌊. Если K < Ki, то размеры интервалов равны 2k−1, 2k−2, …, 1, 0. Но если K > Ki, мы устанавливаем i = N−2l+1, где l = ⌈lg(N−2k+1)⌉, корректируем указатель интервала, и размеры интервалов равны 2l−1, 2l−2, …, 1, 0.
Алгоритм Шара определяет позицию записи с ключом K бит за битом. Каждый тест добавляет еще один бит. Нам нужен еще один тест, после того, как мы определили все биты, чтобы увидеть, находится ли запись в таблице на самом деле или нет.
Красивая реализация
Бентли предоставляет прекрасную версию алгоритма Шара в своей книге. Код работает для таблиц с 1000 элементами. Код в книге написан на Pascal, но транслированный на D выглядит так:
int bsearch1000(ref int[1001] xs, int x)
{
auto i = 0;
if (xs[512] <= x) { i = 1000 - 512 + 1; }
if (xs[i + 256] <= x) { i += 256; }
if (xs[i + 128] <= x) { i += 128; }
if (xs[i + 64] <= x) { i += 64; }
if (xs[i + 32] <= x) { i += 32; }
if (xs[i + 16] <= x) { i += 16; }
if (xs[i + 8] <= x) { i += 8; }
if (xs[i + 4] <= x) { i += 4; }
if (xs[i + 2] <= x) { i += 2; }
if (xs[i + 1] <= x) { i += 1; }
if (xs[i] == x) return i;
else return 0;
}Здесь происходит несколько вещей. Во-первых, нечетный размер массива, 1001. Массивы Pascal начинаются с единицы. D следует за C и использует нумерацию элементов массива начиная с нуля. В этом случае мы просто игнорируем xs[0]. Кстати, это ошибка. Бентли признает это, но не предоставляет исправления, поскольку считает, что это отвлекает от изложения. Мы можем исправить это, установив i равным 1 в начале, и внести соответствующие корректировки в код. Это усложнит код до некоторой степени. Другой способ исправления — явно проверить, является ли i равным 0 в последнем тесте.
Во-вторых, код полностью развертывает цикл поиска. Это возможно только потому, что мы заранее знаем размер таблицы. Код может быть настроен под другие размеры таблиц по мере необходимости.
То, что делает этот код красивым, это то, что он почти такой же эффективный, каким он мог бы быть. Он также является равномерным и относительно простым для понимания, если вы знакомы с алгоритмом Шара. Это практически дословное воплощение алгоритма, специально подогнанное для этого конкретного размера таблицы.
Красивое метапрограммирование
Хотя код Бентли довольно красивый, его несколько трудно настраивать под другие размеры таблиц, и легко ошибиться при вычислении начального значения i. Код сильно повторяется и очень равномерен. Это является сильным намеком на то, что мы можем автоматизировать его написание.
Здесь на помощь приходят мощные возможности метапрограммирования D. Если мы можем определить размер таблицы на этапе компиляции, то в принципе мы можем автоматически генерировать код для развернутого цикла.
Как оказалось, мы можем определить, имеем ли дело со статическим массивом, и получить его размер во время компиляции. Прежде чем показать вам код, давайте разобъем задачу на части. Алгоритм состоит из трех частей:
1.Начальный тест, сравнивающий ключ поиска K с Ki для i = 2k, k = ⌋lgN⌊;
2.Определение последовательных битов позиции кандидата, через перебор по степеням двойки; и
3.Проверка на то, нашли ли мы элемент, который мы ищем.
Начнем с сигнатуры функции:
auto bsearch(T, size_t n)(ref T[n] xs, T x)
{Это действительно круто. Я не ожидал, что компилятор D может вычислить n — в C++ это не работает — но здесь он сработал прекрасно. T — это тип элемента массива, а n — это длина массива. Это статическое значение, доступное на этапе компиляции.
Затем мы определяем k, степень двойки, с которой начинаем поиск:
enum k = iflog2(n - 1);
iflog2 означает целый логарифм по основанию 2. Это обычная функция D, но ее можно вычислить на этапе компиляции, если ее вызвать с значением времени компиляции, что и делаем здесь. Использование enum очень похоже на C++. Поскольку наш массив начинается с одного, мы вычитаем единицу из его длины.
Параметры функции — это таблица xs и ключ x, который мы ищем. Мы передаем xs по ссылке, чтобы не передавать всю таблицу при вызове basearch.
Начальный тест — это просто код проверки в алгоритме Шара:
auto p = 0;
if (xs[2 ^^ k] <= x) p = (n - 1) - 2 ^^ k + 1;Мы отслеживаем позицию кандидата в переменной p.
А теперь самое интересное, генерация тестов степени двойки:
static foreach_reverse (int i; 0 .. k)
{
if (xs[p + 2 ^^ i] <= x) p += 2 ^^ i;
}Этот код замечательно короткий благодаря регулярности проблемы, которую мы упоминали ранее, и мощным возможностям метапрограммирования D. Статический foreach вычисляется на этапе компиляции. И самое главное, он не вводит новой области видимости. Код внутри просто «вставляется» в код окружающей функции. Фактически, этот фрагмент генерирует серию операторов if, эквивалентных bsearch1000. Мы используем foreach_reverse для перебора степеней двойки от k до 1 — диапазон от 0 .. k не включает k, и мы перебираем его в обратном порядке. Выбор foreach_reverse в качестве ключевого слова несколько неудачен. Может быть, есть более чистый способ достижения того же результата, но я не использую D регулярно, поэтому это то, что я придумал :^).
После того, как мы определили все биты позиции кандидата p, нам остается только проверить, находится ли элемент, который мы ищем, на этой позиции.
if (p > 0 && xs[p] == x) return p;
return 0;
}И с этим мы закончили. Если мы проверим сгенерированный для bsearch1000 и bsearch код в compiler explorer, мы увидим, что он практически идентичен. Компилятор D даже встроил для нас константы времени компиляции.
Бонус: сделаем его действительно общим
Одним из недостатков нашего решения является то, что оно работает только для статических массивов. Было бы здорово, если бы мы могли определить, что имеем дело с динамическим массивом, и перейти к другому алгоритму.
Вы, вероятно, не удивитесь, узнав, что мы можем это сделать — в противном случае я бы не писал этот раздел :^).
Все реализация немного антиклиматична, на самом деле. Мы можем использовать функциональное перегрузку и объявить версию bsearch, которая принимает параметр динамического массива:
auto bsearch(T)(T[] xs, T x)
{
writeln("dynamic array: ", xs);
// ...
return 0;
}Компилятор выберет правильную перегрузку на основе аргументов, с которыми мы вызываем функцию.
Выводы
Алгоритм Шара — красивая вариация бинарного поиска. Если мы знаем размер таблицы заранее, мы можем написать эффективный алгоритм бинарного поиска с его использованием.
Реализация Бентли также красива, потому что она выжимает каждый бит производительности из кода. Код не делает больше, чем должен, и в нем есть своего рода красота дзэн.
Возможности метапрограммирования D позволили нам взять красивый код Бентли и сделать его более общим. Мы можем генерировать код для любого размера таблицы, если мы знаем его на этапе компиляции. В противном случае мы переходим к алгоритму, который может работать с динамическими массивами. Андрей Александреску называет эту технику «Проектирование путем интроспекции» (Design by Introspection, DbI).
D — это интересный язык программирования. Он блестает в этом типе задач, где можно использовать метапрограммированиена всю мощь. Я не знаю ни одного другого языка, в котором эту проблему можно было бы выразить столь же чисто, за исключением, возможно, Common Lisp. Мне было бы любопытно увидеть решение на Rust (который имеет мощную систему макросов) и Zig (о котором я читал, что он также имеет сильную поддержку метапрограммирования). Оказывается, кто-то реализовал алгоритм на Zig…
