|
Страница 4 из 4
ArrayList – неоднородный массив переменного размера Несмотря на то, что обычные массивы, безусловно, находят широкое применение, они накладывают определенные ограничения на программиста, поскольку каждый массив может хранить данные только одного типа (однородность) и вдобавок перед использованием массива вы должны выделить (allocate) определенное количество элементов. Однако, часто разработчикам хочется чего-то более гибкого — простую коллекцию объектов потенциально разного типа, с которыми можно было бы просто работать, не беспокоясь о вопросах, связанных с выделением элементов(allocation). Базовая библиотека классов .NET Framework содержит такую структуру данных. Она называется System.Collections.ArrayList. В кусочке кода, приведенном ниже, демонстрируется ArrayList в действии. Заметьте, что если мы используем ArrayList, то мы можем добавить в него любой тип, причем никаких действий по выделению памяти выполнять не требуется. На деле получается, что в ArrayList могут быть добавлены элементы любого типа. Более того, нам больше не нужно заботиться об изменении размера ArrayList. Все эти действия производятся для нас за кулисами. ArrayList countDown = new ArrayList();
countDown.Add(5);
countDown.Add(4);
countDown.Add(3);
countDown.Add(2);
countDown.Add(1);
countDown.Add("blast off!");
countDown.Add(new ArrayList());
А за кулисами ArrayList использует System.Array типа object. Поскольку все типы являются прямыми или непрямыми наследниками object, массив экземпляров типа object может содержать элементы произвольного типа. По умолчанию ArrayList создает массив из 16 элементов типа object, хотя точный размер может быть указан через параметр конструктора в свойстве Capacity. При добавлении элемента с помощью метода Add() число элементов во внутреннем массиве сверяется с размером массива. Если операция добавления элемента вызывает превышение числа элементов массива над его размером, то размер автоматически удваивается(redimensioned). ArrayList, как и обычный массив, использует индекс для доступа к своим элементам с помощью аналогичного синтаксиса: // чтение элемента
int x = (int) countDown[0];
string y = (string) countDown[5];
// запись данных
countDown[1] = 5;
// ** БУДЕТ СГЕНЕРИРОВАНО ИСКЛЮЧЕНИЕ ArgumentOutOfRange **
countDown[7] = 5; Поскольку ArrayList хранит массив объектов, вы должны явным образом привести (explicitly cast) считанное из ArrayList значение к тому типу данных, который хранился в данном элементе ArrayList-а. Также заметьте, что если вы попытаетесь сослаться на элемент ArrayList-а номер, которого больше, чем размер ArrayList-а, будет сгенерировано исключение System.ArgumentOutOfRange. Хотя ArrayList обеспечивает дополнительную гибкость по сравнению с обычным массивом, достигается эта гибкость за счет скорости работы, особенно если вы храните в ArrayList-е размерные типы (value types). Вспомните, что массив размерных типов — таких как System.Int32, System.Double, System.Boolean, и т.д. — хранится в непрерывной области памяти управляемой кучи в распакованной форме (unboxed form). Внутренний массив ArrayList-а при этом является массивом ссылок на экземпляры типа object. Поэтому, даже если ваш ArrayList не хранит ничего, кроме размерных типов, каждый элемент ArrayList-а является ссылкой на упакованный размерный тип (boxed value type), как показано на Рисунке 3. Рисунок 3. ArrayList содержит непрерывную область ссылок на экземпляры типа object Процессы упаковки и распаковки, наряду с наличием дополнительных накладных расходов при хранении размерных типов в ArrayList-е, могут негативно сказаться на производительности вашего приложения при использовании больших ArrayList-ов с большим количеством операций чтения/записи. Как показывает Рисунок 3, использование памяти для ссылочных типов выглядит одинаково как в случае использования обычных массивов, так и ArrayLists-ов. Автоматическое изменение размера ArrayList-а не должно вызывать ухудшения производительности по сравнению с массивом. Если вам известно точно число элементов, которое должно храниться в ArrayList-е, вы просто можете отключить автоматическое изменение размера, указав начальный размер в конструкторе ArrayList-а. Если точный размер вам неизестен, даже в случае использования массива, вам понадобиться увеличивать его размер, если число вставляемых элементов превышает размер массива. Классической задачей computer science является определение того, сколько места необходимо выделять при окончании памяти в некотором буфере (области памяти). Одно решение соcтоит в том, чтобы дополнительно выделить только один элемент из памяти буфера. Т.е. при добавлении элемента в заполненный массив из 5 элементов, размер массива станет равным шести. Очевидно, что данный подход является наиболее экономным, однако он может быть слишком дорогостоящим, потому что за каждой вставкой нового элемента после заполнения массива следует изменение его размера. Диаметрально противоположный подход состоит в увеличении размера массива в 100 раз при окончании наличия свободного места в нем для вставки новых элементов. Т.е. после заполнения массива из 5 элементов при попытке добавления 6-го элемента размер массива будет изменен до 500 элементов. Ясно, что такой подход грандиозно уменьшает число изменений размера массива, однако если лишь немного элементов будут добавлены в массив, огромное количество свободной памяти будет потрачено впустую. Проверенным на практике компромиссом решения данной проблемы является простое удвоение текущего размера массива, когда кончается свободное место для новых элементов. Т.е. для массива, в котором было изначально выделено 5 элементов, добавление шестого элемента вызовет увеличение размера массива до 10 элементов. Это как раз и делает класс ArrayList и, что самое приятное, он делает все это за вас. Асимптотическое время исполнения операции ArrayList-а такое же, как и у обычного массива. Несмотря на то, что при работе с ArrayList-ом действительно возникают дополнительные накладные расходы, особенно при хранении размерных типов, соотношение между числом элементов ArrayList-а и стоимостью выполнения операций не отличается от стандартного массива.
Заключение Данная статья открыла обсуждение структур данных, фокусируясь на том, почему изучение струтур данных важно. Были описаны способы анализа эффективности использования структур данных. Этот материал важен для подсчета времени исполнения различных операций структур данных и является полезным инструментом при выборе той или иной структуры данных для конкретной программистской задачи. После изучения того, как следует анализировать структуры данных, мы обратились к исследованию двух наиболее распространенных структур данных в базовой библиотеке классов .NET Framework — классам System.Array и System.Collections.ArrayList. Массивы позволяют хранить непрерывный блок однородных типов. Основное их преимущество состоит в исключительно малом времени доступа к своим элементам для чтения и записи. Слабое место массивов – дороговизна поиска в них, т.к. при поиске в неотсортированном массиве мы потенциально должны посетить каждый элемент массива. ArrayList является более гибкой массивоподобной структурой данных. Он может содержать данные различных типов, используя массив object-ов. Более того, ArrayList не требует явного выделения элементов и может самостоятельно расширяться по мере добавления элементов. В следующей статье нашей серии мы обратим внимание на классы Stack и Queue. Мы также рассмотрим ассоциативные массивы (associative arrays), которые представляют собой массивы, элементы которых индексируются не целочисленным, а строковым значением. Ассоциативные массивы присутствуют в базовой библиотеке классов .NET Framework в виде класса Hashtable.
Перевод — Станислав Воног, Московский физико-технический институт |