Поиск на диапазонах

В этой статье мы покажем простой пример поиска на 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, связанной с диапазонами.

Добавить комментарий