Проблематика: Для хранения многомерных данных в C# предусмотрены статические массивы Multidimensional arrays и Jagged arrays. Их применение подразумевает, что размерность (число измерений) массивов известна заранее, на этапе компиляции. Если же требуется создание многомерного массива с неизвестным заранее числом измерений, то вместо статических массивов, как правило, используются сложные вложенные списки, типа List<ListOrValue>. Однако их применение неэффективно по ряду причин, среди которых: Большие накладные расходы памяти на хранение объектов, малая скорость создания массива, из-за необходимости создания большого числа объектов, невысокая скорость доступа к данным. В заметке показывается более эффективная структура для создания и хранения многомерных массивов с неизвестной заранее размерностью. Решение: Для хранения многомерных данных, используется одномерный массив. При хранении данных в одном большом одномерном массиве, минимизируются накладные расходы на память, на время создания массива, на время доступа к отдельному элементу. Индекс одномерного массива будем называть сигнатурой. Для преобразования индексов элемента исходного многомерного массива, в индекс одномерного массива используется специальная формула. Основная идея, лежащая в вычислении сигнатуры проста: будем пересчитывать все элементы многомерного массива по порядку, при этом сначала будем считать элементы по первой размерности, потом по второй и так далее. Например, для двумерного массива 3x3, будем считать элементы следующим образом: 012 345 678 Номер элемента в этой схеме как раз и является сигнатурой. Если получена сигнатура, то нетрудно «выпрямить» многомерный массив в одномерный. Одномерный массив просто хранит все элементы многомерного массива по индексу, совпадающему с номером (сигнатурой) элемента в многомерном массиве. Рассмотрим метод определения сигнатуры для произвольных многомерных массивов. Допустим, у нас есть двумерный массив NxM. Из приведенной выше схемы нетрудно видеть, что сигнатура для произвольного элемента [i, j] вычисляется следующим образом: Sig(i, j) = i+j*N Рассмотрим сигнатуру, для элемента [i, j, k] трехмерного массива, размерностью N*M*K: Sig(i, j) = i+j*N+k*N*M Теперь выведем общую формулу сигнатуры для массива размерностью N1*N2*....: Sig(i1, i2, i3 ...) = i1 + i2*N1 + i3*N1*N2 + i4*N1*N2*N3 … Коэффициенты этой формулы, стоящие при индексах: 1, N1, N1*N2, N1*N2*N3 будем называть шагами. Каждая размерность имеет свой шаг, вычиcляемый по формуле: Step(i) = 1*N1*N2*..*N(i-1) Таким образом, сигнатура есть сумма индексов, умноженных на соответствующие шаги. Сигнатура, вычисленная по такой формуле имеет несколько интересных свойств. Свойство1: Если известна сигнатура S для некоторого элемента, то можно легко вычислить сигнатуру для следующего элемента по некоторой размерности i: Snext = S+Step(i) Свойство2: Если известна сигнатура S для некоторого элемента, то можно получить исходный индекс этого элемента в произвольной размерности i: Index(i) = (S/Step(i))%Ni (где / - целочисленное деление, % - деление по модулю) Реализация: Ниже приведена реализация многомерного массива основанного на одномерном массиве для хранения данных и методе сигнатуры, для преобразования многомерных индексов в одномерный. Code: /// <summary> /// Многомерный массив c произвольным числом измерений /// </summary> public class MultiDimensionalArray<T> { //размеры по измерениям public readonly int[] sizes; //шаги по измерениям public readonly int[] steps; //хранимые значения readonly T[] values; public MultiDimensionalArray(List<int> sizes) { this.sizes = sizes.ToArray(); //считаем шаги, и суммарную размерность steps = new int[sizes.Count]; int step = 1; for (int iDim = 0; iDim < sizes.Count; iDim++) { steps[iDim] = step; step = step * sizes[iDim]; } //создаем линейный массив, для хранения данных values = new T[step]; } /// <summary> /// Получение сигнатуры, по исходным индексам /// </summary> public int GetSignature(List<int> indexes) { int signature = 0; for (int iDim = 0; iDim < indexes.Count; iDim++) signature += indexes[iDim] * steps[iDim]; return signature; } /// <summary> /// Доступ к элементам по сигнатуре /// </summary> public T this[int signature] { get { return values[signature]; } set { values[signature] = value; } } /// <summary> /// Доступ к элементам по индексам /// </summary> public T this[List<int> indexes] { get { return values[GetSignature(indexes)]; } set { values[GetSignature(indexes)] = value; } } /// <summary> /// Получение многомерных индексов по сигнатуре /// </summary> public List<int> GetIndexes(int signature) { List<int> indexes = new List<int>(sizes.Length); for (int iDim = 0; iDim < sizes.Length; iDim++) indexes.Add((signature / steps[iDim]) % sizes[iDim]); return indexes; } } Примеры использования: Code: //создаем пятимерный массив, с размером 10 по каждой координате List<int> sizes = new List<int>() { 10, 10, 10, 10, 10}; MultiDimensionalArray<int> array = new MultiDimensionalArray<int>(sizes); //заносим и читаем некое значение по координатам array[new List<int> { 2, 3, 4, 2, 7 }] = 22; Console.WriteLine(array[new List<int> { 2, 3, 4, 2, 7 }]); // выводим одномерный срез по 4-му измерению (по координатам [2, 3, 4, *, 7]) // с применением сигнатуры и шага int size = array.sizes[3];//получаем размер 4-го измерения int step = array.steps[3];//получаем шаг 4-го измерения int sig = array.GetSignature(new List<int> { 2, 3, 4, 0/*стартуем с нуля*/, 7 });//получаем начальную сигнатуру for (int i = 0; i < size; i++) Console.WriteLine(array[sig+i*step]); //выводим двумерный срез по координатам [2, *, 4, *, 7] int size1 = array.sizes[3];//получаем размер 4-го измерения int step1 = array.steps[3];//получаем шаг 4-го измерения int size2 = array.sizes[1];//получаем размер 2-го измерения int step2 = array.steps[1];//получаем шаг 2-го измерения sig = array.GetSignature(new List<int> { 2, 0/*стартуем с нуля*/, 4, 0/*стартуем с нуля*/, 7 });//получаем начальную сигнатуру for (int i = 0; i < size1; i++) for (int j = 0; j < size2; j++) Console.WriteLine(array[sig + i*step1 + j*step2]); Тестирование производительности: Тестировались пятимерные массивы, с размерностью 10x10x10x10x10. По результатам тестирования, время создания многомерного массива MultiDimensionalArray<int> на 6% дольше создания int[,,,,]. Время доступа по сигнатуре – практически совпадает с доступом к int[,,,,] Время доступа по индексам – в 8 раз медленнее чем int[,,,,] Размер занимаемой памяти – равен int[,,,,]
Эм, а смысл использовать это, а не обыкновенный массив, если мы не можем сделать так(псевдокодом): m[2,3,4].append([[45],[3,4]]) Т.е. по сути у нас получается обыкновенный n-мерный массив, только с другой системой хранения.
псевдокода не понял ) Так и есть, разница только в том, что размерность (число измерений) в MultiDimensionalArray может быть задана в рантайме. То есть например так: Code: Console.ReadLine("Введите число измерений массива:") int dimCount = int.Parse(Console.ReadLine()); List<int> sizes = new List<int>(); for(int i=0;i<dimCount;i++) sizes.Add(10);//в каждом измерении 10 элементов MultiDimensionalArray<int> array = new MultiDimensionalArray<int>(sizes); PS Немного поправил статью, что бы было понятно, что речь идет о числе измерений, а не о числе элментов в каждом измерении.
В данной заметке ценность для кого-то представляет реализация. Ведь саму процедуру придумал Кантор больше ста лет назад. Правда он строил изоморфизм из произведения счётных, а не конечных множеств в счётное множество... Я тоже не до конца понял псевдокода... Мы добавляем к массиву m ещё один массив? Кстати да, проблемы начнутся тогда, когда надо будет динамически менять число элементов в массиве...
все хорошо .... алгоритм нужный , и пусть физики и математики нет для 5-го измерения .... ! для Си шарпа сойдет ... а для серьезных вещей умножение и деление меняется на сдвиги и в размерах(размерности) дополнение в большую сторону до степени 2-ки(для тех самых сдвигоф)! (если заводили речь о скорости)
я чета не понял, а че C# поддерживает обращение по индексу в более чем 2-х размерном миссиве ? Это чисто фича С#, ведь в С/C++ таким образом можно обратиться максимум к двумерному массиву, и все. Притом где то даже читал видал реализацию на С++, n-мерных массивов путем хранения их как одномерных. И везде написано что обращение к двумерным массивам гораздо более медленное чем к одномерным. Шот какое то безумие выше описано. Либо опять таки спрашиваю это только особенность С# ?
Ну про Кантора я как-то я не подумал, когда столкнулся с проблемой. Конечно я америку тут не открываю, просто небольшой велосипедик, трехколесный В моих задачах это не встречается. Я делал просто замену статических массивов.
В некоторых задачах многомерные данные встречаются довольно часто (OLAP, статистика) Обращаю внимание, что алгоритм предназначался не для оптимизации скорости доступа (он безусловно выше в статическом массиве), а для снижения накладных расходов памяти по сравнению с реализацией на списках. НО если ты предложишь реализацию с более эффективным доступом, я буду только рад
