alias
SortOutput
= std.typecons.Flag!"sortOutput".Flag;
Указывает, требуется ли выход определенного алгоритма в отсортированном формате.
Если установлено в
SortOutput
.no, выход не должен быть отсортирован.
В противном случае, если установлено в
SortOutput
.yes, выход должен быть отсортирован.
void
completeSort
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(SortedRange!(Range1, less)
lhs
, Range2
rhs
)
if (hasLength!Range2 && hasSlicing!Range2);
Сортирует цепь диапазонов с произвольным доступом chain(lhs
, rhs
) согласно предикату
less. Предполагается, что левая сторона диапазона lhs
уже отсортирована; rhs
считается неотсортированным. Точная стратегия выбирается в зависимости от относительных размеров lhs
и
rhs
. Выполняет от Ο(lhs
.length + rhs
.length * log(rhs
.length))
(в лучшем случае) до Ο((lhs
.length + rhs
.length) * log(lhs
.length +
rhs
.length)) (при неблагоприятном случае) операций обмена swap.
Параметры: less |
Предикат для сортировки. |
ss |
Используемая стратегия обмена. |
SortedRange!(Range1, less) lhs |
Отсортированная, левая сторона диапазона с произвольным доступом. |
Range2 rhs |
Неотсортированная, правая сторона диапазона с произвольным доступом. |
Примеры: import std.range : assumeSorted;
int[] a = [ 1, 2, 3 ];
int[] b = [ 4, 0, 6, 5 ];
completeSort(assumeSorted(a), b);
assert(a == [ 0, 1, 2 ]);
assert(b == [ 3, 4, 5, 6 ]);
bool
isSorted
(alias less = "a < b", Range)(Range
r
)
if (isForwardRange!Range);
bool
isStrictlyMonotonic
(alias less = "a < b", Range)(Range
r
)
if (isForwardRange!Range);
Проверяет, отсортирован ли лидирующий диапазон согласно операции сравнения less. Выполняет Ο(r
.length) вычислений less.
В отличие от
isSorted
,
isStrictlyMonotonic
не допускает равные значения, то есть такие, для которых как
less(a, b), так и
less(b, a) возвращают
false
.
С каждой из функций, предикат должен давать строгое упорядочение. Например, использование
"a <= b" вместо
"a < b"
некорректно и вызовет сообщение об ошибке.
Параметры: less |
Предикат, в соответсвии с которым должен быть отсортирован диапазон. |
Range r |
Лидирующий диапазон, который проверяется на наличие сортировки. |
Возвращает: true если диапазон отсортирован, false
в противном случае. isSorted
допускает дубликаты, isStrictlyMonotonic
– нет.
Примеры: assert([1, 1, 2].isSorted);
assert(![1, 1, 2].isStrictlyMonotonic);
int[] arr = [4, 3, 2, 1];
assert(!isSorted(arr));
assert(!isStrictlyMonotonic(arr));
assert(isSorted!"a > b"(arr));
assert(isStrictlyMonotonic!"a > b"(arr));
sort(arr);
assert(isSorted(arr));
assert(isStrictlyMonotonic(arr));
bool
ordered
(alias less = "a < b", T...)(T
values
)
if (T.length == 2 && is(typeof(binaryFun!less(values
[1], values
[0])) : bool) || T.length > 2 && is(typeof(ordered
!less(values
[0..1 + $ / 2]))) && is(typeof(ordered
!less(values
[$ / 2..$]))));
bool
strictlyOrdered
(alias less = "a < b", T...)(T
values
)
if (is(typeof(ordered!less(values
))));
Подобно isSorted, возвращает true
, если данные величины values
упорядочены согласно операции сравнения less. В отличие от isSorted, принимает величины непосредственно, а не структурированные в диапазоне.
ordered
допускает повторения
values
, т.е.
ordered
(1, 1, 2) возвратит
true
. Чтобы проверить, что
values
упорядочены строго монотонно, используйте
strictlyOrdered
;
strictlyOrdered
(1, 1, 2) возвратит
false
.
С каждой из функций, предикат должен давать строгое упорядочение. Например, использование
"a <= b" вместо
"a < b"
некорректно и вызовет сообщение об ошибке.
Параметры: T values |
Тестируемые значения |
less |
Сравнивающий предикат |
Возвращает: true
если значения упорядочены; ordered
допускает дубликаты,
strictlyOrdered
– нет.
Примеры: assert(ordered(42, 42, 43));
assert(!strictlyOrdered(43, 42, 45));
assert(ordered(42, 42, 43));
assert(!strictlyOrdered(42, 42, 43));
assert(!ordered(43, 42, 45));
assert(ordered("Jane", "Jim", "Joe"));
assert(strictlyOrdered("Jane", "Jim", "Joe"));
assert(ordered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
assert(!strictlyOrdered!((a, b) => a.length > b.length)("Jane", "Jim", "Joe"));
Range
partition
(alias predicate, SwapStrategy ss, Range)(Range
r
)
if (ss == SwapStrategy.stable && isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
Range
partition
(alias predicate, SwapStrategy ss = SwapStrategy.unstable, Range)(Range
r
)
if (ss != SwapStrategy.stable && isInputRange!Range && hasSwappableElements!Range);
Разделяет диапазон на два, используя данный предикат predicate.
В частности, переупорядочивает диапазон r
= [left, right), используя обмен так, что все элементы i, для которых predicate(i) возвращает истину, предшествуют всем элементам j, для которых predicate(j) возвращает ложь.
Выполняет Ο(r
.length) (для unstable или semistable) или Ο(r
.length * log(r
.length)) (для stable) вычислений less и операций обмена. Неустойчивая (unstable) версия выполняет минимально возможное количество операций обмена (приблизительно половина от выполняемых полуустойчивой (semistable) версией).
Параметры: predicate |
Предикат, в соотвествии с которым происходит разделение. |
ss |
Применяемая стратегия обмена. |
Range r |
Разделяемый диапазон с произвольным доступом. |
Возвращает: Правая часть
r
после разделения.
Если
ss == SwapStrategy.stable,
partition
сохраняет относительное упорядочение всех элементов
a,
b в
r
для которых
predicate(a) ==
predicate(b). Если
ss == SwapStrategy.semistable,
partition
сохраняет относительное упорядочение всех элементов
a,
b в левой части
r
для которых
predicate(a) == predicate(b).
Примеры: import std.algorithm.searching : count, find;
import std.conv : text;
import std.range.primitives : empty;
import std.algorithm.mutation : SwapStrategy;
auto Arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
auto arr = Arr.dup;
static bool even(int a) { return (a & 1) == 0; }
auto r = partition!(even)(arr);
assert(r == arr[5 .. $]);
assert(count!(even)(arr[0 .. 5]) == 5);
assert(find!(even)(r).empty);
arr[] = Arr[];
r = partition!(q{(a & 1) == 0})(arr);
assert(r == arr[5 .. $]);
arr[] = Arr[];
r = partition!(q{(a & 1) == 0}, SwapStrategy.stable)(arr);
assert(arr == [2, 4, 6, 8, 10, 1, 3, 5, 7, 9] && r == arr[5 .. $]);
arr[] = Arr[];
int x = 3;
bool fun(int a) { return a > x; }
r = partition!(fun, SwapStrategy.semistable)(arr);
assert(arr == [4, 5, 6, 7, 8, 9, 10, 2, 3, 1] && r == arr[7 .. $]);
size_t
pivotPartition
(alias less = "a < b", Range)(Range
r
, size_t
pivot
)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
Слово "pivot", как это бывает с большинством слов в английском языке, имеет кучу значений. Тут и далее я решил придерживаться значения, используемого в 3D-графике – "опорная точка" – прим. пер.
Разделяет
r
вокруг
pivot
, используя функцию сравнения
less, алгоритм родственен
Разбиению по Хоару. В частности, переставляет элементы
r
и возвращает индекс
k < r
.length такой, что:
r
[pivot
] заменено на r
[k]
- Все элементы e в поддиапазоне
r
[0 .. k] удовлетворяют !less(r
[k], e)
(то есть r
[k] больше или равен каждому элементу слева от него согласно предикату less)
- Все элементы e в поддиапазоне
r
[k .. $] удовлетворяют !less(e,
r
[k]) (то есть r
[k] меньше или равен каждому элементу справа от него согласно предикату less)
Если
r
содержит эквиалентные элементы, множество перестановок
r
удовлетворяют этим ограничениям. В таких случаях,
pivotPartition
пытается распределить эквивалентные элементы слева и справа от
k так, что
k останется близким к
r
.length / 2.
Параметры: less |
Предикат, используемый для сравнения, смоделированный как строгое слабое упорядочение (нерефлексивное, антисимметричное, транзитивное, и подразумевающее переходную эквивалентность) |
Range r |
Разделяемый диапазон |
size_t pivot |
Индекс опорной точки для разбиения, должен быть меньше, чем r .length |
Возвращает: Новая позиция pivot
Примеры: int[] a = [5, 3, 2, 6, 4, 1, 3, 7];
size_t pivot = pivotPartition(a, a.length / 2);
import std.algorithm.searching : all;
assert(a[0 .. pivot].all!(x => x <= a[pivot]));
assert(a[pivot .. $].all!(x => x >= a[pivot]));
bool
isPartitioned
(alias pred, Range)(Range
r
)
if (isForwardRange!Range);
Параметры: pred |
Предикат, в соответсвии с которым диапазон должен быть разделен. |
Range r |
Проверяемый диапазон. |
Возвращает: true
, если r
разделен в зависимости от предиката pred.
Примеры: int[] r = [ 1, 3, 5, 7, 8, 2, 4, ];
assert(isPartitioned!"a & 1"(r));
auto
partition3
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, E)(Range
r
, E
pivot
)
if
(ss == SwapStrategy.unstable && isRandomAccessRange!Range
&& hasSwappableElements!Range && hasLength!Range
&& hasSlicing!Range && is(typeof(binaryFun!less(r
.front, pivot
)) == bool) && is(typeof(binaryFun!less(pivot
, r
.front)) == bool) && is(typeof(binaryFun!less(r
.front, r
.front)) == bool));
Перестраивает элементы в r
на три граничащих диапазона и возвращает их. Первый и самый левый диапазон содержит только те элементы в r
, значение которых меньше, чем pivot
. Второй и средний диапазон содержит только те элементы в r
, которые равняются pivot
. Наконец, третий и самый правый диапазон содержит только те элементы в r
, которые больше, чем pivot
. Тест меньше-чем определяется двухаргументной функцией
less.
Параметры: less |
Предикат, используемый для перестроения. |
ss |
Используемая стратегия обмена. |
Range r |
Диапазон с произвольным доступом для перестройки. |
E pivot |
Элемент – опорная точка. |
Возвращает: Кортеж
std.typecons.Tuple из трех получившихся диапазонов. Эти диапазоны являются срезами исходного диапазона.
Недостатки: стабильная стратегия для partition3
ещё пока не реализована.
Примеры: auto a = [ 8, 3, 4, 1, 4, 7, 4 ];
auto pieces = partition3(a, 4);
assert(pieces[0] == [ 1, 3 ]);
assert(pieces[1] == [ 4, 4, 4 ]);
assert(pieces[2] == [ 8, 7 ]);
SortedRange!(RangeIndex, (a, b) => binaryFun!less(*a, *b))
makeIndex
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range
r
, RangeIndex
index
)
if (isForwardRange!Range && isRandomAccessRange!RangeIndex && is(ElementType!RangeIndex : ElementType!Range*));
void
makeIndex
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range
r
, RangeIndex
index
)
if
(isRandomAccessRange!Range && !isInfinite!Range &&
isRandomAccessRange!RangeIndex && !isInfinite!RangeIndex
&& isIntegral!(ElementType!RangeIndex));
Вычисляет индекс index
для r
, основанный на сравнении less.
index
– это отсортированный массив указателей или индексов в исходном диапазоне. Эта техника подобна сортировке, но более гибкая, поскольку (1) она допускает "сортировку" неизменяемых (immutable) коллекций, (2) допускает двоичный поиск, даже если исходная коллекция не предлагает произвольный доступ, (3) допускает множественные индексы, каждый со своим предикатом, и (4) может быть более быстрой при работе с большими объектами. Тем не менее, использование index
может также быть медленным при определенных обстоятельствах из-за дополнительной косвенности, и всегда использует больше памяти, чем решения, основанные на сортировке, поскольку, для индекса нужно пространство в дополнение к исходной коллекции. Сложность такая же, как и у sort.
Первая перегрузка
makeIndex
пишет в диапазон, содержащий указатели, вторая пишет в диапазон, содержащий смещения. Первая перегрузка требует, чтобы
Range был лидирующим диапазоном, последняя требует, чтобы он был диапазоном с произвольным доступом.
makeIndex
перезаписывает результат в свой второй аргумент, но никогда не перераспределяет его.
Параметры: less |
Используемое сравнение. |
ss |
Стратегия обмена. |
Range r |
Диапазон для построения индекса. |
RangeIndex index |
Результирующий индекс. |
Возвращает: Версия, основанная на указателях, возвращает обёртку SortedRange над индексом, с типом SortedRange!(RangeIndex, (a, b) =>
binaryFun!less(*a, *b)) , таким образом отражая упорядочение индекса. Версия, основанная на индексах, возвращает void, поскольку упорядочивающее отношение включает в себя не только index
, но также r
.
Исключения: Если длина второго аргумента меньше, чем длина самого индексируемого диапазона, выбрасывается исключение.
Примеры: immutable(int[]) arr = [ 2, 3, 1, 5, 0 ];
auto index1 = new immutable(int)*[arr.length];
makeIndex!("a < b")(arr, index1);
assert(isSorted!("*a < *b")(index1));
auto index2 = new size_t[arr.length];
makeIndex!("a < b")(arr, index2);
assert(isSorted!
((size_t a, size_t b){ return arr[a] < arr[b];})
(index2));
struct
Merge
(alias less = "a < b", Rs...) if (allSatisfy!(isInputRange, Rs));
Merge!(less, Rs)
merge
(alias less = "a < b", Rs...)(Rs
rs
);
Лениво вычисляет объединение двух или больше диапазонов rs
. Принимается, что диапазоны отсортированы предикатом less. Элементы на выходе не уникальные; длина выхода является суммой длин входов. (Свойство длины length предоставляется, если все диапазоны также имеют длину.) Типы элементов всех диапазонов должны иметь общий тип.
Параметры: less |
Предикат, в соответствии с которым данные диапазоны отсортированы. |
Rs rs |
Диапазоны для вычисления объединения. |
Возвращает: Диапазон, содержащий объединение данных диапазонов.
Примеры: import std.algorithm.comparison : equal;
int[] a = [1, 3, 5];
int[] b = [2, 3, 4];
assert(a.merge(b).equal([1, 2, 3, 3, 4, 5]));
-
-
-
@property ref ElementType
front
();
-
-
@property size_t
length
();
-
-
template
multiSort
(less...)
auto multiSort
(Range)(Range r)
if (validPredicates!(ElementType!Range, less));
Сортирует диапазон несколькими ключами. Вызов multiSort
!("a.id < b.id",
"a.date > b.date")(r) сортирует диапазон r по возрастанию id, и сортирует элементы, которые имеют одинаковый id по убыванию date. Такой вызов является эквивалентом sort!"a.id != b.id ? a.id
< b.id : a.date > b.date"(r), но multiSort
быстрее, поскольку он выполняет меньше сравнений (в дополнении к большему удобству).
Возвращает: Начальный диапазон, завернутый в виде SortedRange со своими предикатами, преобразованными в эквиалентный единичный предикат.
SortedRange!(Range, less)
sort
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range
r
)
if
((ss == SwapStrategy.unstable && (hasSwappableElements!Range ||
hasAssignableElements!Range) || ss != SwapStrategy.unstable &&
hasAssignableElements!Range) && isRandomAccessRange!Range
&& hasSlicing!Range && hasLength!Range);
Сортирует диапазон с произвольным доступом в соответсвии с предикатом
less. Выполняет
Ο(r
.length * log(r
.length)) вычислений
less. Если
less включает дорогие вычисления в ключе сортировки, возможно стоит использовать вместо этого
schwartzSort.
Стабильная сортировка требует, чтобы
hasAssignableElements!Range возвращал
true
.
sort
возвращает
std.range.SortedRange поверх исходного диапазона, позволяя функциям, которые имеют преимущество с отсортированными данными, знать, что диапазон отсортирован, и приспособиться соответственно.
std.range.SortedRange – это обёртка вокруг исходного диапазона, так что и она, и исходный диапазон отсортированы. Другие функции могут не знать, что исходный диапазон был отсортирован, но они
могут знать, что этот
std.range.SortedRange отсортирован.
Предварительные условия:
Ожидается, что предикат удовлетворяет определенным правилам для того, чтобы функция sort
вела себя, как ожидается, – в противном случае программа может потерпеть неудачу на определенных вводных данных (но не на всех), когда не скомпилирована в режиме релиза, из-за поверхностной проверки assumeSorted.
В частности, sort
ожидает, что при less(a,b) && less(b,c) подразумевается
less(a,c) (транзитивность), и, наоборот, при !less(a,b) && !less(b,c) подразумевается !less(a,c). Заметьте, что по умолчанию предикат ("a < b") не всегда удовлетворяет этим условиям для типов с плавающей точкой, поскольку это выражение всегда будет возвращать false
, если a или b равны NaN.
Используйте вместо этого std.math.cmp.
Параметры: less |
Предикат, используемый для сортировки. |
ss |
Используемая стратегия обмена. |
Range r |
Диапазон для сортировки. |
Возвращает: Исходный диапазон, завёрнутый в SortedRange с предикатом
binaryFun!less.
Алгоритмы:
Для нестабильной сортировки используется Introsort , а для стабильной –
Timsort. Каждый алгоритм имеет преимущества в дополнение к стабильности. Introsort обычно быстрее, но Timsort может достичь больших скоростей на данных с низкой энтропией или, если вызовы предиката дороги. Introsort не распределяет память, тогда как Timsort выполнит одно или более распределений за вызов. Оба алгоритма работают за Ο(n log n) в худшем случае сложности.
Примеры: int[] array = [ 1, 2, 3, 4 ];
array.sort!("a > b");
assert(array == [ 4, 3, 2, 1 ]);
array.sort();
assert(array == [ 1, 2, 3, 4 ]);
alias myComp = (x, y) => x > y;
assert(array.sort!(myComp).release == [ 4, 3, 2, 1 ]);
Примеры: import std.algorithm.mutation : SwapStrategy;
string[] words = [ "aBc", "a", "abc", "b", "ABC", "c" ];
sort!("toUpper(a) < toUpper(b)", SwapStrategy.stable)(words);
assert(words == [ "a", "aBc", "abc", "ABC", "b", "c" ]);
Примеры: double[] numbers = [-0.0, 3.0, -2.0, double.nan, 0.0, -double.nan];
import std.math : cmp, isIdentical;
import std.algorithm.comparison : equal;
sort!((a, b) => cmp(a, b) < 0)(numbers);
double[] sorted = [-double.nan, -2.0, -0.0, 0.0, 3.0, double.nan];
assert(numbers.equal!isIdentical(sorted));
SortedRange!(R, (a, b) => binaryFun!less(unaryFun!transform(a), unaryFun!transform(b)))
schwartzSort
(alias transform, alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, R)(R
r
)
if (isRandomAccessRange!R && hasLength!R);
Альтернативный метод сортировки, который нужно использовать, когда сравнение ключей включает дорогое вычисление. Вместо использования less(a, b) для сравнения элементов,
schwartzSort
использует less(transform(a), transform(b)). Значения функции
transform заранее вычисляются во временный массив, таким образом предотвращая её многократное вычисление. И наоборот, если стоимость transform небольшая по сравнению со стоимостью распределения памяти и заполнением предвычисленного массива, sort
может оказаться более быстрой и, следовательно, предпочтительной.
Этот метод сортировки родственен
Преобразованию Шварца, также известному как шаблон decorate-sort-undecorate в языках Python и Lisp. Сложность такая же, как и у соответствующей
sort, но
schwartzSort
вычисляет
transform только
r
.length раз (меньше половины по сравнению с обычной сортировкой). Использование лучше всего можно проиллюстрировать на примере.
Example:
uint hashFun(string) { ... дорогое вычисление ... }
string[] array = ...;
sort!((a, b) => hashFun(a) < hashFun(b))(array);
schwartzSort!(hashFun, "a < b")(array);
Функция
schwartzSort
может потребовать меньше временных данных и быть быстрее, чем идиома Perl или идиома decorate-sort-undecorate, представленная в Python и Lisp. Дело в том, что сортировка выполняется на-месте и создаются только минимальные дополнительные данные (один массив преобразованных элементов).
Проверить, был ли отсортирован массив, можно вызовом
isSorted!less(map!transform(r
)).
Параметры: transform |
Применяемое преобразование. |
less |
Сортирующий предикат. |
ss |
Стратегия обмена. |
R r |
Диапазон для сортировки. |
Возвращает: Исходный диапазон, завёрнутый в SortedRange с предикатом (a, b) => binaryFun!less(transform(a),
transform(b)).
void
partialSort
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range
r
, size_t
n
)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
Переупорядочивает диапазон с произвольным доступом r
так, что диапазон r
[0
.. mid] будет таким же, как будто весь r
был отсортирован, и оставляет диапазон r
[mid .. r
.length] в произвольном порядке. Выполняется за
Ο(r
.length * log(mid)) вычислений pred. Реализация просто вызывает topN!(less, ss)(r
, n
), и затем sort!(less, ss)(r
[0 .. n
]).
Параметры: less |
Предикат для сортировки. |
ss |
Используемая стратегия обмена. |
Range r |
Переупорядочиваемый диапазон с произвольным доступом. |
size_t n |
Длина начального сегмента r , которая будет отсортирована. |
Примеры: int[] a = [ 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 ];
partialSort(a, 5);
assert(a[0 .. 5] == [ 0, 1, 2, 3, 4 ]);
auto
topN
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range)(Range
r
, size_t
nth
)
if (isRandomAccessRange!Range && hasLength!Range && hasSlicing!Range);
Переупорядочивает с использованием обмена диапазон r
так, что r
[nth
] имеет отношение к элементу, который должен попасть туда, если диапазон полностью был отсортирован. Кроме того, функция также разделяет r
так, что все элементы
e1 от r
[0] до r
[nth
] удовлетворяют !less(r
[nth
], e1),
и все элементы e2 от r
[nth
] до r
[r
.length] удовлетворяют
!less(e2, r
[nth
]). По сути, она находит n
минимальных элементов (в соответсвии с less) в r
. Ожидаемое выполнение за
Ο(r
.length) (при unstable) или Ο(r
.length * log(r
.length))
(при stable) вычислений less и операций обмена.
Если n >= r
.length, алгоритм не имеет эффекта и возвращает
r
[0 .. r
.length].
Параметры: less |
Предикат для сортировки. |
ss |
Используемая стратегия обмена. |
Range r |
Переупорядочиваемый диапазон с произвольным доступом. |
size_t nth |
Индекс элемента, который должен оказаться в отсортированной позиции после выполнения функции. |
Недостатки: Стабильная версия topN
пока не реализована.
Примеры: int[] v = [ 25, 7, 9, 2, 0, 5, 21 ];
topN!"a < b"(v, 100);
assert(v == [ 25, 7, 9, 2, 0, 5, 21 ]);
auto n = 4;
topN!"a < b"(v, n);
assert(v[n] == 9);
auto
topN
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range1, Range2)(Range1
r1
, Range2
r2
)
if
(isRandomAccessRange!Range1 && hasLength!Range1 &&
isInputRange!Range2 && is(ElementType!Range1 ==
ElementType!Range2));
Сохраняет самые маленькие элементы двух диапазонов в диапазоне слева.
Параметры: less |
Предикат для сортировки. |
ss |
Используемая стратегия обмена. |
Range1 r1 |
Первый диапазон. |
Range2 r2 |
Второй диапазон. |
Примеры: int[] a = [ 5, 7, 2, 6, 7 ];
int[] b = [ 2, 1, 5, 6, 7, 3, 0 ];
topN(a, b);
sort(a);
assert(a == [0, 1, 2, 2, 3]);
TRange
topNCopy
(alias less = "a < b", SRange, TRange)(SRange
source
, TRange
target
, SortOutput
sorted
= No.sortOutput)
if (isInputRange!SRange && isRandomAccessRange!TRange && hasLength!TRange && hasSlicing!TRange);
Копирует верхние
n элементов входного диапазона
source
(источник) в диапазон с произвольным доступом
target
(цель), где
n =
target
.length. Элементы
source
остаются нетронутыми. Если
sorted
равно
true
,
target
будет отсортирована. В противном случае,
target
соблюдает
Двоичную кучу.
Параметры: less |
Предикат для сортировки. |
SRange source |
Диапазон – источник. |
TRange target |
Диапазон – цель. |
SortOutput sorted |
Сортировать ли элементы, скопированные в target . |
Возвращает: Срез target
, содержащий скопированные элементы.
Примеры: int[] a = [ 10, 16, 2, 3, 1, 5, 0 ];
int[] b = new int[3];
topNCopy(a, b, Yes.sortOutput);
assert(b == [ 0, 1, 2 ]);
void
topNIndex
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range
r
, RangeIndex
index
, SortOutput
sorted
= No.sortOutput)
if
(isRandomAccessRange!Range && isRandomAccessRange!RangeIndex
&& hasAssignableElements!RangeIndex &&
isIntegral!(ElementType!RangeIndex));
void
topNIndex
(alias less = "a < b", SwapStrategy ss = SwapStrategy.unstable, Range, RangeIndex)(Range
r
, RangeIndex
index
, SortOutput
sorted
= No.sortOutput)
if
(isRandomAccessRange!Range && isRandomAccessRange!RangeIndex
&& hasAssignableElements!RangeIndex &&
is(ElementType!RangeIndex == ElementType!Range*));
Дан диапазон элементов, создается индекс index
его верхних n элементов (то есть, первые n элементов, если бы диапазон был отсортирован).
Похоже на
topN, за исключением того, что диапазон не модифицируется.
Параметры: less |
Двухаргументный предикат, который определяет упорядочение элементов диапазона. Устанавливается по умолчанию в a < b. |
ss |
(Пока не реализовано.) Используемая стратегия обмена. |
Range r |
Диапазон с произвольным доступом
элементов, для которого создаётся индекс. |
RangeIndex index |
Диапазон с произвольным доступом
с присваиваемыми элементами, в котором строится индекс. Длина этого диапазона определяет, сколько верхних элементов в r будет проиндексировано.
Элементы этого индексного диапазона могут быть целыми числами, в этом случае конструируемый индекс будет состоять из начинающихся с нуля цифровых индексов в
r ; или они могут быть указателями на тип элементов r , в этом случае конструируемый индекс будет указателями на верхние элементы в
r . |
SortOutput sorted |
Определяет, сортировать ли index по элементам, на которые они ссылаются. |
Недостатки: Параметр стратегии обмена пока не реализован; в настоящее время игнорируется.
Примеры: int[] a = [ 10, 2, 7, 5, 8, 1 ];
int[] index = new int[3];
topNIndex(a, index, Yes.sortOutput);
assert(index == [5, 1, 3]);
int*[] ptrIndex = new int*[3];
topNIndex(a, ptrIndex, Yes.sortOutput);
assert(ptrIndex == [ &a[5], &a[1], &a[3] ]);
bool
nextPermutation
(alias less = "a < b", BidirectionalRange)(BidirectionalRange
range
)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
Переставляет диапазон range
на-месте к следующей лексикографически бОльшей перестановке.
Предикат
less определяет лексикографический порядок, который будет использоваться.
Если диапазон является к настоящему времени лексикографически самой большой перестановкой, он переставляется в наименьшую перестановку и возвращается
false
. В противном случае, возвращается
true
. Таким образом можно сгенерировать все перестановки диапазона, отсортировав его согласно
less, что произведёт лексикографически наименьшую перестановку, и затем вызывая
nextPermutation
, пока она не возвратит
false
.
Это гарантирует генерацию всех различных перестановок диапазона точно по одному разу. Если в дипазоне присутсвуют
N элементов и все они уникальные, тогда будет сгенерировано
N! перестановок. В противном случае, если есть несколько дублированных элементов, будет произведено меньше перестановок.
int[] a = [1,2,3,4,5];
do
{
} while (nextPermutation(a));
Параметры: less |
Этот предикат будет использоваться для определения лексикографического порядка перестановок. |
BidirectionalRange range |
Переставляемый диапазон. |
Возвращает: false
, если диапазон был лексикографически самым большим, в этом случае диапазон возвращается на лексикографически минимальную перестановку; в противном случае возвращается true
.
Примеры: int[] a = [1,2,3];
assert(nextPermutation(a) == true);
assert(a == [1,3,2]);
assert(nextPermutation(a) == true);
assert(a == [2,1,3]);
assert(nextPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextPermutation(a) == true);
assert(a == [3,2,1]);
assert(nextPermutation(a) == false);
assert(a == [1,2,3]);
Примеры: int[] a = [1,1,2];
assert(nextPermutation(a) == true);
assert(a == [1,2,1]);
assert(nextPermutation(a) == true);
assert(a == [2,1,1]);
assert(nextPermutation(a) == false);
assert(a == [1,1,2]);
bool
nextEvenPermutation
(alias less = "a < b", BidirectionalRange)(BidirectionalRange
range
)
if (isBidirectionalRange!BidirectionalRange && hasSwappableElements!BidirectionalRange);
Переставляет диапазон range
на-месте к следующей лексикографически бОльшей чётной
перестановке.
Предикат
less определяет лексикографический порядок, который будет использоваться.
Чётной перестановкой является та, которая получается путем замены чётного числа пар элементов в исходном диапазоне. Множество чётных перестановок отличается от множества
всех перестановок только тогда, когда нет повторяющихся элементов в диапазоне. Если диапазон имеет
N уникальных элементов, тогда существует точно
N!/2 чётных перестановок.
Если диапазон является к настоящему времени лексикографически самой большой перестановкой, он переставляется в наименьшую перестановку и возвращается
false
.
В противном случае, возвращается
true
, и диапазон модифицируется на-месте в лексикографически следующую чётную перестановку.
Таким образом можно сгенерировать чётные перестановки диапазона с уникальными элементами начиная с лексикографически минимальной перестановки, и многократно вызывая
nextEvenPermutation
, пока он не возвратит
false
.
int[] a = [1,2,3,4,5];
do
{
} while (nextEvenPermutation(a));
Можно также сгенерировать
нечётные перестановки замечая, что перестановки следуют правилу, что чётный + чётный = чётный, и нечётный + чётный = нечётный. Таким образом, обмен последних двух элементов в лексикографически наименьшем диапазоне, формирует первую нечётную перестановку. Затем, вызов
nextEvenPermutation
на этой первой нечётной перестановке сгенерирует следующую чётную перестановку относительно этой нечётной перестановки, которая будет являться следующей нечётной перестановкой исходного диапазона. Таким образом, многократно вызывая
nextEvenPermutation
, пока не возвратится
false
, можно получить перечисление нечётных перестановок исходного диапазона.
int[] a = [1,2,3,4,5];
swap(a[$-2], a[$-1]); do
{
} while (nextEvenPermutation(a));
Предупреждение:
Поскольку чётные перестановки отличаются от всех перестановок, только когда элементы диапазона уникальные, эта функция предполагает, что нет повторяющихся элементов с указанным порядком. Если это не так, некоторые перестановки могут не сгенерироваться. Если в диапазоне присутсвуют не уникальные элементы, вы должны использовать nextPermutation.
Параметры: less |
Этот предикат будет использоваться для определения лексикографического порядка перестановок. |
BidirectionalRange range |
Переставляемый диапазон. |
Возвращает: false
, если диапазон был лексикографически самым большим, в этом случае диапазон возвращается на лексикографически минимальную перестановку; в противном случае возвращается true
.
Примеры: int[] a = [1,2,3];
assert(nextEvenPermutation(a) == true);
assert(a == [2,3,1]);
assert(nextEvenPermutation(a) == true);
assert(a == [3,1,2]);
assert(nextEvenPermutation(a) == false);
assert(a == [1,2,3]);
Примеры: Чётные перестановки полезны для генерации координат определенных геометрических форм. Вот нетривиальный пример:
import std.math : sqrt;
enum real Phi = (1.0 + sqrt(5.0)) / 2.0; real[][] seeds = [
[0.0, 1.0, 3.0*Phi],
[1.0, 2.0+Phi, 2.0*Phi],
[Phi, 2.0, Phi^^3]
];
size_t n;
foreach (seed; seeds)
{
do
{
size_t i;
do
{
for (i=0; i < seed.length; i++)
{
if (seed[i] != 0.0)
{
seed[i] = -seed[i];
if (seed[i] < 0.0)
break;
}
}
n++;
} while (i < seed.length);
} while (nextEvenPermutation(seed));
}
assert(n == 60);