(C ++) Ищите советы по сокращению использования памяти

Question

У меня проблема с очень жестким и жестким ограничением памяти.Я фанат CPP и хочу уменьшить использование памяти.Пожалуйста, дайте мне несколько советов.

---

Один из моих друзей порекомендовал взять из них функции внутри моих структур.например, вместо использования:

struct node{
   int f()
   {}
}

он порекомендовал мне использовать:

int f(node x)
{}

это действительно помогает?

Примечание: у меня много копий моей структуры.

---

вот еще немного информации:

Я кодирую какое-то дерево сегментов для практической задачина онлайн-судье.Я получаю узлы дерева в структуре.моя структура имеет следующие переменные:

  int start;
  int end;
  bool flag;
  node* left;
  node* right;

Ограничение памяти составляет 16 МБ, и я использую 16,38 МБ.

Answer 1

По подтексту вашего вопроса я предполагаю, что большая часть вашего использования памяти - это данные, а не код.Вот несколько советов:

• Если ваши диапазоны данных ограничены, воспользуйтесь этим.Если диапазон целого числа составляет от -128 до 127, используйте char вместо int или unsigned char, если это от 0 до 255. Аналогичным образом используйте int16_t или uint16_t для диапазонов -32768..32767 и 0..65535.
• Переставьте элементы структуры так, чтобы на первом месте были более крупные элементы, чтобы при выравнивании данных не оставалось мертвого пространства в середине структуры.Обычно вы также можете управлять заполнением с помощью опций компилятора, но лучше всего сначала сделать макет оптимальным.
• Используйте контейнеры, которые не требуют больших накладных расходов.Например, используйте vector вместо list.Используйте boost::ptr_vector вместо std::vector, содержащего shared_ptr.
• Избегайте виртуальных методов.Первый виртуальный метод, который вы добавляете в структуру или класс, добавляет скрытый указатель на виртуальную таблицу.

Answer 2

Нет, обычные функции-члены не увеличивают класс или структуру.Введение виртуальной функции 1002 * может (на многих платформах) добавить указатель vtable на класс.На x86 это увеличило бы размер на четыре байта.При добавлении виртуальных функций больше памяти не потребуется - достаточно одного указателя.Размер класса или типа структуры никогда не равен нулю (независимо от того, есть ли у него переменные-члены или виртуальные функции).Это делается для того, чтобы каждый экземпляр занимал свое собственное пространство памяти ( источник , раздел 9.0.3).

Answer 3

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

Answer 4

Для вашего последнего примера (дерева) вы можете использовать хитрый хак с XOR, чтобы заменить два указателя узла одним указателем узла, как описано здесь . Однако это работает, только если вы пересекаете дерево в правильном порядке. Очевидно, что это ухудшает читабельность кода, поэтому должно быть что-то вроде последнего средства.

Answer 5

Как уже говорили другие, наличие методов не увеличивает размер структуры, если один из них не является виртуальным.

Вы можете использовать битовые поля для эффективного сжатия данных (это особенно эффективно с вашим логическим значением ...). Также вы можете использовать индексы вместо указателей, чтобы сохранить несколько байтов.

Не забудьте распределить узлы большими порциями, а не по отдельности (например, один раз использовать [], а не многократно новый), чтобы избежать затрат на управление памятью.

Если вам не нужна полная гибкость, которую обеспечивают указатели узлов, вы можете уменьшить или устранить их. Например, у heapsort всегда есть почти полное двоичное дерево, поэтому стандартная реализация использует неявное дерево, которое вообще не нуждается в указателях.

Прежде всего, поиск другого алгоритма может полностью изменить игру ...

Answer 6

Две возможности совсем не эквивалентны:

• В первом f() является функцией-членом node.
• Во втором f()является свободной (или областью имен)(Обратите также внимание, что подпись двух f() различна.)

Теперь обратите внимание, что в первом стиле f() является функцией-членом inline.Определение функции-члена внутри тела класса делает его встроенным.Хотя встраивание не гарантируется, это всего лишь подсказка компилятору.Для функций с небольшими телами может быть полезно встроить их, так как это позволит избежать вызова функции через голову.Однако я никогда не видел, чтобы это был фактор «сделай или сломай».

Если вы не хотите или если f() не подходит для встраивания, вы должны определить его вне тела класса (вероятно, вфайл .cpp) как:

 int node::f() { /* stuff here */ }

Если использование памяти является проблемой в вашем коде, то, скорее всего, вышеперечисленные темы не актуальны.Изучение следующего может дать вам подсказку

• Найдите размеры всех классов в вашей программе.Используйте sizeof, чтобы найти эту информацию, например, sizeof (node)
• Найдите максимальное количество объектов каждого класса, создаваемого вашей программой.

• Использование двух приведенных вышеряд информации, оцените использование памяти в худшем случае вашей программой

  Использование памяти в худшем случае = n1 * sizeof (node1) + n2 * sizeof (node2) + ...

Если вышеуказанное число слишком велико, у вас есть следующие варианты:

• Сокращение количества максимальных экземпляров классов.Это, вероятно, будет невозможно, потому что это зависит от входных данных для программы, и это вне вашего контроля
• Уменьшите размер каждого класса.Это под вашим контролем, хотя.

Как уменьшить размер классов?Старайтесь компактно упаковывать учеников, чтобы избежать упаковки .

Answer 7

Вы можете использовать флаги компиляции для оптимизации.Если вы используете g ++, вы можете проверить с помощью: -O2

Есть замечательные темы по этому вопросу:

C ++ Оптимизация

Должны ли мы все еще оптимизировать "в малом"?

Константы и оптимизация компилятора в C ++

Что такоеизвестные оптимизации C / C ++ для GCC