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

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

akkuraten 05.08.16 в 12:02

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

thornik 04.03.18 в 14:15

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

thornik 04.03.18 в 14:18

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

thornik 04.03.18 в 14:19

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

thornik 04.03.18 в 14:20

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));
}

lovermann 27.02.17 в 18:23

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

thornik 04.03.18 в 14:21

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

thornik 04.03.18 в 14:22

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

thornik 04.03.18 в 14:24

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

lovermann 27.02.17 в 18:23

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

thornik 04.03.18 в 14:27

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

thornik 04.03.18 в 14:28

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

thornik 04.03.18 в 14:31

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

thornik 04.03.18 в 14:34

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

thornik 04.03.18 в 14:41

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

thornik 04.03.18 в 14:44

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

thornik 04.03.18 в 14:46

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

thornik 04.03.18 в 14:50

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

thornik 04.03.18 в 14:53

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

thornik 04.03.18 в 14:56

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

thornik 04.03.18 в 15:01

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

thornik 04.03.18 в 15:04

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

thornik 04.03.18 в 15:07

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

thornik 04.03.18 в 15:09

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

thornik 04.03.18 в 15:11

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

thornik 04.03.18 в 15:13

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

thornik 04.03.18 в 15:14

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;
}

lovermann 27.02.17 в 18:26

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

thornik 04.03.18 в 15:15

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

thornik 04.03.18 в 15:19