В этой статье мы покажем простой пример поиска на D, однако, вместо традиционно предлагаемого массива в таком алгоритме будет использован диапазон. Данный выбор был продиктован тем, что диапазоны обеспечивают большую гибкость, производительность, а иногда и большую читабельность кода.
Вот пример поиска на D, реализованного с применением диапазонов и некоторого функционала стандартной библиотеки:
import std.range : dropOne, empty, front, isInputRange, takeOne;
import std.traits : isOrderingComparable;
bool search(Range, T)(Range range, T value)
if (isInputRange!Range && is(typeof(range.front) : T) && isOrderingComparable!T)
{
while (!range.empty)
{
auto mid = range.front;
if (mid == value)
{
return true;
}
else if (mid < value)
{
range = range.dropOne;
}
else
{
range = range.takeOne;
}
if ((range.dropOne.empty) && (mid != value))
{
return false;
}
}
return range.front == value;
}Данный код реализует алгоритм поиска на диапазонах, где под диапазоном понимается упорядоченный диапазон данных, т.е. объект, который можно перебирать поэлементно, к примеру, таким объектом является диапазон или список, или выход любого алгоритма D. Под алгоритмом мы здесь понимаем не сам программный код, а абстракцию D, которая работает с диапазонами, и возвращает диапазон (в частности, функция поиска также является алгоритмом в терминологии D, но диапазон не возвращает).
На каждой итерации цикла while происходит следующее:
- Получаем средний элемент диапазона mid с помощью вызова функции front, которая возвращает первый элемент диапазона.
- Если mid равен искомому значению value, то функция возвращает true, поскольку искомое значение найдено.
- Если mid меньше value, то функция продолжает поиск в правой половине диапазона, отбрасывая левую часть с помощью вызова функции dropOne.
- Если mid больше value, то функция продолжает поиск в левой части диапазона, отбрасывая правую часть с помощью вызова функции takeOne.
- Если диапазон состоит из одного элемента и этот элемент не равен искомому значению, то функция возвращает false, поскольку искомое значение не найдено.
- Цикл продолжается до тех пор, пока диапазон не станет пустым. Если диапазон пустой, то искомое значение не найдено, и функция возвращает false. Если же диапазон не пустой, то на последней итерации цикла проверяется, равен ли последний элемент диапазона искомому значению. Если он равен, то функция возвращает true, в противном случае, функция возвращает false.
Также при реализации данной функции были применены шаблонные типы Range и T, которые соответствуют самому диапазону и типу искомого значения. На эти типы накладывается ряд ограничений по возможным их вариантам, в частности, isInputRange проверяет то, что диапазон принадлежит к так называемым диапазонам ввода (InputRange). Принадлежность к этому типу означает некий общий интерфейс для диапазонов, который заключается в наличии в них реализаций следующих методов: front, empty и popFront, через которые работают алгоритмы dropOne и takeOne. Также проверяем то, что тип первого элемента диапазона, как минимум, можно привести к типу исходного значения, чтобы можно было выполнить сравнение. Поскольку операции сравнения реализует не все типы данных, а лишь те для которых был определен метод opCmp, то добавлена проверка isOrderingComparable. Эта проверка срабатывает только тогда, когда определены операции сравнения через opCmp, которые нужны для работы операторов <, != и т.п.
Испытания можно провести, например, следующим образом:
import std.algorithm : map;
import std.stdio;
void main()
{
int[] arr = [1, 3, 5, 7, 9];
bool found = search(arr[], 5);
writeln("Found 5: ", found); // Output: Found 5: true
found = search(arr.map!(a => a), -1);
writeln("Found -1: ", found); // Output: Found 6: false
}Алгоритм получился достаточно простой и интересный, по сравнению с классическим решением, однако содержит потенциал к улучшению. К примеру, можно учесть, что не все типы поддаются сравнению и ввести в алгоритм параметр функции, которая будет сравнивать значения и тем самым сделать еще большое обобщение алгоритма, однако, это мы оставляем как упражнение для читателя.
Этот рецепт написан по большей части для того, чтобы показать функционал и удобство некоторой части стандартной библиотеки D, связанной с диапазонами.
