[C#] Эффективное хранение многомерных массивов

Discussion in 'С/С++, C#, Rust, Swift, Go, Java, Perl, Ruby' started by Algol, 20 Jan 2010.

  1. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    Проблематика:
    Для хранения многомерных данных в 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[,,,,]
     
    #1 Algol, 20 Jan 2010
    Last edited: 25 Jan 2010
  2. nerezus

    nerezus Banned

    Joined:
    12 Aug 2004
    Messages:
    3,192
    Likes Received:
    727
    Reputations:
    266
    Эм, а смысл использовать это, а не обыкновенный массив, если мы не можем сделать так(псевдокодом):
    m[2,3,4].append([[45],[3,4]])
    Т.е. по сути у нас получается обыкновенный n-мерный массив, только с другой системой хранения.
     
  3. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    псевдокода не понял )

    Так и есть, разница только в том, что размерность (число измерений) в 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
    Немного поправил статью, что бы было понятно, что речь идет о числе измерений, а не о числе элментов в каждом измерении.
     
    #3 Algol, 20 Jan 2010
    Last edited: 20 Jan 2010
  4. Root-access

    Root-access Elder - Старейшина

    Joined:
    18 Jun 2008
    Messages:
    194
    Likes Received:
    195
    Reputations:
    91
    В данной заметке ценность для кого-то представляет реализация.
    Ведь саму процедуру придумал Кантор больше ста лет назад. ;)
    Правда он строил изоморфизм из произведения счётных, а не конечных множеств в счётное множество...

    Я тоже не до конца понял псевдокода... Мы добавляем к массиву m ещё один массив?

    Кстати да, проблемы начнутся тогда, когда надо будет динамически менять число элементов в массиве...
     
  5. Retimiled

    Retimiled Banned

    Joined:
    23 Dec 2009
    Messages:
    110
    Likes Received:
    17
    Reputations:
    0
    все хорошо .... алгоритм нужный , и пусть физики и математики нет для 5-го измерения .... ! :D

    для Си шарпа сойдет ... а для серьезных вещей умножение и деление меняется на сдвиги и в размерах(размерности) дополнение в большую сторону до степени 2-ки(для тех самых сдвигоф)! :p (если заводили речь о скорости)
     
    #5 Retimiled, 20 Jan 2010
    Last edited: 20 Jan 2010
  6. cupper

    cupper Elder - Старейшина

    Joined:
    6 Jun 2007
    Messages:
    370
    Likes Received:
    92
    Reputations:
    5
    я чета не понял, а че C# поддерживает обращение по индексу в более чем 2-х размерном миссиве ? Это чисто фича С#, ведь в С/C++ таким образом можно обратиться максимум к двумерному массиву, и все. Притом где то даже читал видал реализацию на С++, n-мерных массивов путем хранения их как одномерных. И везде написано что обращение к двумерным массивам гораздо более медленное чем к одномерным. Шот какое то безумие выше описано. Либо опять таки спрашиваю это только особенность С# ?
     
  7. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    Ну про Кантора я как-то я не подумал, когда столкнулся с проблемой. Конечно я америку тут не открываю, просто небольшой велосипедик, трехколесный :D

    В моих задачах это не встречается. Я делал просто замену статических массивов.
     
  8. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    В некоторых задачах многомерные данные встречаются довольно часто (OLAP, статистика)

    Обращаю внимание, что алгоритм предназначался не для оптимизации скорости доступа (он безусловно выше в статическом массиве), а для снижения накладных расходов памяти по сравнению с реализацией на списках.
    НО если ты предложишь реализацию с более эффективным доступом, я буду только рад :)
     
  9. Algol

    Algol New Member

    Joined:
    29 May 2002
    Messages:
    1,759
    Likes Received:
    4
    Reputations:
    0
    Да, поддерживает.
     
  10. \\ChaOs//

    \\ChaOs// Member

    Joined:
    26 Feb 2009
    Messages:
    102
    Likes Received:
    26
    Reputations:
    5
    Неправда, можно обращаться к n-мерному массиву.
     
  11. cupper

    cupper Elder - Старейшина

    Joined:
    6 Jun 2007
    Messages:
    370
    Likes Received:
    92
    Reputations:
    5
    mas[a][c] ?
     
  12. \\ChaOs//

    \\ChaOs// Member

    Joined:
    26 Feb 2009
    Messages:
    102
    Likes Received:
    26
    Reputations:
    5


    Ага, mas[a1][a2][a3]...[aN]
     
Loading...