ANTICHAT.XYZ    VIDEO.ANTICHAT.XYZ    НОВЫЕ СООБЩЕНИЯ    ФОРУМ  
Баннер 1   Баннер 2
Antichat снова доступен.
Форум Antichat (Античат) возвращается и снова открыт для пользователей. Здесь обсуждаются безопасность, программирование, технологии и многое другое. Сообщество снова собирается вместе.
Новый адрес: forum.antichat.xyz
Вернуться   Форум АНТИЧАТ > Программирование > С/С++, C#, Delphi, .NET, Asm
   
Ответ
 
Опции темы Поиск в этой теме Опции просмотра

[C#] Эффективное хранение многомерных массивов
  #1  
Старый 20.01.2010, 13:12
Аватар для Algol
Algol
Регистрация: 29.05.2002
Сообщений: 1,793
Провел на форуме:
2050916

Репутация: 0


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

Проблематика:
Для хранения многомерных данных в 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
(где / - целочисленное деление, % - деление по модулю)

Реализация:
Ниже приведена реализация многомерного массива основанного на одномерном массиве для хранения данных и методе сигнатуры, для преобразования многомерных индексов в одномерный.

Код:
    /// <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[,,,,]

Последний раз редактировалось Algol; 25.01.2010 в 11:17..
 
Ответить с цитированием

  #2  
Старый 20.01.2010, 18:26
Аватар для nerezus
nerezus
Pagan Heart
Регистрация: 12.08.2004
Сообщений: 3,791
Провел на форуме:
6490435

Репутация: 2290


Отправить сообщение для nerezus с помощью ICQ
По умолчанию

Эм, а смысл использовать это, а не обыкновенный массив, если мы не можем сделать так(псевдокодом):
m[2,3,4].append([[45],[3,4]])
Т.е. по сути у нас получается обыкновенный n-мерный массив, только с другой системой хранения.
 
Ответить с цитированием

  #3  
Старый 20.01.2010, 19:24
Аватар для Algol
Algol
Регистрация: 29.05.2002
Сообщений: 1,793
Провел на форуме:
2050916

Репутация: 0


По умолчанию

Цитата:
Сообщение от nerezus  
Эм, а смысл использовать это, а не обыкновенный массив, если мы не можем сделать так(псевдокодом):
m[2,3,4].append([[45],[3,4]])
псевдокода не понял )

Цитата:
Сообщение от nerezus  
Т.е. по сути у нас получается обыкновенный n-мерный массив, только с другой системой хранения.
Так и есть, разница только в том, что размерность (число измерений) в MultiDimensionalArray может быть задана в рантайме.

То есть например так:
Код:
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
Немного поправил статью, что бы было понятно, что речь идет о числе измерений, а не о числе элментов в каждом измерении.

Последний раз редактировалось Algol; 20.01.2010 в 19:31..
 
Ответить с цитированием

  #4  
Старый 20.01.2010, 20:20
Аватар для Root-access
Root-access
Участник форума
Регистрация: 18.06.2008
Сообщений: 222
Провел на форуме:
2223440

Репутация: 648
Отправить сообщение для Root-access с помощью ICQ
По умолчанию

В данной заметке ценность для кого-то представляет реализация.
Ведь саму процедуру придумал Кантор больше ста лет назад.
Правда он строил изоморфизм из произведения счётных, а не конечных множеств в счётное множество...

Цитата:
Эм, а смысл использовать это, а не обыкновенный массив, если мы не можем сделать так(псевдокодом):
m[2,3,4].append([[45],[3,4]])
Я тоже не до конца понял псевдокода... Мы добавляем к массиву m ещё один массив?

Цитата:
Немного поправил статью, что бы было понятно, что речь идет о числе измерений, а не о числе элментов в каждом измерении.
Кстати да, проблемы начнутся тогда, когда надо будет динамически менять число элементов в массиве...
 
Ответить с цитированием

  #5  
Старый 20.01.2010, 20:42
Аватар для Retimiled
Retimiled
Banned
Регистрация: 24.12.2009
Сообщений: 141
Провел на форуме:
487460

Репутация: 45
По умолчанию

все хорошо .... алгоритм нужный , и пусть физики и математики нет для 5-го измерения .... !

для Си шарпа сойдет ... а для серьезных вещей умножение и деление меняется на сдвиги и в размерах(размерности) дополнение в большую сторону до степени 2-ки(для тех самых сдвигоф)! (если заводили речь о скорости)

Последний раз редактировалось Retimiled; 20.01.2010 в 20:52..
 
Ответить с цитированием

  #6  
Старый 20.01.2010, 21:31
Аватар для cupper
cupper
Постоянный
Регистрация: 06.06.2007
Сообщений: 575
Провел на форуме:
1180737

Репутация: 180


По умолчанию

Цитата:
Время доступа по индексам – в 8 раз медленнее чем int[,,,,]
я чета не понял, а че C# поддерживает обращение по индексу в более чем 2-х размерном миссиве ? Это чисто фича С#, ведь в С/C++ таким образом можно обратиться максимум к двумерному массиву, и все. Притом где то даже читал видал реализацию на С++, n-мерных массивов путем хранения их как одномерных. И везде написано что обращение к двумерным массивам гораздо более медленное чем к одномерным. Шот какое то безумие выше описано. Либо опять таки спрашиваю это только особенность С# ?
 
Ответить с цитированием

  #7  
Старый 20.01.2010, 22:06
Аватар для Algol
Algol
Регистрация: 29.05.2002
Сообщений: 1,793
Провел на форуме:
2050916

Репутация: 0


По умолчанию

Цитата:
Сообщение от Root-access  
В данной заметке ценность для кого-то представляет реализация.
Ведь саму процедуру придумал Кантор больше ста лет назад.
Правда он строил изоморфизм из произведения счётных, а не конечных множеств в счётное множество...
Ну про Кантора я как-то я не подумал, когда столкнулся с проблемой. Конечно я америку тут не открываю, просто небольшой велосипедик, трехколесный

Цитата:
Сообщение от Root-access  
Кстати да, проблемы начнутся тогда, когда надо будет динамически менять число элементов в массиве...
В моих задачах это не встречается. Я делал просто замену статических массивов.
 
Ответить с цитированием

  #8  
Старый 20.01.2010, 22:13
Аватар для Algol
Algol
Регистрация: 29.05.2002
Сообщений: 1,793
Провел на форуме:
2050916

Репутация: 0


По умолчанию

Цитата:
Сообщение от Retimiled  
все хорошо .... алгоритм нужный , и пусть физики и математики нет для 5-го измерения .... !
В некоторых задачах многомерные данные встречаются довольно часто (OLAP, статистика)

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

  #9  
Старый 20.01.2010, 22:14
Аватар для Algol
Algol
Регистрация: 29.05.2002
Сообщений: 1,793
Провел на форуме:
2050916

Репутация: 0


По умолчанию

Цитата:
Сообщение от cupper  
я чета не понял, а че C# поддерживает обращение по индексу в более чем 2-х размерном миссиве ?
Да, поддерживает.
 
Ответить с цитированием

  #10  
Старый 20.01.2010, 23:21
Аватар для \\ChaOs//
\\ChaOs//
Познающий
Регистрация: 26.02.2009
Сообщений: 65
Провел на форуме:
583734

Репутация: 34
Отправить сообщение для \\ChaOs// с помощью ICQ
По умолчанию

Цитата:
Сообщение от cupper  
... ведь в С/C++ таким образом можно обратиться максимум к двумерному массиву...
Неправда, можно обращаться к n-мерному массиву.
 
Ответить с цитированием
Ответ



Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Sale of ICQ Hertz ICQ - Покупка, продажа 1 28.09.2009 04:27



Здесь присутствуют: 1 (пользователей: 0 , гостей: 1)
 


Быстрый переход




ANTICHAT.XYZ