Algol
20.01.2010, 13:12
Проблематика:
Для хранения многомерных данных в C# предусмотрены статические массивы Multidimensional arrays и Jagged arrays. Их применение подразумевает, что размерность (число измерений) массивов известна заранее, на этапе компиляции. Если же требуется создание многомерного массива с неизвестным заранее числом измерений, то вместо статических массивов, как правило, используются сложные вложенные списки, типа List<ListOrValue>. Однако их применение неэффективно по ряду причин, среди которых: Большие накладные расходы памяти на хранение объектов, малая скорость создания массива, из-за необходимости создания большого числа объектов, невысокая скорость доступа к данным.
В заметке показывается более эффективная структура для создания и хранения многомерных массивов с неизвестной заранее размерностью.
Решение:
Для хранения многомерных данных, используется одномерный массив.
При хранении данных в одном большом одномерном массиве, минимизируются накладные расходы на память, на время создания массива, на время доступа к отдельному элементу.
Индекс одномерного массива будем называть сигнатурой. Для преобразования индексов элемента исходного многомерного массива, в индекс одномерного массива используется специальная формула.
Основная идея, лежащая в вычислении сигнатуры проста: будем пересчитывать все элементы многомерного массива по порядку, при этом сначала будем считать элементы по первой размерности, потом по второй и так далее. Например, для двумерного массива 3x3, будем считать элементы следующим образом:
012
345
678
Номер элемента в этой схеме как раз и является сигнатурой. Если получена сигнатура, то нетрудно «выпрямить» многомерный массив в одномерный. Одномерный массив просто хранит все элементы многомерного массива по индексу, совпадающему с номером (сигнатурой) элемента в многомерном массиве.
Рассмотрим метод определения сигнатуры для произвольных многомерных массивов. Допустим, у нас есть двумерный массив NxM. Из приведенной выше схемы нетрудно видеть, что сигнатура для произвольного элемента вычисляется следующим образом:
[I]Sig(i, j) = i+j*N
Рассмотрим сигнатуру, для элемента трехмерного массива, размерностью N*M*K:
[I]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
(где / - целочисленное деление, % - деление по модулю)
Реализация:
Ниже приведена реализация многомерного массива основанного на одномерном массиве для хранения данных и методе сигнатуры, для преобразования многомерных индексов в одномерный.
/// <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;
}
}
Примеры использования:
//создаем пятимерный массив, с размером 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[,,,,]
Для хранения многомерных данных в C# предусмотрены статические массивы Multidimensional arrays и Jagged arrays. Их применение подразумевает, что размерность (число измерений) массивов известна заранее, на этапе компиляции. Если же требуется создание многомерного массива с неизвестным заранее числом измерений, то вместо статических массивов, как правило, используются сложные вложенные списки, типа List<ListOrValue>. Однако их применение неэффективно по ряду причин, среди которых: Большие накладные расходы памяти на хранение объектов, малая скорость создания массива, из-за необходимости создания большого числа объектов, невысокая скорость доступа к данным.
В заметке показывается более эффективная структура для создания и хранения многомерных массивов с неизвестной заранее размерностью.
Решение:
Для хранения многомерных данных, используется одномерный массив.
При хранении данных в одном большом одномерном массиве, минимизируются накладные расходы на память, на время создания массива, на время доступа к отдельному элементу.
Индекс одномерного массива будем называть сигнатурой. Для преобразования индексов элемента исходного многомерного массива, в индекс одномерного массива используется специальная формула.
Основная идея, лежащая в вычислении сигнатуры проста: будем пересчитывать все элементы многомерного массива по порядку, при этом сначала будем считать элементы по первой размерности, потом по второй и так далее. Например, для двумерного массива 3x3, будем считать элементы следующим образом:
012
345
678
Номер элемента в этой схеме как раз и является сигнатурой. Если получена сигнатура, то нетрудно «выпрямить» многомерный массив в одномерный. Одномерный массив просто хранит все элементы многомерного массива по индексу, совпадающему с номером (сигнатурой) элемента в многомерном массиве.
Рассмотрим метод определения сигнатуры для произвольных многомерных массивов. Допустим, у нас есть двумерный массив NxM. Из приведенной выше схемы нетрудно видеть, что сигнатура для произвольного элемента вычисляется следующим образом:
[I]Sig(i, j) = i+j*N
Рассмотрим сигнатуру, для элемента трехмерного массива, размерностью N*M*K:
[I]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
(где / - целочисленное деление, % - деление по модулю)
Реализация:
Ниже приведена реализация многомерного массива основанного на одномерном массиве для хранения данных и методе сигнатуры, для преобразования многомерных индексов в одномерный.
/// <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;
}
}
Примеры использования:
//создаем пятимерный массив, с размером 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[,,,,]