Анимация
JavaScript


Главная  Библионтека 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 [ 43 ] 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85

(конечно, не считая заполнения для выравнивания; заметим, что в случае вектора "последовательное размещение" имеет тот же смысл, что и у С-массива, как показано на рис. 21.2).

• deque<T> можно рассматривать как vector<T>, чья внутренняя память разделена на части. deque<T> хранит блоки, или "страницы" объектов; реальный размер страниц стандартом не определяется и зависит в первую очередь от размера объекта т и от выбора, сделанного разработчиком вашей стандартной библиотеки. Такое разбиение на страницы требует хранения одного дополнительного указателя на страницу, что приводит к дополнительным расходам, составляющим доли бита на один объект. Напри.мер, в системе с 8-битовыми байтами и 4-битовыми целыми числами и указателями deque<int> с 4-Кбайтовой страницей приводит к расходам памяти, равным 1/32=0.03125 бита на один int. Других накладных расходов не имеется, поскольку deque<T> не хранит никаких дополнительных указателей или другой информации для отдельных объектов т. В стандарте нет требования, чтобы страницы deque<T> представляли собой С-массивы, однако это - общепринятый способ реализации.

• 1ist<T> представляет собой двухсвязный список узлов, хранящих элементы типа т. Это означает, что для каждого элемента т в 1ist<T> хранятся также два указателя на предьщущий и последующий узлы в списке. Каждый раз при вставке нового элемента т мы также создаем два указателя, так что list<T> требует как минимум двух указателей накладных расходов памяти на один элемент.

• set<T> (а также аналогичные в этом отношении mu1tiset<T>, тар<кеу,т> и multimap<Key,T>) тоже хранят узлы, в которых содержатся объекты типа т (или pai r<const Key ,т>). Обычная реализация set представляет собой дерево с тремя дополнительными указателями на один узел дерева. Зачасгую, услышав об этом, многие спрашивают: "Почему три указателя? Разве недостаточно двух -- на левый и правый дочерние узлы?" Дело в том, что требуется еще один указатель на родительский узел, иначе задача определения "следующего" узла по отношению к некоторому произвольно взятому не может быть решена достаточно эффективно. (Возможны и другие способы реализации этих контейнеров; например, можно использовать т.н. alternating skip list - но и в этом случае требуется как минимум три указателя на каждый элемент (см. [МагпеОО]).)

В табл. 21.1 приведены дополнительные расходы памяти на хранение одного элемента в различных стандартных контейнерах. Заметим, что иногда можно снизить расходы на хранение объектов, перенеся их на итераторы - т.е. часть работы может быть перенесена в итераторы, что даст нам "толстые" итераторы в обмен на "худые" контейнеры. Впрочем, я не знаком ни с одной коммерческой реализацией стандартной библиотеки, которая бы придерживалась этой методики.

Таблица 21.1. Дополнительные расходы памяти на хранение одного объекта

у разных контейнеров

Контейнер

Типичные накладные расходы памяти на один хранимый объект

vector

Нет дополнительных расходов

deque

Пренебрежимо малые расходы - обычно доли битов

list

Два указателя

set, multiset

Три указателя

map, multimap

Три указателя на pai r<const кеу, т>



Память и стандартные контейнеры: практика

Теперь мы перейдем к самой интересной части. Не будем спешить делать выводы из табл. 21.1. Например, исходя из приведенных данных, вы можете сделать вывод б том, что list требует меньших расходов памяти, чем set - ведь первому требуется только два дополнительных указателя, а последнему - три. Интересно, что это может оказаться неверным, если принять во внимание стратегию распределения памяти.

Рассмотрим вопрос более детально, для чего обратимся к табл. 21.2. в которой приведены типичные структуры узлов, используемые реализациями list, set/ multiset и map/multimap.

Таблица 21.2. Блоки динамической памяти, используемые для хранения объектов в разных контейнерах

Контейнер

Типичные блоки памяти для хранения объектов

vector

Отсутствуют; объекты игщивидуально не хранятся

deque

Отсутствуют; объекты хранятся в страницах; почти все страницы хранят большое количество объектов

list

struct LNode { LNode* prev;

LNode* next; T object;

set, multiset

struct SNode {

SNode* prev;

SNode* next;

SNode* parent;

T object; }; или эквивалентная структура

map, multimap

struct MNode { MNode* prev; MNode* next; MNode* parent;

std::pair<const Key, T> data; }; Или эквивалентная структура

Теперь рассмотрим, что происходит в реальной ситуации при приведенных далее предположениях, которые справедливы для большинства расп ро с тра н с н и ы х в настоящее время платформ.

• Указатели и целые числа имеют размер 4 байта (типично для 32-битовых платформ).

• si zeof (stri ng) равно 16. Заметим, что это просто размер непосредственно объекта stri ng, здесь не учитываются буферы данных, которые могут быть выделены строке; количество и размер внутренних буферов string варьируется от реализации к реализации, но это не влияет на приведенные далее сравнительные результаты. (Рассматриваемое значение si zeof (stri ng) представляет собой реальную величину, взятую из одной распространенной реализации стандартной библиотеки.)

• Стратегия распределения памяти по умолчанию использует выделение блоков фиксированного размера; размеры блоков кратны 16 байтам (типичное распределение памяти в Microsoft Visual С-ь+).



Таблица 21.3. Реальные расходы памяти на хранение объекта, рассматриваемые в предположении, что sizeof (string) == 16, указатели и int имеют размер 4 байта, и выделение памяти происходит 16-байтовыми блоками

Контейнер

Теоретический размер данных узла

Реальный размер блока выделенной для узла

памяти (с учетом выравнивания и накладных расходов при вьщелении памяти)

list<char>

9 байтов

16 байтов

set<char>, mu1tiset<char>

13 байтов

16 байтов

list<int>

12 байтов

16 байтов

set<int>, multiset<int>

16 байтов

16 байтов

1ist<stri ng>

24 байта

32 байта

set<string>, multiset<stri ng>

28 байтов

32 байта

В табл. 21.3 приведены результаты простого анализа с использованием рассмотренных выше предположений. Вы можете повторить эксперимент на своей платформе со своим компилятором - просто подставив собственные значения. Чтобы написать программу, которая определяет реальные накладные расходы при выделении блока определенного размера на вашей платформе, обратитесь к приложению 3 в книге Джона Бентли (Jon Bcntlcy) [BentleyOO].

Благодаря табл. 21.3 мы немедленно обнаруживаем один интересный результат: во многих случаях - примерно для 75% всех возможных размеров типа т - накладные расходы при использовании 1 i st и set/mul ti set в рассматриваемой среде оказываются одинаковы. Более того, вот результат, который еше интереснее, - list<char> и set<int> имеют в данной среде одни и тс же реальные накладные расходы, несмотря на то, что последний контейнер хранит данные большего размера и требует большего количества дополнительной информации для каждого узла.

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

Резюме

Для каждого вида контейнера определяются свои компромиссы между расходами памяти и производительностью. При использовании vector и set можно быстро решить те задачи, которые невозможно столь же эффективно решить при использовании 1 ist - например, поиск за время 0(log N); при использовании vector можно сделать веши, невозможные при применении list или set - например, произвольный доступ. Вставка элемента в средину легко выполняется в 1 i st, менее эффективно-в set, и очень медленно - в vector. Словом, примеров таких по-разному выполняющихся задач очень много. Большая гибкость зачастую требует больших накладных расходов памяти, но если учесть выравнивание данных и возможные стратегии распределения памяти, то различие может оказаться куда меньшим, чем вы думаете! Вопросы выравнивания данных и оптимизации использования памяти рассматривались также в книге [SutterOO].

Если содержимое вектора отсортировано. Задача 21. Контейнеры в памяти. Часть 2: какие они на самом деле?



0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 [ 43 ] 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85