std.algorithm.iteration

Переместиться к: cache · cacheBidirectional · chunkBy · cumulativeFold · each · filter · filterBidirectional · fold · group · Group · joiner · map · permutations · Permutations · reduce · splitter · sum · uniq

Это подмодуль std.algorithm. Он содержит типовые итерационные алгоритмы.

Шпаргалка
Имя функции	Описание
cache	Eagerly evaluates and caches another range's front. Жадно вычисляет и кеширует front в другом диапазоне.
cacheBidirectional	Тоже, что и выше, но также предоставляет back и popBack.
chunkBy	chunkBy!((a,b) => a[1] == b[1])([[1, 1], [1, 2], [2, 2], [2, 1]]) возвращает диапазон, содержащий 3 поддиапазона: первый с [1, 1]; второй с элементами [1, 2] и [2, 2]; и третий с [2, 1].
cumulativeFold	cumulativeFold!((a, b) => a + b)([1, 2, 3, 4]) возвращает лениво-вычисляемый диапазон, содержащий последовательно сведённые (reduced) значения 1, 3, 6, 10.
each	each!writeln([1, 2, 3]) жадно печатает числа 1, 2 и 3 на своих собственных строках.
filter	filter!(a => a > 0)([1, -1, 2, 0, -3]) итерирует элементы 1 и 2.
filterBidirectional	Аналогично filter, но также предоставляет back и popBack при небольшом увеличении стоимости.
fold	fold!((a, b) => a + b)([1, 2, 3, 4]) возвращает 10.
group	group([5, 2, 2, 3, 3]) возвращает диапазон, содержащий кортежи tuple(5, 1), tuple(2, 2), и tuple(3, 2).
joiner	joiner(["hello", "world!"], "; ") возвращает диапазон, который итерирует над символами "hello; world!". Новой строки не создаётся – итерирование ведётся по существующим входам.
map	map!(a => a * 2)([1, 2, 3]) лениво возвращает диапазон с числами 2, 4, 6.
permutations	Лениво вычисляет все перестановки, используя Heap's algorithm.
reduce	reduce!((a, b) => a + b)([1, 2, 3, 4]) возвращает 10. Это старая реализация fold.
splitter	Лениво делит диапазон по разделителю.
sum	Тоже, что и fold, но специализируется на достоверном суммировании.
uniq	Итерирует над уникальными элементами в диапазоне, который считается отсортированным.

Лицензия:

Boost License 1.0.

Авторы:

Andrei Alexandrescu

Исходный код: std/algorithm/iteration.d

auto cache(Range)(Range range) if (isInputRange!Range); auto cacheBidirectional(Range)(Range range) if (isBidirectionalRange!Range);

cache жадно считает front диапазона range на каждой конструкции или вызове popFront, чтобы сохранить результат в кеше. Затем, при вызове front, непосредственно возвращается результат, а не пересчитывается.

Это может быть полезной функцией для помещения в цепь, после функций с дорогостоящими вычислениями, как ленивая альтернатива для std.array.array. В частности, можно разместить после вызова map, или перед вызовом filter.

cache может предоставить двунаправленную итерацию при необходимости, но так как это происходит при повышенной стоимости, её надо явно запросить через вызов cacheBidirectional. Кроме того, двунаправленный кеш будет считать "центральный" элемент дважды, когда только один элемент останется в диапазоне.

cache не предоставляет примитивы произвольного доступа, так как cache не смог бы кэшировать случайный доступ. Если Range предоставляет примитивы выделения среза, тогда cache предоставит те же примитивы среза, но hasSlicing!Cache не вернёт true (так как признак std.range.primitives.hasSlicing также удостоверяется в наличии произвольного доступа).

Параметры:

Range range входной диапазон

Возвращает:

входной диапазон с кешируемыми величинами диапазона range

Примеры:

import std.algorithm.comparison : equal;
import std.stdio, std.range;
import std.typecons : tuple;

ulong counter = 0;
double fun(int x)
{
    ++counter;
    // http://en.wikipedia.org/wiki/Quartic_function
    return ( (x + 4.0) * (x + 1.0) * (x - 1.0) * (x - 3.0) ) / 14.0 + 0.5;
}
// Без кеша, с массивом (жадным)
auto result1 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
                         .filter!(a => a[1] < 0)()
                         .map!(a => a[0])()
                         .array();

// значения x, при которых y отрицателен:
assert(equal(result1, [-3, -2, 2]));

// Проверяем, сколько раз вычислялась fun.
// Столько же раз, сколько элементов в источнике и в результате вместе.
assert(counter == iota(-4, 5).length + result1.length);

counter = 0;
// Без массива, с кэшем (лениво)
auto result2 = iota(-4, 5).map!(a =>tuple(a, fun(a)))()
                         .cache()
                         .filter!(a => a[1] < 0)()
                         .map!(a => a[0])();

// значения x, при которых y отрицателен:
assert(equal(result2, [-3, -2, 2]));

// Проверяем, сколько раз вычислялась fun.
// Только столько, сколько элементов в источнике.
assert(counter == iota(-4, 5).length);

Примеры:

Подсказка: cache жаден при вычислении элементов. Если вызов front на лежащем в основе диапазоне имеет побочный эффект, то его можно будет наблюдать перед вызовом front во время текущего кэширования диапазона.

Кроме того, следует позаботиться о композиции cache с std.range.take. Если разместить take перед cache, то cache будет "знать", когда диапазон заканчивается, и корректно перестанет кешировать элементы, когда нужно. Если вызов front не имеет побочных эффектов, размещение take после cache может дать более быстрый диапазон.

В любом случае, полученные диапазоны будут эквивалентны, но, возможно, не при тех же затратах или побочных эффектах.

import std.algorithm.comparison : equal;
import std.range;
int i = 0;

auto r = iota(0, 4).tee!((a){i = a;}, No.pipeOnPop);
auto r1 = r.take(3).cache();
auto r2 = r.cache().take(3);

assert(equal(r1, [0, 1, 2]));
assert(i == 2); //Последний "увиденный" элемент был 2. Данные в кеше очищены.

assert(equal(r2, [0, 1, 2]));
assert(i == 3); //cache получил доступ к 3. Он до сих пор хранятся внутри кэша.

template map(fun...) if (fun.length >= 1)

auto map(Range)(Range r) if (isInputRange!(Unqual!Range));

Реализует одноимённую функцию (также известную как transform), присутсвующую во многих языках с функциональным привкусом. Вызов map!(fun)(range) возвращает диапазон, у которого элементы получены примением fun(a) слева направо для всех элементов a в range. Исходные диапазоны не изменяются. Вычисление выполняется лениво.

Параметры:

fun	одна или больше функций
Range r	входной диапазон

Возвращает:

диапазон с применённой каждой из fun ко всем элементам. Если присутсвует более одной функции fun, типом элемента будет Tuple (кортеж), содержащий один элемент для каждой fun.

Смотрите также:

Map

Примеры:

import std.algorithm.comparison : equal;
import std.range : chain;
int[] arr1 = [ 1, 2, 3, 4 ];
int[] arr2 = [ 5, 6 ];
auto squares = map!(a => a * a)(chain(arr1, arr2));
assert(equal(squares, [ 1, 4, 9, 16, 25, 36 ]));

Примеры:

В map можно передать несколько функций. В этом случае, тип элемента будет кортежем, содержащим один элемент для каждой функции.

auto sums = [2, 4, 6, 8];
auto products = [1, 4, 9, 16];

size_t i = 0;
foreach (result; [ 1, 2, 3, 4 ].map!("a + a", "a * a"))
{
    assert(result[0] == sums[i]);
    assert(result[1] == products[i]);
    ++i;
}

Примеры:

Вы можете присвоить идентификатору псевдоним для map с некоторой функцией(ями) и использовать его отдельно:

import std.algorithm.comparison : equal;
import std.conv : to;

alias stringize = map!(to!string);
assert(equal(stringize([ 1, 2, 3, 4 ]), [ "1", "2", "3", "4" ]));

template each(alias pred = "a")

Жадно итерирует над r и вызывает pred на каждом элементе.

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

each также поддерживает основанные на opApply итераторы, так что он будет работать, например, с std.parallelism.parallel.

Параметры:

pred	предикат, применяемый к каждому элементу диапазона
Range r	диапазон или итерируемый объект, над которым`each` итерирует

Смотрите также:

std.range.tee

Примеры:

import std.range : iota;

long[] arr;
iota(5).each!(n => arr ~= n);
assert(arr == [0, 1, 2, 3, 4]);

// Если диапазон это поддерживает, величину можно изменять на месте
arr.each!((ref n) => n++);
assert(arr == [1, 2, 3, 4, 5]);

arr.each!"a++";
assert(arr == [2, 3, 4, 5, 6]);

// ref-лямбды не поддерживаются для не-ref-диапазонов
static assert(!is(typeof(arr.map!(n => n).each!((ref n) => n++))));

// предикат по-умолчанию поглощает диапазон
auto m = arr.map!(n => n);
(&m).each();
assert(m.empty);

// Индексы также доступны для изменений на-месте
arr[] = 0;
arr.each!"a=i"();
assert(arr == [0, 1, 2, 3, 4]);

// Итераторы opApply также работают
static class S
{
    int x;
    int opApply(scope int delegate(ref int _x) dg) { return dg(x); }
}

auto s = new S;
s.each!"a++";
assert(s.x == 1);

template filter(alias predicate) if (is(typeof(unaryFun!predicate)))

auto filter(Range)(Range rs) if (isInputRange!(Unqual!Range));

Реализует фильтрующую функцию высшего порядка. Предикат передаётся на std.functional.unaryFun, и может принимать или строку, или любой вызываемый объект, который можно выполнить через pred(element).

Параметры:

predicate	Функция, применяемая к каждому элементу диапазона
Range range	Входной диапазон элементов

Возвращает:

filter!(predicate)(range) возвращает новый диапазон, содержащий только те элементы x в диапазоне range , для которых predicate(x) возвращает true.

Смотрите также:

Filter (higher-order function)

Примеры:

import std.algorithm.comparison : equal;
import std.math : approxEqual;
import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];

auto small = filter!(a => a < 3)(arr);
assert(equal(small, [ 1, 2 ]));

// Тоже самое, через Uniform Function Call Syntax (UFCS)
auto sum = arr.filter!(a => a < 3);
assert(equal(sum, [ 1, 2 ]));

// В сочетании с chain(), чтобы охватить несколько диапазонов
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = chain(a, b).filter!(a => a > 0);
assert(equal(r, [ 3, 400, 100, 102 ]));

// Смешивание конвертируемых типов – тоже честная игра 
double[] c = [ 2.5, 3.0 ];
auto r1 = chain(c, a, b).filter!(a => cast(int) a != a);
assert(approxEqual(r1, [ 2.5 ]));

template filterBidirectional(alias pred)

auto filterBidirectional(Range)(Range r) if (isBidirectionalRange!(Unqual!Range));

Аналогично filter, за исключением того, что определяет двунаправленный диапазон. Есть недостаток в скорости – конструктор тратит время на поиск последнего элемента в диапазоне, который удовлетворяет условию фильтрации (дополнительно к поиску первого). Преимущество в том, что отфильтрованный диапазон может распределяться с обоих направлений. Также, к отфильтрованному диапазону можно применить std.range.retro.

Предикат передаётся на std.functional.unaryFun, и может принимать или строку, или любой вызываемый объект, который можно выполнить через pred(element).

Параметры:

pred	Функция, применяемая к каждому элементу диапазона
Range r	Двунаправленный диапазон элементов

Возвращает:

новый диапазон, содержащий только те элементы в r , для которых pred возвращает true.

Примеры:

import std.algorithm.comparison : equal;
import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];
auto small = filterBidirectional!("a < 3")(arr);
static assert(isBidirectionalRange!(typeof(small)));
assert(small.back == 2);
assert(equal(small, [ 1, 2 ]));
assert(equal(retro(small), [ 2, 1 ]));
// В комбинации chain(), чтобы распределять несколько диапазонов
int[] a = [ 3, -2, 400 ];
int[] b = [ 100, -101, 102 ];
auto r = filterBidirectional!("a > 0")(chain(a, b));
assert(r.back == 102);

Group!(pred, Range) group(alias pred = "a == b", Range)(Range r); struct Group(alias pred, R) if (isInputRange!R);

Группирует последовательные эквиалентные элементы в единственный кортеж из элемента и количества его повторений.

Аналогично uniq, group формирует диапазон, который итерирует над уникальными последовательными элементами данного диапазона. Каждый элемент этого диапазона является кортежем из элемента и количества, сколько раз он повторялся в исходном диапазоне. Эквивалентность элементов определяется с использованием предиката pred, который установлен по умолчанию на "a == b". Предикат передаётся на std.functional.binaryFun, и может принимать или строку, или любой вызываемый объект, который может быть выполнен через pred(element, element).

Параметры:

pred	Двухаргументный предикат для определения эквивалентности двух элементов.
Range `r`	Входной диапазон для итерации.

Возвращает:

Диапазон элементов типа Tuple!(ElementType!R, uint), представляющий каждый последовательный уникальный элемент и соответствующее количество его вхождений. Он будет входным диапазоном, если R является входным диапазоном, и лидирующим диапазоном во всех остальных случаях.

Примеры:

import std.algorithm.comparison : equal;
import std.typecons : tuple, Tuple;

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(group(arr), [ tuple(1, 1u), tuple(2, 4u), tuple(3, 1u),
    tuple(4, 3u), tuple(5, 1u) ][]));

auto chunkBy(alias pred, Range)(Range r) if (isInputRange!Range);

Разделяет входной диапазон на поддиапазоны эквиалентных соседних элементов.

Эквивалентность определяется предикатом pred, который может быть любым двухаргументным, который передаётся в std.functional.binaryFun, или одноаргументным, который передаётся в std.functional.unaryFun. В двухаргументной форме, два элемента диапазона a и b считаются эквивалентными, если pred(a,b) возвращает истину. В одноаргументной форме, два элемента считаются эквивалентными, если pred(a) == pred(b) – истинно.

Этот предикат должен быть отношением эквивалентности, то есть, он должен быть рефлексивным (pred(x,x) – всегда истина), симметричным (pred(x,y) == pred(y,x)), и транзитивным (pred(x,y) && pred(y,z) подразумевает pred(x,z)). Если это не так, то диапазон, возвращаемый chunkBy, может вызвать исключение во время выполнения или работать нестабильно.

Параметры:

pred	Предикат для определения эквивалентности.
Range `r`	Диапазон, который будет разбит на части.

Возвращает:

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

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

Смотрите также:

group, который схлопывает соседние эквивалентные элементы в единственный элемент.

Примеры:

Показано использование с двухаргументным предикатом:

import std.algorithm.comparison : equal;

// Группирование по конкретному атрибуту каждого элемента:
auto data = [
    [1, 1],
    [1, 2],
    [2, 2],
    [2, 3]
];

auto r1 = data.chunkBy!((a,b) => a[0] == b[0]);
assert(r1.equal!equal([
    [[1, 1], [1, 2]],
    [[2, 2], [2, 3]]
]));

auto r2 = data.chunkBy!((a,b) => a[1] == b[1]);
assert(r2.equal!equal([
    [[1, 1]],
    [[1, 2], [2, 2]],
    [[2, 3]]
]));

Примеры:

Показано использование с одноаргументным предикатом:

import std.algorithm.comparison : equal;
import std.typecons : tuple;
import std.range.primitives;

// Группирование по конкретному атрибуту каждого элемента:
auto range =
[
    [1, 1],
    [1, 1],
    [1, 2],
    [2, 2],
    [2, 3],
    [2, 3],
    [3, 3]
];

auto byX = chunkBy!(a => a[0])(range);
auto expected1 =
[
    tuple(1, [[1, 1], [1, 1], [1, 2]]),
    tuple(2, [[2, 2], [2, 3], [2, 3]]),
    tuple(3, [[3, 3]])
];
foreach (e; byX)
{
    assert(!expected1.empty);
    assert(e[0] == expected1.front[0]);
    assert(e[1].equal(expected1.front[1]));
    expected1.popFront();
}

auto byY = chunkBy!(a => a[1])(range);
auto expected2 =
[
    tuple(1, [[1, 1], [1, 1]]),
    tuple(2, [[1, 2], [2, 2]]),
    tuple(3, [[2, 3], [2, 3], [3, 3]])
];
foreach (e; byY)
{
    assert(!expected2.empty);
    assert(e[0] == expected2.front[0]);
    assert(e[1].equal(expected2.front[1]));
    expected2.popFront();
}

auto joiner(RoR, Separator)(RoR r, Separator sep) if (isInputRange!RoR && isInputRange!(ElementType!RoR) && isForwardRange!Separator && is(ElementType!Separator : ElementType!(ElementType!RoR))); auto joiner(RoR)(RoR r) if (isInputRange!RoR && isInputRange!(ElementType!RoR));

Лениво соединяет к диапазон диапазонов с разделителем sep. Сам разделитель является диапазоном. Если разделитель не предусмотрен, тогда диапазоны соединяются непосредственно без чего-либо в между ними (в других языках часто называется flatten).

Параметры:

RoR `r`	Входной диапазон входных диапазонов для соединения.
Separator `sep`	Лидирующий диапазон элемента(элементов), служащий в качестве разделителей в соединенном диапазоне.

Возвращает:

Диапазон элементов в соединенном диапазоне. Он будет лидирующим диапазоном, если как внешний, так и внутренние диапазоны RoR являются лидирующими диапазонами; в противном случае он будет только входным дипазоном.

Смотрите также:

std.range.chain, который сцепляет последовательность диапазонов с совместимыми элементами в единственный диапазон.

Примеры:

import std.algorithm.comparison : equal;
import std.conv : text;

assert(["abc", "def"].joiner.equal("abcdef"));
assert(["Mary", "has", "a", "little", "lamb"]
    .joiner("...")
    .equal("Mary...has...a...little...lamb"));
assert(["", "abc"].joiner("xyz").equal("xyzabc"));
assert([""].joiner("xyz").equal(""));
assert(["", ""].joiner("xyz").equal("xyz"));

Переместиться к: reduce
template reduce(fun...) if (fun.length >= 1)

Реализует одноимённую функцию (также известную как accumulate, compress, inject, или foldl), представленную в различных языках программирования с функциональным привкусом. Есть также fold, которая делает то же самое, но с противоположным порядком параметров. Вызов reduce!(fun)(seed, range) сначала присваивает seed (семя) внутренней переменной result, также называемой аккумулятором. Затем, для каждого элемента x в диапазоне вычисляется result = fun(result, x). Наконец, result возвращается. Одноаргументная версия reduce!(fun)(range) работает аналогично, но использует первый элемент диапазона в качестве семени (дипазон должен быть не-пустым).

Возвращает:

накопленный result

Смотрите также:

Свёртка списка

fold функционально эквивалентна reduce с обратным порядком аргументов, и без необходимости использовать кортеж для нескольких семян. Это делает её легче для использования в цепях UFCS.

sum аналогична reduce!((a, b) => a + b) с парным суммированием чисел с плавающей запятой.

Примеры:

Множество составных действий над диапазоном оказываются решаемы быстро и легко с помощью reduce. Пример ниже иллюстрирует замечательную мощность и гибкость reduce.

import std.algorithm.comparison : max, min;
import std.math : approxEqual;
import std.range;

int[] arr = [ 1, 2, 3, 4, 5 ];
// Сумма всех элементов
auto sum = reduce!((a,b) => a + b)(0, arr);
assert(sum == 15);

// Снова сумма, с использованием строкового предиката с "a" и "b"
sum = reduce!"a + b"(0, arr);
assert(sum == 15);

// Вычислить максимум всех элементов
auto largest = reduce!(max)(arr);
assert(largest == 5);

// Снова максимум, но с использованием Uniform Function Call Syntax (UFCS)
largest = arr.reduce!(max);
assert(largest == 5);

// Вычислить количество нечетных элементов
auto odds = reduce!((a,b) => a + (b & 1))(0, arr);
assert(odds == 3);

// Вычислить сумму квадратов
auto ssquares = reduce!((a,b) => a + b * b)(0, arr);
assert(ssquares == 55);

// Цепь нескольких диапазонов
int[] a = [ 3, 4 ];
int[] b = [ 100 ];
auto r = reduce!("a + b")(chain(a, b));
assert(r == 107);

// Смешивание конвертируемых типов – тоже честная игра
double[] c = [ 2.5, 3.0 ];
auto r1 = reduce!("a + b")(chain(a, b, c));
assert(approxEqual(r1, 112.5));

// Для минимизации вложенности скобок можно использовать Uniform Function Call Syntax 
auto r2 = chain(a, b, c).reduce!("a + b");
assert(approxEqual(r2, 112.5));

Примеры:

Иногда очень полезно вычислять несколько составных действий за один проход. Одним из преимуществ является то, что вычисление выполняется быстрее, поскольку они будут разделять накладные расходы на выполнение цикла. Вот почему reduce принимает несколько функций. Если переданы две или больше функций, reduce возвращает объект std.typecons.Tuple (кортеж), в котором по одному члену на каждую переданную функцию. Количество семян должно соответственно возрасти.

import std.algorithm.comparison : max, min;
import std.math : approxEqual, sqrt;
import std.typecons : tuple, Tuple;

double[] a = [ 3.0, 4, 7, 11, 3, 2, 5 ];
// Вычислить минимум и максимум за один проход
auto r = reduce!(min, max)(a);
// Тип r - это Tuple!(int, int)
assert(approxEqual(r[0], 2));  // минимум
assert(approxEqual(r[1], 11)); // максимум

// Вычислить сумму и сумму квадратов за один проход
r = reduce!("a + b", "a + b * b")(tuple(0.0, 0.0), a);
assert(approxEqual(r[0], 35));  // сумма
assert(approxEqual(r[1], 233)); // сумма квадратов
// Вычислить среднее и среднеквадратичное отклонение из предыдущего
auto avg = r[0] / a.length;
auto stdev = sqrt(r[1] / a.length - avg * avg);

Переместиться к: 2
auto reduce(R)(R r)
if (isIterable!R);

Версия без семени. Первый элемент r используется как величина seed.

Для каждой функции f в fun, соответствующий seed тип S – Unqual!(typeof(f(e, e))), где e – элемент r: ElementType!R для диапазонов, и ForeachType!R в противном случае.

Как только S определён, затем S s = e; и s = f(s, e); оба должны быть легальными.

Если r пуст, тогда бросается исключение.

Параметры:

fun	одна или более функций
R `r`	итерируемая величина, как определено isIterable

Возвращает:

конечный результат аккумулятора

auto reduce(S, R)(S seed, R r) if (isIterable!R);

Для удобства, если seed – константа или квалифицированное поле, тогда reduce будет действовать на неквалифицированной копии. Если это случится, тогда возвращаемый тип не вполне будет соответствовать S.

Используйте fold вместо reduce , чтобы использовать версию с семенем в цепи UFCS.

Параметры:

fun	одна или более функций
S `seed`	начальное значение аккумулятора
R `r`	итерируемая величина, как определено isIterable

Возвращает:

конечный результат аккумулятора

template fold(fun...) if (fun.length >= 1)

Реализует одноимённую функцию (также известную как accumulate, compress, inject, или foldl), представленную в различных языках программирования с функциональным привкусом. Вызов fold!(fun)(range, seed) сначала присваивает seed (семя) внутренней переменной result, также называемую аккумулятором. Затем, для каждого элемента x в диапазоне вычисляется result = fun(result, x). Наконец, result возвращается. Одноаргументная версия fold!(fun)(range) работает аналогично, но использует первый элемент диапазона как семя (диапазон должен быть не-пустым).

Возвращает:

накопленный результат

Смотрите также:

Свёртка списка

sum аналогична fold!((a, b) => a + b), что обеспечивает точное суммирование чисел с плавающей запятой.

Это функционально эквивалентно reduce с обратным порядком аргументов, и без необходимости использовать кортеж для нескольких семян.

Примеры:

immutable arr = [1, 2, 3, 4, 5];

// Сумма всех элементов
assert(arr.fold!((a, b) => a + b) == 15);

// Просуммировать все элементы с явным семенем
assert(arr.fold!((a, b) => a + b)(6) == 21);

import std.algorithm.comparison : min, max;
import std.typecons : tuple;

// Вычислить минимум и максимум одновременно
assert(arr.fold!(min, max) == tuple(1, 5));

// Вычислить минимум и максимум одновременно с семенем
assert(arr.fold!(min, max)(0, 7) == tuple(0, 7));

// Можно использовать в цепи UFCS
assert(arr.map!(a => a + 1).fold!((a, b) => a + b) == 20);

Переместиться к: cumulativeFold
template cumulativeFold(fun...) if (fun.length >= 1)

Аналогично fold, но возвращает диапазон, содержащий последовательно вычисленные значения. Вызов cumulativeFold!(fun)(range, seed) сначала присваивает seed внутренней переменной result, также называемой аккумулятором. Возвращаемый диапазон содержит значения result = fun(result, x), лениво вычисляемые для каждого элемента x в диапазоне. Наконец, последний элемент имеет то же значение, что и fold!(fun)(seed, range). Одноаргументная версия cumulativeFold!(fun)(range) работает аналогично, но здесь первый элемент возвращается неизменным и используется как семя для следующих элементов. Эта функция также известна как partial_sum, accumulate, scan, Cumulative Sum.

Возвращает:

Функция возвращает диапазон, содержащий последовательность вычисленных значений. Если присутсвует более одной fun, типом элементов будет std.typecons.Tuple, содержащий один элемент для каждой fun.

Смотрите также:

Prefix Sum

Примеры:

import std.algorithm.comparison : max, min;
import std.array : array;
import std.math : approxEqual;
import std.range : chain;

int[] arr = [1, 2, 3, 4, 5];
// Частичная сумма всех элементов
auto sum = cumulativeFold!((a, b) => a + b)(arr, 0);
assert(sum.array == [1, 3, 6, 10, 15]);

// Снова частичная сумма, с использованием строкового предиката с "a" и "b"
auto sum2 = cumulativeFold!"a + b"(arr, 0);
assert(sum2.array == [1, 3, 6, 10, 15]);

// Вычислить частичный максимум всех элементов
auto largest = cumulativeFold!max(arr);
assert(largest.array == [1, 2, 3, 4, 5]);

// Снова частичный максимум, но с использованием Uniform Function Call Syntax (UFCS)
largest = arr.cumulativeFold!max;
assert(largest.array == [1, 2, 3, 4, 5]);

// Частичное количество нечетных элементов
auto odds = arr.cumulativeFold!((a, b) => a + (b & 1))(0);
assert(odds.array == [1, 1, 2, 2, 3]);

// Вычислить частичную сумму квадратов
auto ssquares = arr.cumulativeFold!((a, b) => a + b * b)(0);
assert(ssquares.array == [1, 5, 14, 30, 55]);

// Цепь нескольких диапазонов
int[] a = [3, 4];
int[] b = [100];
auto r = cumulativeFold!"a + b"(chain(a, b));
assert(r.array == [3, 7, 107]);

// Смешивание конвертируемых типов – тоже честная игра
double[] c = [2.5, 3.0];
auto r1 = cumulativeFold!"a + b"(chain(a, b, c));
assert(approxEqual(r1, [3, 7, 107, 109.5, 112.5]));

// Для минимизации вложенности скобок можно использовать Uniform Function Call Syntax 
auto r2 = chain(a, b, c).cumulativeFold!"a + b";
assert(approxEqual(r2, [3, 7, 107, 109.5, 112.5]));

Примеры:

Иногда очень полезно вычислять несколько составных действий за один проход. Одним из преимуществ является то, что вычисление выполняется быстрее, поскольку они будут разделять накладные расходы на выполнение цикла. Вот почему cumulativeFold принимает несколько функций. Если переданы две или больше функций, cumulativeFold возвращает объект std.typecons.Tuple (кортеж), в котором по одному члену на каждую переданную функцию. Количество семян должно соответственно возрасти.

import std.algorithm.comparison : max, min;
import std.algorithm.iteration : map;
import std.math : approxEqual;
import std.typecons : tuple;

double[] a = [3.0, 4, 7, 11, 3, 2, 5];
// Вычислить минимум и максимум за один проход
auto r = a.cumulativeFold!(min, max);
// Тип r - это Tuple!(int, int)
assert(approxEqual(r.map!"a[0]", [3, 3, 3, 3, 3, 2, 2]));     // минимум
assert(approxEqual(r.map!"a[1]", [3, 4, 7, 11, 11, 11, 11])); // максимум

// Вычислить сумму и сумму квадратов за один проход
auto r2 = a.cumulativeFold!("a + b", "a + b * b")(tuple(0.0, 0.0));
assert(approxEqual(r2.map!"a[0]", [3, 7, 14, 25, 28, 30, 35]));      // сумма
assert(approxEqual(r2.map!"a[1]", [9, 25, 74, 195, 204, 208, 233])); // сумма квадратов

Переместиться к: 2
auto cumulativeFold(R)(R range)
if (isInputRange!(Unqual!R));

Версия без семени. Первый элемент r используется как семя. Для каждой функции f в fun, соответствующий тип семени S – это Unqual!(typeof(f(e, e))), где e – элемент r: ElementType!R. Как только S определен, тогда S s = e; и s = f(s, e); оба выражения должны быть легальными.

Параметры:

fun	одна или больше функций
R `range`	Входной диапазон, как определено isInputRange

Возвращает:

диапазон, содержащий последовательно вычисленные значения.

auto cumulativeFold(R, S)(R range, S seed) if (isInputRange!(Unqual!R));

Версия с семенем. seed должно быть единственным значением, если fun является единственной функцией. Если fun – это несколько функций, тогда seed должно быть std.typecons.Tuple, с одним полем на функцию в f. Для удобства, если seed – константа или квалифицированное поле, тогда cumulativeFold будет действовать на неквалифицированной копии. Если это случится, тогда возвращаемый тип не вполне будет соответствовать S.

Параметры:

fun	одна или несколько функций
R `range`	входной диапазон, как определено isInputRange
S `seed`	начальное значение аккумулятора

Возвращает:

диапазон, содержащий последовательно вычисленные значения.

Переместиться к: 2 · 3 · 4
auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s)
if (is(typeof(binaryFun!pred(r.front, s)) : bool) && (hasSlicing!Range && hasLength!Range || isNarrowString!Range));

Лениво разделяет диапазон, используя элемент как разделитель. Это можно использовать с любым типом узких строк или диапазоном с поддержкой срезов, но популярнее всего со строковыми типами.

Про два соседних разделителя считается, что они окружают пустой элемент в диапазоне разделения. Примените filter!(a => !a.empty) к результату, чтобы избавиться от пустых элементов.

Предикат передаётся в std.functional.binaryFun, и может принимать как строку, так и любой вызываемый объект, который может выполнять pred(element, s).

Если дан пустой диапазон, результатом будет диапазон с одним пустым элементом. Если дан диапазон с одним разделителем, результатом будет диапазон с двумя пустыми элементами.

Если строка разбивается по пробельным символам и требуется сжать токены, рекомендуется использовать splitter без указания разделителя (см. четвертую перегрузку ниже).

Параметры:

pred	Предикат для сравнения каждого элемента с разделителем, по умолчанию "a == b".
Range `r`	Входной диапазон для разделения. Должен поддерживать срезы и свойство .length.
Separator `s`	Элемент, который будет рассматриваться как разделитель между сегментами диапазона для разделения.

Ограничения: Предикат pred должен принимать элемент r и разделитель s.

Возвращает:

Входной диапазон поддиапазонов из элементов между разделителями. Если r – лидирующий диапазон или двунаправленный диапазон, возвращаемый диапазон будет таким же.

Смотрите также:

std.regex.splitter для версии, которая разделяет с использованием регулярного выражения, заданного разделителем.

Примеры:

import std.algorithm.comparison : equal;

assert(equal(splitter("hello  world", ' '), [ "hello", "", "world" ]));
int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
assert(equal(splitter(a, 0), w));
a = [ 0 ];
assert(equal(splitter(a, 0), [ (int[]).init, (int[]).init ]));
a = [ 0, 1 ];
assert(equal(splitter(a, 0), [ [], [1] ]));
w = [ [0], [1], [2] ];
assert(equal(splitter!"a.front == b"(w, 1), [ [[0]], [[2]] ]));

auto splitter(alias pred = "a == b", Range, Separator)(Range r, Separator s) if (is(typeof(binaryFun!pred(r.front, s.front)) : bool) && (hasSlicing!Range || isNarrowString!Range) && isForwardRange!Separator && (hasLength!Separator || isNarrowString!Separator));

Подобно предыдущей перегрузке splitter, за исключением того, что использует другой диапазон как разделитель. Он может использоваться любым типом узкой строки или может типом диапазона с поддержкой срезов, но популярнее всего со строковыми типами. Предикат передаётся в std.functional.binaryFun, и может принимать как строку, так и любой вызываемый объект, который может выполнять pred(r.front, s.front).

Параметры:

pred	Предикат для сравнения каждого элемента с разделителем, по умолчанию "a == b".
Range `r`	Входной диапазон для разделения.
Separator `s`	Лидирующий диапазон , рассматриваемый как разделитель между сегментами `r`.

Ограничения: Предикат pred должен принимать элемент r и разделитель s.

Возвращает:

Смотрите также:

std.regex.splitter для версии, которая разделяет с использованием регулярного выражения, заданного разделителем.

Примеры:

import std.algorithm.comparison : equal;

assert(equal(splitter("hello  world", "  "), [ "hello", "world" ]));
int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
int[][] w = [ [1, 2], [3, 0, 4, 5, 0] ];
assert(equal(splitter(a, [0, 0]), w));
a = [ 0, 0 ];
assert(equal(splitter(a, [0, 0]), [ (int[]).init, (int[]).init ]));
a = [ 0, 0, 1 ];
assert(equal(splitter(a, [0, 0]), [ [], [1] ]));

auto splitter(alias isTerminator, Range)(Range input) if (isForwardRange!Range && is(typeof(unaryFun!isTerminator(input.front))));

Подобно предыдущей перегрузке splitter, за исключением того, что не использует разделитель. Вместо этого, предикат является одноаргументной функцией над типом элементов входного диапазона. Предикат isTerminator передаётся на std.functional.unaryFun и может принимать как строку, так и любой вызываемый объект, который может выполнять pred(element).

Параметры:

isTerminator	Предикат для принятия решения, где разделить диапазон.
Range `input`	Входной диапазон для разделения.

Ограничения: Предикат isTerminator должен принимать элемент input.

Возвращает:

Смотрите также:

std.regex.splitter для версии, которая разделяет с использованием регулярного выражения, заданного разделителем.

Примеры:

import std.algorithm.comparison : equal;

assert(equal(splitter!(a => a == ' ')("hello  world"), [ "hello", "", "world" ]));
int[] a = [ 1, 2, 0, 0, 3, 0, 4, 5, 0 ];
int[][] w = [ [1, 2], [], [3], [4, 5], [] ];
assert(equal(splitter!(a => a == 0)(a), w));
a = [ 0 ];
assert(equal(splitter!(a => a == 0)(a), [ (int[]).init, (int[]).init ]));
a = [ 0, 1 ];
assert(equal(splitter!(a => a == 0)(a), [ [], [1] ]));
w = [ [0], [1], [2] ];
assert(equal(splitter!(a => a.front == 1)(w), [ [[0]], [[2]] ]));

auto splitter(C)(C[] s) if (isSomeChar!C);

Лениво разделяет строку s на слова, используя пробел как разделитель.

Эта функция специфична для строк и, в отличие от splitter!(std.uni.isWhite), несколько пробелов подряд объединяются вместе (никакие пустые токены не будут производиться).

Параметры:

C[] s Строка для разделения.

Возвращает:

Входной диапазон срезов оригинальной строки, разделённой пробелами.

Примеры:

import std.algorithm.comparison : equal;
auto a = " a     bcd   ef gh ";
assert(equal(splitter(a), ["a", "bcd", "ef", "gh"][]));

auto sum(R)(R r) if (isInputRange!R && !isInfinite!R && is(typeof(r.front + r.front))); auto sum(R, E)(R r, E seed) if (isInputRange!R && !isInfinite!R && is(typeof(seed = seed + r.front)));

Суммирует элементы r, который должен быть конечным входным диапазоном. Хотя в принципе sum(r) эквивалентна fold!((a, b) => a + b)(r, 0), sum использует специализированные алгоритмы, максимузирующие точность, следующим образом.

Если std.range.primitives.ElementType!R – тип чисел с плавающей запятой и R – диапазон с произвольным доступом с длиной и поддержкой срезов, тогда sum использует pairwise summation алгоритм.
Если ElementType!R – тип чисел с плавающей запятой и R – конечный входной дипазон (но не является диапазоном с произвольным доступом с поддержкой срезов), тогда sum использует алгоритм Кэхэна.
Во всех остальных случаях выполняется простое сложение элемент за элементом.

Для входных чисел с плавающей запятой, вычисления выполняются с точностью real для входов real и с точностью double в противном случае (Обратите внимание, что это особый случай, который отклоняется от поведения fold, который сохранил бы точность float для диапазона float). Для всех остальных типов, расчеты производятся на типе, полученном при суммировании двух элементов диапазона, который может отличаться от типа самих элементов (например, в случае integral promotion).

В sum можно передать семя seed. Это семя не только будет использоваться как начальное значение, но и его тип аннулирует всё, сказанное выше, и определяет алгоритм и точность, используемые для суммирования.

Заметьте, что эти специализированные алгоритмы суммирования выполняют больше простых операций, чем обычное суммирование. Поэтому, если в определённых случаях максимальная скорость требуется за счет точности, можно использовать fold!((a, b) => a + b)(r, 0), который не специализируется на суммировании.

Параметры:

E `seed`	начальное значение для суммирования
R `r`	конечный входной диапазон

Возвращает:

Сумма всех элементов в диапазоне r.

auto uniq(alias pred = "a == b", Range)(Range r) if (isInputRange!Range && is(typeof(binaryFun!pred(r.front, r.front)) == bool));

Лениво итерирует уникальные последовательные элементы данного диапазона (функционально родственно системной утилите uniq). Эквивалентность элементов вычисляется с использованием предиката pred, по умолчанию "a == b". Предикат передаётся в std.functional.binaryFun, и может принимать как строку, так и любой вызываемый объект, который может выполнять pred(element, element). Если данный диапазон является двунаправленным, uniq также производит двунаправленный диапазон.

Параметры:

pred	Предикат для определения эквивалентности между элементами диапазона.
Range `r`	Входной диапазон элементов для фильтрации.

Возвращает:

Входной диапазон последовательно уникальных элементов в исходном диапазоне. Если r также является лидирующим диапазоном или двунаправленным диапазоном, возвращаемый диапазон будет таким же.

Примеры:

import std.algorithm.mutation : copy;
import std.algorithm.comparison : equal;

int[] arr = [ 1, 2, 2, 2, 2, 3, 4, 4, 4, 5 ];
assert(equal(uniq(arr), [ 1, 2, 3, 4, 5 ][]));

// Фильтрация дубликатов на-месте, используя копию
arr.length -= arr.uniq().copy(arr).length;
assert(arr == [ 1, 2, 3, 4, 5 ]);

// Заметьте, что уникальность определяется только для последовательных элементов;
// дублированные элементы, разделенные промежуточным отличающимся элементом, 
// не будут устраняться:
assert(equal(uniq([ 1, 1, 2, 1, 1, 3, 1]), [1, 2, 1, 3, 1]));

Permutations!Range permutations(Range)(Range r) if (isRandomAccessRange!Range && hasLength!Range); struct Permutations(Range) if (isRandomAccessRange!Range && hasLength!Range);

Лениво вычисляет все перестановки r, используя Heap's algorithm.

Возвращает:

Лидирующий диапазон, элементы которого – объекты std.range.indexed, примерённые к r.

Смотрите также:

std.algorithm.sorting.nextPermutation.

Примеры:

import std.algorithm.comparison : equal;
import std.range : iota;
assert(equal!equal(iota(3).permutations,
    [[0, 1, 2],
     [1, 0, 2],
     [2, 0, 1],
     [0, 2, 1],
     [1, 2, 0],
     [2, 1, 0]]));

Andrei Alexandrescu 2008-. | Page generated by Ddoc on Mon Dec 26 12:45:19 2016