Как узнать размер памяти, выделенной для карты?
Есть ли способ найти количество / размер памяти, выделенной для карты в С ++? Есть функция для определения размера карты, т. Е. Количества записей на карте, но есть ли такой метод для памяти. У меня есть карта (строка, строка). Sizeof () всегда дает мне размер 48. По какой причине это так? Спасибо 🙂
5 ответов
Вот что я сделал (в соответствии с предложением Дэймона), что зависит от реализации malloc. В glibc / linux позиция сразу за возвращаемым указателем дает размер выделения, поэтому можно использовать следующий код для отслеживания выделенных / освобожденных байтов:
И использование идет следующим образом:
Надеюсь, это кому-то поможет.
Примечание: это не предназначалось для использования в производственной среде, так как мой новый не является реентерабельным. Тем не менее, я успешно запустил его во время многопоточного модульного тестирования.
Общий размер, используемый картой =
Map.size () даст количество записей на карте
Все стандартные библиотечные контейнеры по умолчанию распределяются с использованием «распределителя по умолчанию», который представляет собой не более чем структуру / класс с парой функций-оберток вокруг new и delete (которые сами по себе внутренне немного больше чем оболочки вокруг malloc и free с небольшим выравниванием и приведением типа во многих компиляторах).
Если по какой-либо причине вас не устраивает распределитель по умолчанию, вы можете предоставить настраиваемый распределитель для шаблона контейнера, и он будет просто без проблем использовать его.
Как узнать размер map c
максимальный элемент в C++ map
Нам дан C++ map m; Как эффективно вычислить максимальное x, такое что m[x]!=0 и какая асимптотика одного такого вычисления?
Мне в голову приходит запустить цикл for с реверс-итератором и т.к. элементы упорядочены(?), то первое значение как раз и будет x. Даже если это работает, то я совсем не уверен, что это эффективный метод.
Сразу оговорюсь, я пока плохо разбираюсь в структурах данных. Объясните, пожалуйста, почему O(1), а не logN?
Вот здесь указана complexity этого метода.
для std::map инкремент или декремент итератора работает в худшем случае за логарифм, из-за это куча людей получает TLE на контестах
Спасибо. Единственное, что еще следует учесть — если ты какому-то элементу явно присвоил значение 0, то это может не работать. Знатоки C++, пожалуйста прокомментируйте это утверждение.
Стоит учесть, что при обращении к елементу ему автоматически присваивается значение 0
Размеры и масштабы
Это одна из самых важных статей для начинающего маппера, которая поможет понять, какого размера необходимо создавать объекты, чтобы они казались реальными. Например, какой высоты нужно сделать стену, чтобы она равнялась 1 этажу или какой высоты должна быть дверь, чтобы игрок мог в нее пройти и т.п. Также Вы узнаете о максимально возможных размерах карты.
Единицы измерения в Half-Life и редакторе
Размеры (длина, ширина, высота) и расстояние в Half-Life измеряются в юнитах (unit) — некой виртуальной единице измерения длины. Размеры в редакторе карт измеряются также в юнитах, что позволяет видеть карту такой, какой она будет в игре.
Минимальной единицей длины, высоты и ширины является 1 юнит. А это значит, что самый маленький объект на карте может иметь размеры 1х1х1 юнит.
Максимальный размер карты в Half-Life
В Half-Life максимальный размер карты может составлять 8192х8192х8192 юнита. Именно такой размер имеет рабочее пространство в редакторе карт. Данное пространство можно представить в виде куба со стороной 8192 юнита (см. рис. ниже).
В центре этого воображаемого куба находится начало координат, которое в 3D-виде обозначается цветными перпендикулярными линиями, а на 2D-видах — зелеными. Обычно, карту начинают строить около начала координат, т.е. в центре куба.
Для сравнения максимально возможного размера карты с существующими известными картами приведем несколько примеров.
- Длина: 6032 (отсчет от базы CT до T)
- Длина: 6208 (отсчет от базы CT до T)
Из приведенных примеров видно, что по длине эти карты занимают
75% пространства, по ширине: 41% (ацтек) и 68% (даст), по высоте: 21% (ацтек) и 10% (даст). Исходя из этих данных, можно сделать вывод, что типичные карты занимают от 55 до 65% свободного пространства.
Создание объектов нужного размера
Размер объектов в редакторе очень просто контролировать по клеткам. Но сначала нужно определить шаг сетки (размер каждой клетки). Посмотреть его можно в строке состояния, в самой правой ее части, после слова «Grid:».
Например, Grid: 16 означает, что шаг сетки равен 16 юнитам. Увеличение/уменьшение шага сетки осуществляется кнопками «[» и «]». Запомните эти кнопки, Вы будете часто их использовать.
На рисунке ниже видно, как действует данная функция: шаг сетки уменьшается, а приближение (zoom) остается постоянным. Эта функция нужна для более точного определения размера объекта. Например, если нам надо сделать ящик в 64 юнита, то удобно поставить шаг сетки в 16 юнитов и отсчитать 4 клетки. Если нужно сделать бортик высотой 24 юнита, то здесь удобнее выставить шаг сетки в 8 юнитов и отсчитать 3 клетки и т.п.
Теперь посмотрим на вторую функцию, управляющую внешним видом сетки — это приближение. Здесь все просто: шаг сетки одинаковый, а просто происходит увеличение (уменьшение) изображения. Для изменения приближения пользуйтесь кнопками «+» и «–» на дополнительной клавиатуре.
Шаг сетки и другие ее параметры можно изменить в меню «Options/2D views» (см. рис. ниже).
Ну, чтож, теперь Вы знаете, как управлять координатной сеткой и отсчитывать размеры объектов.
Примеры размеров на картах
Итак, вернемся к юнитам. С чем можно сравнить юнит из реальной жизни? Скорее всего, с дюймом (2,54 см), но точного ответа Вам никто не даст (может быть, только в Valve 🙂 Косвенно подтвердить нашу догадку может высота игрока в Half-Life, которая составляет 72 юнита или в переводе на сантиметры — 180 см, что вполне сопоставимо с ростом человека. Кстати говоря, высота игрока в CS чуть меньше — 64 юнита или 160 см, что для спецназовца явно маловато :)))
Теперь приведем несколько примеров, демонстрирующих различные размеры на картах.
Для начала неплохо бы посмотреть, какие бывают максимальные расстояния на стандартных картах (возьмем Ацтек и Даст). Приведенный ниже пример должен остановить Вас, если Вы захотите сделать открытое пространство более 2600 юнитов 🙂 Просто слишком большие открытые пространства лишают карту стратегичности, превращая ее в AWP-арену.
Ширина спуска под мост (256 юнитов):
Размер ящика у входа в кишку (128 юнитов):
Ширина ступенек на базе T (224 юнита):
Длина моста на Ацтеке (720 юнитов):
Расстояние в воде (2240 юнитов):
Ширина ворот (256 юнитов):
Высота ступенек (16 юнитов):
Размеры стандартных объектов
Для часто встречающихся объектов таких как: двери, лестницы, окна и др. определены более-менее стандартные (лучше сказать, оптимальные) размеры, которые воспринимаются в игре, как реальные.
1. Двери (дверные проемы)
Высота: 96
Ширина: 64
Толщина: 4-8
2. Окна (оконные проемы)
Высота: 64
Ширина: 48
Ширина: 32
Толщина: 4
При постройке обычных лестниц высоту ступеньки делают равной 16 юнитов (если больше, то игрок не сможет залесть на нее без прыжка), а длину — 16-32 юнита (см. рис. ниже).
На рисунке ниже представлены основные размеры ящиков со сторонами 128, 96, 64 и 48 юнитов в сравнении с игроком высотой 72 юнита (в CS игрок — 64 юнита, т.е. его рост точно равен высоте второго справа ящика).
Толщина стен, обычно, 16-32 юнита;
Высота стандартной комнаты 128-144 юнита.
Gameplay-размеры
При постройке карт необходимо учитывать не только пропорции и размеры объектов, чтобы они не казались нам чрезмерно большими или слишком маленькими, но и размеры, влияющие на геймплей. Например, если между двумя стенами сделать не достаточно большое расстояние, то игрок не сможет между ними пройти или, второй пример, расстояние между крышами домов слишком велико, тогда игрок может разбиться, недопрыгнув.
Ниже мы приводим основные gameplay-размеры для Half-Life.
Замечание: для CS данные о максимальной дальности прыжков поменьше.
Высота преграды, которую игрок способен преодолеть без прыжка:
(такой преградой могут быть ступеньки лестницы или бортик)
Минимальная высота между землей и объектом, позволяющая игроку пройти:
(это могут быть дверные или оконные проемы, вентиляционная шахта, люк и т.п.)
Минимальное расстояние между объектами, позволяющее игроку пройти между ними:
Максимальная высота объекта, на которую игрок способен запрыгнуть:
Максимальная дальность прыжка на ровной поверхности:
Повреждения, получаемые игроком при падении с разных высот:
128 юнитов — 0%
192 юнита — 9-10%
256 юнитов — 27-28%
320 юнитов — 43-44%
384 юнита — 57-58%
448 юнитов — 70-71%
512 юнитов — 82-83%
576 юнитов — 93-95%
640 юнитов — 100% Death 🙂
Размеры CLR-объектов. Точное определение
Предисловие
Ниже приведена внутренняя структура CLR-объектов:
Первоначально значение SyncBlock равно нулю. Однако в SyncBlock может хранится хеш-код объекта (при вызове метода GetHashCode), или номер записи syncblk, который помещает в заголовок объекта среда при синхронизации (использование lock, либо напрямую Monitor.Enter).
Каждый тип имеет свой MethodTable, и все экземпляры объектов одного и того же типа ссылаются на один и тот же MethodTable. Данная таблица хранит информацию о самом типе (интерфейс, абстрактный класс и т.д.).
Reference type pointer — ссылка на объект, хранящаяся в переменной, размещенной в стеке со смещением 4.
Остальное представляет собой поля класса.
Перейдем от теории к практике. Стандартными средствами CLR невозможно установить размер объекта. Да есть оператор sizeof в C#, но предназначен он для установления размера unmanaged-объектов, а также размеров value types. В вопросах ссылочных типов – бесполезен.
Именно для этих целей существует расширение дебаггера Visual Studio – SOS (Son of Strike).
Перед началом использование необходимо разрешить unmanaged code debugging:
Для активации SOS, во время отладки необходимо открыть VS > Debug > Windows > Immediate Window и ввести следующее:
.load sos.dll
После чего увидим его успешную загрузку:
Для демонстрации создадим простое консольное приложение и напишем класс MyExampleClass:
Возьмем калькулятор и посчитаем предполагаемый размер для экземпляра класса – пока что 64 байт.
Однако помните в начале статьи про структуру объектов? Так вот окончательный размер будет равен:
CLR-объект = SyncBlock (4) + TypeHandle (4) + Fields (64) = 72
Проверим теорию.
Добавим следующий код:
И запустим отладку (F5).
Введем следующие команды в Immediate Window:
.load sos.dll
!DSO
Ну что же, размер myObject составляет 72 байта. Не так ли?
Ответ нет. Дело в том, что мы забыли еще добавить размер строки переменной StringValue. Ее 4 байта – это только ссылка. А вот истинный размер мы сейчас и проверим.
Таким образом, настоящий размер myObject составляет 100 байт.
Дополнительные 28 байт занимает переменная StringValue.
Однако проверим это. Для этого используем адрес переменной StringValue 01b8c008:
Из чего складывается размер System.String?
Во-первых, в CTS символы (тип System.Char) представлены в Unicode и занимают 2 байта.
Во-вторых, строка – есть не что иное, как массив символов. Так в StringValue мы записали значение “String”, что равно 12 байт.
В-третьих, System.String – ссылочный тип, а это значит, что располагается он в GC Heap, и будет состоять из SyncBlock, TypeHandle, Reference point + остальные поля класса. Reference point здесь браться в расчет не будет, т.к. уже посчитан в самом классе MyExampleClass (ссылка 4 байта).
В-четвертых, структура System.String выглядит следующим образом:
Дополнительные поля класса составляют переменные m_stringLength типа Int32 (4 байта), m_firstChar типа Char (2 байта), переменная Empty считаться не будет, т.к. является пустой статичной строкой.
Также обратим внимание на размер – 26 байт вместо 28, посчитанных ранее. Сложим все вместе:
StringValue = SyncBlock (4) + TypeHandle (4) + m_stringLength (4) + m_firstChar (2) + “String” (12) = 26
Дополнительные 2 байта образуются из-за выравнивания, производимого менеджером памяти CLR.
x86 vs. x64
Основное различие заключается в размере DWORD – указателя памяти. В 32-битных системах он составляет 4 байта, в 64-битных уже 8 байт.
Так, если пустой класс будет равен в x86 лишь 12 байт, то в x64 уже 24 байта.
Лимит размеров CLR-объектов
Принято считать, что размер System.String ограничено лишь доступной системной памятью.
Однако любой экземпляр любого типа не может занимать более 2 Gb памяти. И это ограничение распространяется как на x86, так и x64 системы.
Так, List, хотя и имеет метод LongCount(), это не означает возможности расположить 2^64 объектов. Решением может быть использование класса BigArray, предназначенного для этих целей.
Послесловие
В большинстве своем вопрос размера объектов, их выравнивания в памяти приходят только при сильной необходимости – возможности оптимизации использования ресурсов.
Надеюсь, статья оказалась интересной и полезной. Спасибо за внимание!
О реализации структуры данных Map в V8
Объект Map должен быть реализован либо с использованием хеш-таблиц, либо с применением других механизмов, которые, в среднем, обеспечивают доступ к элементам коллекции за сублинейное время. Структуры данных, используемые в спецификации объекта Map, предназначены лишь для описания наблюдаемой семантики объектов Map. Они не задумывались как реальная модель реализации этих объектов.
Прежде чем мы начнём, хочу отметить, что то, о чём речь пойдёт ниже, относится к движку V8 8.4, который встроен в свежую dev-версию Node.js (если точнее, то речь идёт о коммите 238104c). Вам не нужно ожидать чего-то, выходящего за пределы спецификации.
Алгоритм, лежащий в основе реализации Map
В первую очередь скажу о том, что структуры данных Map основаны на хеш-таблицах. Ниже я исхожу из предположения о том, что вы знаете о том, как работают хеш-таблицы. Если же вы с хеш-таблицами не знакомы, то вам стоит сначала о них почитать (здесь, например) и уже потом продолжать чтение этой статьи.
V8 использует так называемые «детерминированные хеш-таблицы», предложенные Тайлером Клоузом. Следующий псевдокод, основанный на TypeScript, демонстрирует основные структуры данных, используемые при реализации таких хеш-таблиц:
А теперь — последний кусочек нашей головоломки. Когда таблица оказывается полна записей (и актуальных, и удалённых), она должна быть перехеширована (перестроена) с увеличением её размера. Размер таблицы может быть изменён и в сторону уменьшения.
Практическое исследование алгоритма
Давайте рассмотрим несколько примеров, позволяющих нам исследовать алгоритм на практике. Предположим, у нас имеется CloseTable с 2 хеш-контейнерами ( hastTable.length ), общая ёмкость которой составляет 4 элемента ( dataTable.length ). Эту таблицу заполняют следующим содержимым:
Внутреннее представление таблицы, получившейся в этом примере, может выглядеть так:
Если мы добавим в таблицу ещё пару записей, то она будет нуждаться в перехешировании. Этот процесс мы подробно обсудим немного ниже.
Теперь, когда мы разобрались с тем, что стоит за объектами Map в V8, мы готовы к тому, чтобы двинуться дальше.
Детали реализации
Так как нас особенно интересуют практические подробности о реализации Map в V8, нам, для начала, надо понять то, как задаётся ёмкость таблицы.
Ёмкость таблицы
В V8 ёмкость хеш-таблицы (структуры данных Map ) всегда равна некоей степени двойки. Если говорить о коэффициенте использования хеш-контейнеров, то он всегда представлен числом 2. То есть, максимальная ёмкость таблицы — это 2 * number_of_buckets — 2, умноженное на количество хеш-контейнеров. При создании пустого объекта Map в его внутренней хеш-таблице имеется 2 хеш-контейнера. В результате ёмкость такого объекта равняется 4 записям.
И наконец, коэффициент увеличения или уменьшения таблицы тоже всегда представлен произведением некоего числа на 2. Это значит, что после того, как в описываемую таблицу будет добавлено 4 записи, следующая операция вставки вызовет необходимость в перехешировании таблицы, в ходе которого размер таблицы увеличится в два раза. При уменьшении размеров таблицы, она, соответственно, может стать в 2 раза меньше.
Этот скрипт просто вставляет в структуру данных Map 100 записей. Вот что выводится в консоли после его запуска:
Как видно, когда таблица заполняется, то, при каждом изменении её размера, она увеличивается в 2 раза. Попробуем теперь добиться уменьшения таблицы, удаляя из неё элементы:
Вот что выведет этот скрипт:
Тут, опять же, видно, что размер таблицы уменьшается каждый раз, когда в ней оказывается меньше чем number_of_buckets / 2 элементов.
Хеш-функция
Для значений, которые можно отнести к числовым, используется та или иная хорошо известная хеш-функция с низкой вероятностью коллизии.
Для строковых значений выполняется вычисление хеш-кода, который основан на самих этих значениях. После этого данный код кешируется во внутреннем заголовке.
И, наконец, для объектов хеши вычисляют на основе случайного числа, а то, что получилось затем кешируется во внутреннем заголовке.
Временная сложность операций с объектами Map
Представим себе наихудший сценарий развития событий, когда таблица полностью заполнена, то есть, в ней заняты N из N мест. Все записи при этом принадлежат единственному хеш-контейнеру, а искомая запись находится в самом конце цепочки записей. В подобном сценарии для поиска этой записи понадобится выполнить N действий.
С другой стороны, в наилучшем сценарии, когда таблица заполнена, и при этом в каждом хеш-контейнере находится всего 2 записи, поиск записи потребует всего 2 действий.
Потребление памяти
Массив, используемый для хранения структур данных Map в памяти
Отдельные части массива имеют следующее назначение:
Итоги
В этом материале мы разобрали много всего, имеющего отношение к структуре данных Map в JavaScript. Подведём итоги:
