Довольно часто встречается задача поиска уникальных элементов в массивах или каких-то иных последовательностях данных со схожим интерфейсом доступа и казалось бы тут не должно быть проблем, особенно, если учесть тот факт, что в Phobos в модуле std.algorithm есть такая замечательная вещь, как uniq, но…
Если взять достаточно простой пример, то подвох будет найден почти сразу:
import std.algorithm : uniq;
import std.stdio : writeln;
void main()
{
int[] a = [1,2,3,4,1,2,1,3,2,4,1,4,2,2,4,5,2,4,1,4];
writeln(uniq!”a == b”(a));
}
Результат, который выдает этот алгоритм (в терминах D, функция манипулирующая диапазонами, т.е структурами данных с английским названием ranges, называется алгоритмом. Поскольку функция uniq принимает диапазон, то это, по определению, алгоритм), несколько сбивает с толку:
[1, 2, 3, 4, 1, 2, 1, 3, 2, 4, 1, 4, 2, 4, 5, 2, 4, 1, 4]
Такое ощущение, что uniq отработала впустую…
Но если взять последовательность из документации, то все проходит, так как и должно: получаем правильную последовательность из уникальных элементов и неутешительный вывод – встроенная функция с предикатом равенства (хотя выражение ”a == b” можно было опустить и вызвать функцию вот так: uniq(a). Оба вызова эквиваленты, поскольку во втором вызове функции uniq выражение ”a == b” будет неявно подставлено при компиляции, что указано в документации к стандартной библиотеки прямо в сигнатуре функции.) сможет дать уникальные элементы только если не уникальные элементы идут друг за другом.
Что делать ?
Можно, конечно, написать свою функции профильтровки и передать ее как предикат в функцию uniq, но есть идея гораздо интереснее и полезнее – можно написать свою версию этого алгоритма, превратив его в обычную, хотя и параметризованную функцию.
Идея алгоритма до безобразия проста (но иногда и неэффективна): создается пустой массив-аккумулятор типа Т, в который и будут накапливаться уникальные элементы, затем по массиву, который нужно обработать на получение уникальных элементов, организуется проход с помощью цикла просмотра. Внутри цикла просмотра постоянно проверяется условие наличия элемента из массива для обработки в массиве-аккумуляторе, и если, элемент не был найден, то он добавляется в массив-аккумулятор. Таким образом, необходимо реализовать две вещи: условие наличия некоторого элемента в массиве (иными словами, нужно произвести простой поиск в массиве) и цикл прохода по массиву – и при том, все это надо реализовать, используя параметризованные функции.
У меня получилось примерно так:
import std.algorithm;
import std.array;
import std.functional;
/* уникальные элементы массива */
T[] uniqueElements(alias pred = "a == b", T)(T[] x) if (is(typeof(binaryFun!pred(x.front, x.front)) == bool))
{
// содержит ли массив некоторый элемент ?
bool contain(alias pred, T)(T[] x, T a)
{
foreach (b; x)
{
if (mixin(pred))
{
return true;
}
}
return false;
}
T[] arr;
foreach (elem; x)
{
if (!(contain!pred(arr, elem)))
{
arr ~= elem;
}
}
return arr;
}
Работает все это достаточно просто: вначале функции мы определяем два обобщенных аргумента: pred – предикат (логическая функция, признак) уникальности элемента и Т – некоторый обобщенный тип, на месте которого может оказаться любой из допустимых языком программирования D тип. Применение alias в сигнатуре функции – это довольно часто используемый прием среди программистов D и здесь это используется в самом обычном виде: alias используется для передачи некоторого выражения или оператора внутрь обобщенной функции.
В самой сигнатуре функции, помимо двух обобщенных типов, присутствует кое-что интересное, а именно, ограничение сигнатуры (signature constraint), которое в данном случае записано с помощью выражения if (is(typeof(binaryFun!pred(x.front, x.front)) == bool)). Шаблон binaryFun делает довольно интересную вещь: он создает функцию двух аргументов по ее строковому описанию, а в нашем случае, binaryFun конструирует функцию-предикат, которая будет использована для отсеивания уникальных элементов.
Но в самой этой функции есть один весьма необычный момент – дело в том, что функция создается из одного и того же элемента (это аргумент x.front) ! Подобные выражения (вплоть до такого: x == x) довольно часто встречаются в ограничениях сигнатуры шаблонов и ничуть не противоречат логике (и не являются бессмысленными), но нужно понимать их (в этих случаях) иначе, чем обычно: выражения такого вида служат для проверки некоторого выражения на его компилируемость (звучит немного странно, но попробую объяснить: выражение binaryFun!pred(x.front, x.front)) скомпилируется только в том случае, если величины x.front, получаемые из некоторой структуры, сравнимы между собой. И в этом случае, результатом такого выражения будет true, т.е логический тип и таким образом, мы узнаем, что выражение успешно скомпилируется и что оно корректно) : если выражение на этапе компиляции проходит эту проверку (т.е is сопоставил тип результата этого выражения с логическим типом и пришел к выводу, что это одно и то же), то функция содержащая такое ограничение сигнатуры успешно скомпилируется и будет корректно работать (что мы и доказали на этапе компиляции).
Не уверен, что объяснил все четко и правильно, однако, к таким вещам нужно привыкать (и подробное объяснение такого рода случаев есть в книге «Язык программирования D» Андрея Александреску). Остальное, думаю, итак понятно из кода.
Однако, некоторое время подумав над функцией выделения уникальных элементов, я пришел к выводу, что ее реализация не сильно эффективна и слишком наивна (я четко был уверен в том, что в стандартной библиотеке есть какое-нибудь средство для отслеживания наличия каких-либо элементов в массиве, ну а также был уверен в том, что такого рода функции так как описано никогда не пишутся).
И тогда мне в голову пришел вот такой вариант (не сильно лучше первого, но более аккуратный):
import std.algorithm;
import std.array;
import std.functional;
/* уникальные элементы массива , версия 2.0 */
T[] uniqueElements2(alias pred = "a == b", T)(T[] x) if (is(typeof(binaryFun!pred(x.front, x.front)) == bool))
{
T[] arr;
alias condition = canFind!pred;
foreach (elem; x)
{
if (!(condition(arr, elem)))
{
arr ~= elem;
}
}
return arr;
}
Скажите, код стал чище и проще для понимания?
Надеюсь, опыт реализации, описанной в этой статье функции извлечения уникальных элементов из массива, окажется нужным и полезным.
P.S: Применять эти функции очень просто: uniqueElements!»a == b»(a) или uniqueElements(a).