Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Общие вопросы по .NET и C# > Как можно увеличить размер массива?


Автор: ivashkanet 23.2.2006, 18:55
Как можно увеличить размер массива?

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

Задачу можно решить так:

Код

public void AddNewClass(string Name)
        {
            if (Clases != null)
            {
                Class[] Temp = Clases;
                int Len = Temp.Length;

                Clases = new Class[Len + 1];
                for (int i = 0; i < Len; i++)
                {
                    Clases[i] = Temp[i];
                }

                Clases[Len] = new Class(Name);
            }
            else
            {
                Clases = new Class[1];
                Clases[0] = new Class(Name);
            }
        }


Но поэлементное присваивание не очень эффективно.
Хотелось бы что нибудь вроде
Код

 Clases = new Class[Len + 1];
Clases = Temp
Clases[Len] = new Class(Name);


Но при использовании Clases = Temp в массив Clases передается не только элементы массива Temp, но и его размер.

Автор: Illuminaty 23.2.2006, 20:36
A готовый класс http://msdn.microsoft.com/library/default.asp?url=/library/en-us/cpref/html/frlrfsystemcollectionsarraylistclasstopic.asp не подойдет?

Автор: ivashkanet 23.2.2006, 21:18
Спасибо, Illuminaty, очень даже подошло!

P.S. Пока разбирался с ArrayList, нашел класс Hashtable, который подошел еще больше! Спаибо.

Автор: Illuminaty 23.2.2006, 21:52
Пожалуйста smile
Заходи еще

Автор: mr.DUDA 23.2.2006, 22:42
Эффективно увеличивать размер массива невозможно, если только массив не растёт с упреждающей скоростью. Поясню на примере: есть массив длиной 10 элементов. Надо добавить 11-й элемент. В памяти все 10 элементов идут друг за другом (так организован массив). Чтобы добавить 11-й, система создаёт новый пустой массив длиной в 11 элементов, копирует каждый элемент (что там у нас - ссылки на объекты C#, указатели на объекты C++, объекты С++, или что бы там ни было) в новый массив, и добавляет 11-й элемент в пустое место в конце массива. Вот так вот. Для оптимизации можно использовать алгоритм упреждающего резервирования: при выделении памяти на N элементов, всегда оставлять место для M дополнительных элементов. Именно так работает контейнер vector<T> в С++. Именно так организуется коллекция ArrayList в C#.

Автор: ivashkanet 4.3.2006, 01:18
Цитата

Нашёл через codeproject.com кульную вещь, просто в восторге - не могу не поделиться. Называется она Reflector, и является заменой убогому ildasm.exe. Позволяет не только бродить по сборке(-кам) с пом. сверхудобной системы навигации, но и дизассемблирует код сборки в C#/VB/Delphi/IL по выбору (очень интересно и познавательно было заглянуть в mscorlib, "написанный" на C# ). Утилка бесплатная.

В общем, кому интересно - качать и смотреть тут:
http://www.aisto.com/roeder/dotnet/


mr.DUDA, большое спасибо. Вещь не просто классная, она крутая smile (советую всем).

Так вот, с ее помощью дезассемблировал класс ArrayList.
Вот основные процедуры:
Код

public virtual int Add(object value)
{
      if (this._size == this._items.Length)
      {
            this.EnsureCapacity(this._size + 1);
      }
      this._items[this._size] = value;
      this._version++;
      return this._size++;
}

Процедура добавляет новый элемент к массиву. Если у нас зарезервировано место в массиве(а резервируется прилично), то все пучком. Если нет то тоже не беда: работает EnsureCapacity.
(Хоть это и функция (return int), лучше назвать её процедера, так как я не думаю, что возвращаемое значение можно где-то использовать smile )


Код

private void EnsureCapacity(int min)
{
      if (this._items.Length < min)
      {
            int num1 = (this._items.Length == 0) ? 4 : (this._items.Length * 2);
            if (num1 < min)
            {
                  num1 = min;
            }
            this.Capacity = num1;
      }
}

То же все предельно просто. Та самая
Цитата

Эффективно увеличивать размер массива невозможно, если только массив не растёт с упреждающей скоростью.

упреждающая скорость. Причем не хилая: 2-х кратный запас ячеек. (Так как они все null , то потери памяти нет (я не специалист но мне так кажется. Поправте меня, пожалуйста, если я ошибаюсь.)


Код

public virtual int Capacity
{
      get
      {
            return this._items.Length;
      }
      set
      {
            if (value != this._items.Length)
            {
                  if (value < this._size)
                  {
                        throw new ArgumentOutOfRangeException("value", Environment.GetResourceString("ArgumentOutOfRange_SmallCapacity"));
                  }
                  if (value > 0)
                  {
                        object[] objArray1 = new object[value];
                        if (this._size > 0)
                        {
                              Array.Copy(this._items, 0, objArray1, 0, this._size);
                        }
                        this._items = objArray1;
                  }
                  else
                  {
                        this._items = new object[4];
                  }
            }
      }
}

Свойство-функция (метод или как они там называются), которая реально и увеличивает размер (емкость) массива.

Код

[ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
public static void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length)
{
      Array.Copy(sourceArray, sourceIndex, destinationArray, destinationIndex, length, false);
}

Метод перенаправляет нас на другой перегруженный метод, который копирует все элементы одного массива в другой (почему нельзя было обойтись без него не знаю. Скорее всего проблема с доступом (я в этом пока не очень) первый метод public, в второй internal).


Код

[MethodImpl(MethodImplOptions.InternalCall), ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);

Очень интересная процедура, как она работает и где это она extern -- не известно. Но ясно одно -- как бы там она не работала, она работает, в среднем, в полтора раза быстрее, чем поэлементное копирование.

Выводы:
1. Основной прирост скорости работы происходит из-за роста массива с упреждающей скоростью.
2. Используется "неизвестная" процедура Copy.
Может это ноу-хау M$, хотя на мой взгляд ноу-хау в таких элементарных вопросах (копирование массивов) уже давно нет. Скорее всего она написана каким-то "хитрым кодом", и скорее всего написать его с помощью C# нельзя smile (опять же --только мое мнение, исправте, если я не прав, но зачем же еще скрывать её smile)

P.S. Надеюсь статья кому нибудь понравится. Еще раз спасибо, mr.DUDA, за Reflector. Знаю ее всего 2 дня, а уже люблю. smile

P.P.S. Исправьте меня, если я где-то не прав smile . Заранее, спасибо.

Автор: mr.DUDA 4.3.2006, 10:45
Цитата
Причем не хилая: 2-х кратный запас ячеек. (Так как они все null , то потери памяти нет

Ну место-то для объектов выделяется. Если это структуры, то память будет выделена сразу по N байт для M структур, если объекты - то по 4 байта для M объектов. Может и не 4, т.к. что там реально в Array хранится - одному CLR'у известно.

Цитата
Используется "неизвестная" процедура Copy.

Скорее всего дёргается memcpy ... smile


Автор: -ser- 4.3.2006, 11:29
как generic альтернативу ArrayList можно использовать List<T>

я полагал что у обоих механизм добавления элемента работает аналогично.

но вот что они пишут
Цитата

As elements are added to a Generic List, the capacity is automatically increased as required by reallocating the internal array

допустим, но читаем дальше
Цитата

The capacity can be decreased by calling TrimExcess or by setting the Capacity property explicitly. Note that decreasing the size requires reallocation and copying of all elements in the Generic List.

так почему в первом случае они не упоминали "and copying"? я подумал, может в случае с генериками они используют внутренний индекс? хотя тогда почему бы его не использовать и в случае уменьшения размера.

Автор: ivashkanet 4.3.2006, 17:27
Цитата(mr.DUDA @ 4.3.2006, 10:45 Найти цитируемый пост)
Скорее всего дёргается memcpy ...


А что такое memcpu??? smile

Автор: ivashkanet 4.3.2006, 22:39
smile

Классно!!! Я получил 1 балл репутации. smile

Но только вот что это, и кто мне его дал??? (Ну и естественно за что?)

Объясните, пожалуйста.

P.S. Что мне мешает создать нового юзера и "наплюсить" себу репутации????

Автор: mr.DUDA 4.3.2006, 22:56
Цитата(ivashkanet @ 4.3.2006, 21:39 Найти цитируемый пост)
Классно!!! Я получил 1 балл репутации. 

Но только вот что это, и кто мне его дал??? (Ну и естественно за что?)

Объясните, пожалуйста.

Это я тебе плюс поставил за пример, как создавать собственные snippets для Visual Studio 2005... Никакого отношения к текущей теме этот плюс не имеет. Чтобы посмотреть, кто и за что тебе ставит плюс, просто нажми на ссылку "Репутация" у себя.

Цитата(ivashkanet @ 4.3.2006, 21:39 Найти цитируемый пост)
P.S. Что мне мешает создать нового юзера и "наплюсить" себу репутации????

Тебе помешает администрация. За такие игры реально получить полный БАН по IP-адресу. Играть с этим не советую...

Автор: arilou 5.3.2006, 01:14
ivashkanet, вот такая вот фигня, ой, атрибут smile..

вобщем,
Код

[MethodImpl(MethodImplOptions.InternalCall)]

означает, что реализация метода находится "внутри" инфраструктуры фреймворка, и написана она в unmanaged коде. Можешь скачать ROTOR (реализация CLR, доступная под лицензией shared source), и посмотреть. Там очень много методов "MethodImplOptions.InternalCall"

http://msdn.microsoft.com/net/sscli/

Автор: ivashkanet 5.3.2006, 11:18
Спасибо, arilou, но мне хватит и .Net. А в дебри CLR я пока лезть не хочу.
Маленький (в смысле новичок) ещё smile .

Автор: ivashkanet 15.12.2006, 08:51
Страшный, вопиющий smile + еще и некрофилизм  smile 

Но это мое первое сообщение/тема на форуме  smile 

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)