Готовый перевод "D"iving Into the D Programming Language / Погружение в язык Ди: 1.4.2 Array Slicing. Type-Generic Functions. Unit Tests

Срез массива - это мощный инструмент, позволяющий работать с частью массива без реального копирования данных.

Для примера, напишем функцию binarySearch, используя одноимённый алгоритм: по отсортированному массиву и значению, binarySearch определит, входит ли это значение в массив.

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

Давайте немного повысим наши амбиции, написав binarySearch, которая работает не только с целыми, а вообще с любыми величинами, которые можно сравнить на "меньше чем".

Оказывается, это не так сложно! Вот как выглядит обобщённая версия binarySearch:

import std.array;
bool binarySearch(T)(T[] input, T value) {
while (!input.empty) {
auto i = input.length / 2;
auto mid = input[i];
if (mid > value) input = input[0 .. i];
else if (mid < value) input = input[i + 1 . $];
else return true;
}
return false;
}
unittest {
assert(binarySearch([ 1, 3, 6, 7, 9, 15 ], 6));
assert(!binarySearch([ 1, 3, 6, 7, 9, 15 ], 5));
}

Языковая запись (T) в сигнатуре binarySearch вводит параметр-тип T.

Далее этот параметр-тип может использоваться в списке обычных параметров функции.

binarySearch выведет тип T из переданных ей фактических аргуметов. Если вы хотите указать тип явно (например, для большей страховки), это можно сделать так:

assert(binarySearch!(int)([ 1, 3, 6, 7, 9, 15 ], 6));

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

Сначала идёт аргумент времени компиляции, заключённый в !(...), а затем - аргументы времени выполнения в (...).

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

Если вы знакомы с обобщениями в Java, C#, или C++, вы определённо заметили, что Ди явно уходит от применения угловых скобок для указания типа-обобщения.

Это было намеренное решение, направленное на избежание проблем, которые выявила практика в С++: усложнившийся парсинг, мириады специальных правил, дополнительные проверки и неочевидный синтаксис.

Корень проблемы в том, что < и > по-сути - операторы сравнения, которые в свою очередь сами могут быть внутри себя же как разделители типа-обобщения.

Такие разделители очень сложно разбивать на пары. Java и C# было легче - они просто запретили выражения внутри <>, но тем самым ограничив будущее развитие в угоду сомнительному преимуществу.

Ди допускает выражения в аргументе-типе и упрощает жизнь программиста и компилятора, расширяя оператор ! до бинарного и используя классические скобки, (которым (я уверен) вы всегда правильно находите пару).

Стоит так же упомянуть про использование auto в реализации binarySearch - типы 'i' и 'mid' были выведены из их инициализирующих выражений.

Следуя хорошим практикам, binarySearch тоже имеет модуль тестирования. Такие модули пишут как блок, начинающийся с ключевого слова unittest. Один файл может содержать множество таких блоков и вы сами знаете - слишком много тестов не бывает.

Для выполнения тестов нужно передать компилятору флаг "-unittest". Хотя тестовые модули и не поражают воображение, они являются неотъемлемой частью хорошего стиля, особено когда их так легко вставлять в код.

Также, если вы мыслите высокоуровнево и предпочитаете видеть сначала тесты, а потом реализацию, нет проблем - вы можете спокойно переместить тест в любое место файла - все символы кода будут доступны.

Выражение input[a .. b] возвращает срез массива от индекса 'a' до индекса 'b', не включая последний. Если 'a' и 'b' равны, возвратится пустой срез, а если 'a' больше 'b', то выпадет исключение.

Срез не вызывает распределения памяти - это просто новое имя для участка массива. В индексе массива или его срезе символ $ означает длину массива, так что "input[0 .. $]" - то же самое, что и просто "input".

Повторюсь: хотя и может показаться, что в binarySearch происходит множество операций с массивами, ни единого байта не распределяется - все операции идут над одним и тем же массивом.

Безусловно, наша реализация хуже традиционной, манипулирующей индексами, но зато она намного понятнее за счёт меньшего количества состояний.

Кстати о состояниях: давайте напишем рекурсивный вариант, который не переприсваивает индекс вообще:

import std.array;
bool binarySearch(T)(T[] input, T value) {
if (input.empty) return false;
auto i = input.length / 2;
auto mid = input[i];
if (mid > value) return binarySearch(input[0 i]);
if (mid < value) return binarySearch(input[i + 1 $]);
return true;
}

Рекурсивная реализация явно проще и лаконичнее, чем итеративная.

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

Внимание! Этот перевод, возможно, ещё не готов.
Его статус: идёт перевод

Переведено на Нотабеноиде
http://notabenoid.org/book/42515/164385

Переводчики: thornik, lovermann, akkuraten