Многомерные массивы в D [перевод]

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

Массивы

Массивы D можно разделить на обычные массивы, массивы фиксированной длины (статические) и динамические массивы. Обычные массивы представляют собой общую концепцию коллекции, в которой элементы расположены рядом. Статические массивы имеют фиксированные размеры во время создания и, следовательно, известны во время компиляции. Динамические массивы не имеют фиксированных размеров и могут увеличиваться или уменьшаться по запросу. Тип массива имеет свойства length (длина) и ptr (указатель на первый элемент) (подробнее о массивах D можно прочитать здесь).

int[] arr = [2, 0, -1, 3, 5];
arr.length;
/* 5 */

arr.ptr;
/* 7FE3FBD34000 */

*arr.ptr;
/* 2 */

Динамические массивы также называются срезами в D. Специфика срезов и их реализации выходит за рамки статьи (о срезах можете прочитать здесь).

int[] arr = [2, 0, -1, 3, 5];
int[] arrSlice1 = arr[]; // создать срез "arr"
assert(arrSlice1.length == arr.length);

int[] arrSlice2 = arr[1 .. 3]; // создать срез "arr"
arrSlice2.length;
/*
    2
*/

*arrSlice2.ptr;
/*
    0
*/

arrSlice2 ~= 5; // добавить новый элемент
/*
    [0, -1, 5]
*/

Создание многомерных массивов

Многомерный массив в D может быть создан с использованием стандартных массивов. Создадим один.

int[][] jaggedArr1 = [[0, 1, 2], [3, 4, 5]];
/*
    [[0, 1, 2]
     [3, 4, 5]]
*/

Это создаст так называемый «зубчатый» массив, потому что количество элементов в каждом измерении не фиксировано и может быть произвольным.

int[][] jaggedArr2 = [[0, 1], [2, 3, 4], [5, 6]];
/*
    [[0, 1]
     [2, 3, 4]
     [5, 6]]
*/

int[][] dynamicJaggedArr = new int[][](2, 3);
/*
    [[0, 0, 0]
     [0, 0, 0]]
*/

Такая схема массива не очень эффективна, потому что внешний массив строится как отдельный блок памяти со ссылками на внутренние массивы. Каждый поиск в массиве будет иметь небольшие накладные расходы.

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

int[2][3] denseArr = [[1, 2], [3, 4], [5, 6]];
/*
    [[1, 2]
     [3, 4]
     [5, 6]]
*/

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

int rows = 3;
double[2][] dynamicDenseArr = double[2][](rows);
/*
    [[0, 0, 0]
     [0, 0, 0]]
*/

Вы также можете использовать функцию iota модуля std.range для ленивого создания диапазона значений в заданном диапазоне и функцию chunks для создания двумерного представления плоского буфера одномерного массива.

import std.range;
import std.array;

int[] arr = 20.iota.array;
auto arr2dView = arr.chunks(5);
/*
    [[0, 1, 2, 3, 4],
     [5, 6, 7, 8, 9],
     [10, 11, 12, 13, 14],
     [15, 16, 17, 18, 19]]
*/

Стандартные массивы не обладают этим shape свойством, но мы можем моделировать его с помощью двух D-шаблонов.

// рекурсивный шаблон
void shape(T)(T arr, long[] dims = []) {
    dims ~= arr.length;
    shape(arr[0], dims);
}

// назначение шаблона в остановке рекурсии и печати результата
void shape(T: int)(T val, long[] dims) {
    writeln(dims);
}

arr2dView.shape;
/*
    [4, 5]
*/

auto arr3dView = arr2dView.chunks(2);
arr3dView.shape;
/*
    [2, 2, 5]
*/

Конечно, наше самодельное shape свойство будет отображать правильные размеры только для правильно разбитых массивов.

Создание многомерных массивов с помощью Mir

Высокопроизводительные многомерные массивы могут быть созданы с помощью библиотеки mir-algorithm, являющейся частью более крупного пакета Mir, который включает в себя различные высокопроизводительные числовые библиотеки для D. Чтобы соответствовать терминологии Mir, мы называем массивы срезами, а матрицы — многомерными срезами.

Модуль mir.ndslice предоставляет различные быстрые и эффективные с точки зрения памяти реализации многомерных срезов (не путайте их со стандартными D-срезами ). mir.ndslice Slice — многомерный диапазон произвольного доступа, который также имеет shape, strides, structure и т.д. свойства. Следует иметь в виду, что mir.ndslice поставляется со своими собственными Slice-совместимыми реализациями многих функций std.range, поэтому по большей части вам не нужно явно импортировать функции из std.range.

Создадим срез.

import mir.ndslice;

auto mirSlice = [1, 2, 3].slice!int;
/*
    [[[0, 0, 0],
      [0, 0, 0]]]
*/

Ой, это не похоже на то, что мы ожидали. Если вы посмотрите на форму mirArr.shape вышеупомянутого среза, вы увидите [1, 2, 3]. Да, мы создали трехмерный срез нулей (потому что int.init == 0) вместо трехэлементного среза. Что вам нужно сделать, так это использовать as функцию модуля mir.ndslice.topology, которая создает ленивое представление исходных элементов, преобразованных в желаемый тип.

import mir.ndslice.topology: as;

auto mirSlice = [1, 2, 3].as!int.slice;
/*
    [1, 2, 3]
*/

Создадим еще несколько многомерных массивов для примера.

auto a = slice!int([2, 3]);
auto b = slice!int(2, 3); // тоже работает!
/*
    [[0, 0],
     [0, 0],
     [0, 0]]
*/

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

import mir.ndslice;

auto a = slice([2, 3], 1);
/*
    [[1, 1, 1],
     [1, 1, 1]],
*/

auto b = slice([2, 3], -0.1);
/*
    [[-0.1, -0.1, -0.1],
     [-0.1, -0.1, -0.1]]
*/

auto c = slice!long([2, 3], 5);
/*
    [[5, 5, 5],
     [5, 5, 5]]
*/

Создание срезов с помощью slice кажется немного громоздким. Есть специальный метод sliced, который значительно упрощает работу.

int[] arr = [1, 2, 3];
auto mirSlice = arr.sliced;
/*
    [1, 2, 3]
*/

// однострочный вариант
auto mirSlice = [1, 2, 3].sliced;
/*
    [1, 2, 3]
*/

sliced создает n-мерное представление над итератором. Итератор может быть простым массивом D, указателем или итератором, определяемым пользователем.

import std.array;
import mir.ndslice;

int[][] jaggedArr = [[0, 1, 2], [3, 4, 5]]; // стандартный D-массив
// создает одномерный вид среза, состоящий из обычных D-массивов. `.shape` будет `[2]`
auto arrSlice11 = jaggedArr.sliced;
// выделенный 2D срез. `.shape` будет `[2, 3]`
auto arrSlice12 = jaggedArr.fuse;
/* arrSlice11 и arrSlice12:
    [[0, 1, 2],
     [3, 4, 5]]
*/

auto arrSlice2 = 100.iota.array.sliced;
/*
    [0, 1, 2, 3, ..., 99]
*/

// функция `iota` также принимает необязательное начальное значение.

// выделенный 1D срез, состоящий из ленивых 1D срезов поверх `IotaIterator`.
// `.shape` будет `[2]`
auto a1 = iota([2, 3], 10).array.sliced;

// выделенный 2D срез. `.shape` будет `[2, 3]`
auto a2 = iota([2, 3], 10).slice;

/* a1 и a2:
    [[10, 11, 12],
     [13, 14, 15]]
*/

Вы можете пропустить вызов array вашего объекта, если укажете размеры sliced.

auto a = 20.iota.sliced(20);
/*
    [0, 1, 2, 3, ..., 19]
*/

auto b = 10.iota.sliced(2, 5);
/*
    [[0, 1],
     [2, 3],
     [4, 5],
     [6, 7],
     [8, 9]]
*/

Но это еще не все! Вы можете комбинировать iota с, fuse чтобы выделить новый срез следующим образом.

auto a = [2, 3].iota!int.fuse;
/*
    [[0, 1, 2],
     [3, 4, 5]]
*/

auto b = [2, 3].iota!int(2).fuse;
/*
    [[2, 3, 4],
     [5, 6, 7]]
*/

Хорошо, но как мне вернуться к обычным массивам D?

Чтобы вернуться к массиву D, используйте .field свойство среза.

import mir.ndslice;

auto mirSlice = [2, 3].slice!int;
int[] arr = mirSlice.field;
/*
    [0, 0, 0, 0, 0, 0]
*/

Подождите, но теперь это одномерный массив! Да, потому что то, что мы называем 2D-массивом в D, — это просто 2D-представление в 1D-массиве. Использование вложенных массивов int[][] для представления многомерных массивов неэффективно, поскольку внешние массивы будут содержать ссылки на внутренние массивы, а поиск каждого элемента будет иметь дополнительные расходы.

Свойство .field доступно только для непрерывных в памяти срезов.

Печать срезов

Печать массивов и срезов в D. Используйте writeln с циклом foreach.

import std.stdio;
import mir.ndslice;

auto m = 15.iota.sliced(3, 5);

writeln(m);
/*
    [[0, 1, 2, 3, 4], [5, 6, 7, 8, 9], [10, 11, 12, 13, 14]]
*/

foreach (i; m) {
    writeln(i);
}
/*
    [0, 1, 2, 3, 4],
    [5, 6, 7, 8, 9],
    [10, 11, 12, 13, 14]
*/

Что ж, это работает, но как насчет красивой печати? Если вы хотите узнать, как красиво печатать многомерные массивы D, ознакомьтесь с этой записью.

Создание случайных N-мерных срезов

Что, если вы хотите создать срез случайных элементов? Мы будем использовать функции generate , take модуля std.range и функцию uniform модуля std.random. Хотя mir.ndslice имеет множество собственных реализаций функций std.range, generate и take является эксклюзивным для std.range.

import std.range: generate, take;
import std.random: uniform;
import mir.ndslice;

auto rndSlice = generate!(() => uniform(0, 0.99)).take(10).array.sliced;
/*
    [0.184327, 0.741689, 0.296142, ..., 0.0102164]
*/

Обратите внимание, как мы явно конвертируем результат выражения в array прежде, чем передать его в sliced. Почему? Потому что вызов array фактически выполняет предыдущее ленивое выражение и позволяет использовать sliced его результат. Без этого преобразования sliced не сработало бы, поскольку не знает, что делать с Take!(Generator!(function () @safe => uniform(0, 0.99)))типом (типом generate!(() => uniform(0, 0.99)).take(10)) выражения.

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

int err; // сохраняет операционный вывод
auto rndMatrix = rndSlice.reshape([5, 2], err);
/*
    [[0.184327, 0.741689],
     [0.296142, 0.982893],
     [0.587764, 0.763811],
     [0.312337, 0.891162],
     [0.0886852, 0.0102164]]
*/

Вы также можете изменить форму с помощью, sliced но тогда вам сначала придется использовать flattened для сглаживания вашего массива.

auto a = [2, 4].iota.flattened.sliced(4, 2);
/*
    [[0, 1],
     [2, 3],
     [4, 5],
     [6, 7]]
*/

Другой способ сгенерировать случайный многомерный срез с использованием стандартных функций D — это объединить предыдущее generate выражение с fill методом, доступным в std.algorithm. Вот, взгляните.

import mir.ndslice;
import std.algorithm.mutation: fill;
import std.range: generate;
import std.random: uniform;

double[] arr = new double[10]; // выделить массив double

auto fun = generate!(() => uniform(0, .99)); // присвоить массиву значения
arr.fill(fun); // fill принимает как отдельные значения, так и функции

arr.sliced(5, 2);
/*
    [[0.0228295, 0.267278],
     [0.224073, 0.962407],
     [0.475771, 0.317672],
     [0.966923, 0.886558],
     [0.758477, 0.854988]]
*/

Вышеупомянутые операции делают все на месте. Если это не является обязательным требованием, мы можем сделать немного иначе. Давайте создадим новый объект и предоставим 2D-представление в наш заполненный массив.

auto sl = slice!double(5, 2);
auto fun = generate!(() => uniform(0, 99));

sl.field.fill(fun);
/*
    [[0.273062, 0.59894],
     [0.358506, 0.784792],
     [0.634209, 0.906578],
     [0.0535602, 0.573161],
     [0.0746745, 0.537331]]
*/

Однако, если вы хотите использовать mir на полную мощность, вам следует использовать randomSlice метод, предоставляемый пакетом mir.random.algorithm. Этот метод позволяет выполнить случайную выборку из нормального или равномерного распределения с использованием выбранной вами формы среза. Вот как это работает.

// этот импорт необходим
import mir.ndslice;
import mir.random : threadLocalPtr, Random; // генераторы случайных чисел
import mir.random.variable : uniformVar, normalVar; // распределения
import mir.random.algorithm : randomSlice;


auto rndMatrix1 = uniformVar!int(0, 10).randomSlice([5, 2]);
/*
    [[5, 0],
     [9, 3],
     [8, 3],
     [5, 9],
     [4, 8]]
*/

// или другой вариант с нестандартным rng семенем
auto rng = Random(123);
auto rndMatrix2 = rng.randomSlice(uniformVar(-1.0, 1.0), [5, 2]);

// даже если тип является предполагаемым, вы можете определить его
auto rndMatrix3 = rng.randomSlice(uniformVar!double(-1.0, 1.0), [5, 2]);

/*
    [[-0.0660341, 0.290473],
     [0.215803, 0.975375],
     [-0.724666, 0.293703],
     [0.131249, 0.664371],
     [-0.0193379, 0.706641]]
*/

// или используйте указатель на генератор rng
auto rndMatrix = threadLocalPtr!Random.randomSlice(uniformVar!double(-1.0, 1.0), [5, 2]);

/*
    [[0.664374, -0.432451],
     [0.717084, 0.130015],
     [-0.0144875, -0.402825],
     [-0.741251, -0.116261],
     [0.918571, -0.530099]]
*/

Какой метод использовать — решать вам. Интуитивно понятно, что использование специальных функций mir было бы наиболее эффективным. Однако возможность генерировать массивы и матрицы также с использованием стандартных языковых методов без слишком большого ущерба для производительности — это здорово. И это верно не только для многомерных массивов. Когда язык позволяет вам плавно перемещаться по своей экосистеме, вы не чувствуете себя обремененным конкретной библиотекой. В конце концов, это означает, что вам не нужно знать значительную часть его API, чтобы добиться цели.

Посмотрите, как обновить элементы до нуля.

// работает для ndslices, arrays и ranges.
import mir.algorithm.iteration: each;

rndMatrix.each!((ref a){a = 0;}); // не выделяем
/*
    [[0, 0],
     [0, 0],
     [0, 0],
     [0, 0],
     [0, 0]]
*/

rndMatrix.each!"a = 0"; // строковый миксин тоже работает, не выделяем
/*
    [[0, 0],
     [0, 0],
     [0, 0],
     [0, 0],
     [0, 0]]
*/

Кроме того, вы можете использовать map вместо each для создания нового Slice объекта. Однако имейте в виду, что вам придется вызвать slice, потому что map ленив.

auto zeroMatrix = rndMatrix.map!(i => 0).slice; // выделено
/*
    [[0, 0],
     [0, 0],
     [0, 0],
     [0, 0],
     [0, 0]]
*/

auto zeroMatrix = rndMatrix.shape.slice!double(0); // выделено
/*
    [[0, 0],
     [0, 0],
     [0, 0],
     [0, 0],
     [0, 0]]
*/

Если вам не хватает numpy с его zeros, напишите простой шаблон D.

void zeros(T)(ref T obj) {
    obj.each!((ref a) {a = 0;}); // не выделяется
}

Более короткий вариант с миксином.

void zeros(T)(ref T obj) {
    obj.each!"a = 0"; // не выделяется
}

rndMatrix.zeros;
/*
    [[0, 0],
     [0, 0],
     [0, 0],
     [0, 0],
     [0, 0]]
*/

Также работает простое присвоение операционного индекса.

rndMatrix[] = 0; // или 0.0

Вариант с map и выделением.

auto zeros(T)(T obj){
    return obj.map!"0".slice; // выделяется новый срез
}

auto zeroMatrix = rndMatrix.zeros;
/*
    [[0, 0],
     [0, 0],
     [0, 0],
     [0, 0],
     [0, 0]]
*/

Основные операции

Основные математические операции с одномерными срезами просты.

import mir.ndslice;

auto a = 10.iota.sliced(10);
/* лениво:
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/

auto b = a + 2;
/* лениво:
    [2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
*/

auto c = 2 * b - 1;
/* лениво:
    [3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
*/

auto d = c^^2; // or c * c
/* лениво:
    [9, 25, 49, 81, 121, 169, 225, 289, 361, 441]
*/

auto a = slice([3], 1); // [1, 1, 1]
auto b = slice([3], 2); // [2, 2, 2]

auto c = a + b;
/* лениво:
    [3, 3, 3]
*/

auto d = b - a;
/* лениво:
    [1, 1, 1]
*/

auto e = 10.iota.sliced(5, 2);
auto f = e - 9;
/* лениво:
    [[-9, -8],
     [-7, -6],
     [-5, -4],
     [-3, -2],
     [-1, 0]]
*/

auto d = 4.iota.sliced(2, 2);
auto g = d * d.transposed.slice; // "g" не выделяется потому, что * лениво в Mir
d[] *= d.transposed; // другой вариант с выделением
/*
    [[0, 2],
     [2, 9]]
*/

Как вы могли заметить, операции применяются поэлементно. Мне удобнее переключаться с D-массива на срезы Mir с помощью sliced, выполнять ряд основных операций, а затем снова переключаться с помощью .field на D-массив. Нет необходимости злоупотреблять map. Имейте в виду, что .field требуется для того, чтобы Slice был непрерывным (смотрите assumeContiguous метод). Но будьте осторожны с assumeContiguous, он отменяет некоторые операции без выделения памяти, такие как .transposed.

auto a = 10.iota.sliced(5, 2);
a.shape == a.transposed.assumeContiguous.shape; // true

Что, если я хочу изменить только одно или несколько определенных значений внутри многомерного среза? Давай попробуем.

auto a = 10.iota.sliced(5, 2);
a[1, 0] *= 2; // ОШИБКА!

Вы не можете сделать это на ленивом представлении срезов. Вам нужен реальный Slice объект, созданный с помощью slice.

auto a = slice([5, 2], 1);
a[1, 0] *= 2;
/*
    [[1, 1],
     [2, 1],
     [1, 1],
     [1, 1],
     [1, 1]]
*/

// обновить всю третью строку
a[2][] *= 3;
/*
    [[1, 1],
     [2, 1],
     [3, 3],
     [1, 1],
     [1, 1]]
*/

Давайте посмотрим , как использовать некоторые универсальные функции, такие как exp, sqrtи sum с Slice. Мы можем применить exp и sqrt используя map следующим образом:

auto a = slice!double([2, 3], 1.0);
/*
    [[1, 1, 1],
     [1, 1, 1]]
*/

import mir.math.common: exp, sqrt;

auto b = a.map!exp;
/* лениво:
    [[2.71828, 2.71828, 2.71828],
     [2.71828, 2.71828, 2.71828]]
*/

auto c = b.map!sqrt;
/* лениво:
    [[1.64872, 1.64872, 1.64872],
     [1.64872, 1.64872, 1.64872]]
*/

А как насчет суммы? mir поставляется с собственной реализацией sum в модуле mir.math.sum. В зависимости от типа переменной доступны разные алгоритмы суммирования.

import mir.math.sum;

auto a = 10.iota.slice;
auto b = arr.sum;
/* 45 */

Доступ к измерениям среза

Как выполнять операции с отдельными измерениями? Для этого у Mir есть функция byDim, которая принимает измерение в качестве параметра для итерации. Посмотрим, как им пользоваться.

byDim возвращает одномерный срез, состоящий из N-1 размерных срезов.

import mir.ndslice;

auto a = [5, 2].iota.slice;
/*
    [[0, 1],
     [2, 3],
     [4, 5],
     [6, 7],
     [8, 9]]
*/

a.byDim!1; // 1 по строкам, 0 по столбцам для 2D-среза
/*
    [[0, 2, 4, 6, 8],
     [1, 3, 5, 7, 9]]
*/

Давайте посчитаем сумму каждого столбца в 2D-срезе.

import mir.math.sum;

auto colsSum = a.byDim!1.map!sum;
/* лениво:
    [20, 25]
*/

Мы можем проверить, какой столбец содержит нечетные числа.

import mir.algorithm.iteration: all;

auto b = [5, 2].iota.slice;
/*
    [[0, 1],
     [2, 3],
     [4, 5],
     [6, 7],
     [8, 9]]
*/

auto c = a.byDim!1.map!(a => a.all!(a => a % 2 == 1))
auto d = a.byDim!1.map!(all!"a % 2"); // или менее подробный миксин
/*
    [false, true]
*/

А как насчет сортировки 2D-среза по размеру?

import mir.ndslice;
import mir.ndslice.sorting;

auto a = [5, 3, -1, 0, 10, 5, 6, 2, 7, 1].sliced(5, 2);
/*
    [[5, 3],
     [-1, 0],
     [10, 5],
     [6, 2],
     [7, 1]]
*/

a.byDim!0.each!sort; // сортировка на месте
/*
    [[3, 5],
     [-1, 0],
     [5, 10],
     [2, 6],
     [1, 7]]
*/

Индексирование, нарезка и итерация

mir.ndslice Slice индексируется целыми числами без знака, идентично стандартным массивам D.

auto origSlice = 10.iota.slice;
/*
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/

origSlice[0];
/*
    0
*/

origSlice[8];
/*
    8
*/

Slice точно так же нарезаются с использованием синтаксиса диапазона номеров [start .. end].

auto origSlice = 10.iota.slice;
/*
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/

auto newSlice = origSlice[0 .. 6];
/*
    [0, 1, 2, 3, 4, 5]
*/

Чтобы проиндексировать последний элемент фрагмента, вы можете использовать свойство .length или его сокращение $. Вы также можете использовать пустые скобки [] для выбора всех элементов массива от индекса 0 до последнего индекса $. Однако отрицательные значения индекса не допускаются.

auto origSlice = 10.iota.slice;
assert(origSlice == origSlice[0 .. origSlice.length]);
assert(origSlice == origSlice[0 .. $]);
assert(origSlice == origSlice[]);

Кроме того, вы можете выполнять основные математические операции с $ оператором, чтобы индексировать элементы с конца. Индексирование только с помощью $ не работает.

auto origSlice = 10.iota.slice;
/*
    [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/

origSlice[$-1];
/*
    9
*/

origSlice[2 .. $-3];
/*
    [2, 3, 4, 5, 6]
*/


origSlice[$-3 .. $-1]
/*
    [7, 8]
*/

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

auto matrix = iota([4, 2], 1);
/*
    [[1, 2],
     [3, 4],
     [5, 6],
     [7, 8]]
*/

matrix[0 .. 2]
/*
    [[1, 2],
     [3, 4]]
*/

matrix[0 .. 2, 1]
/*
    [3, 4]
*/

matrix[0 .. 2][1][0]
/*
    3
*/

Slice также можно проиндексировать с другим Slice подобным образом origSlice[newSlice]. В таком случае newSlice заменяется [0 .. newSlice.length]индексным диапазоном.

auto origSlice = iota([4, 2], 1).slice;
/*
    [[1, 2],
     [3, 4],
     [5, 6],
     [7, 8]]
*/

auto newSlice = 3.iota.slice;
/*
    [0, 1, 2]
*/

origSlice[newSlice]; // origSlice[[0 .. 3]]
/*
    [[1, 2],
     [3, 4],
     [5, 6]]
*/

Источник: tastyminerals — Multidimensional Arrays in D / Mar 22, 2020

Bagomot

Эколог, почти программист-самоучка, мучаю майнкрафт.

Добавить комментарий