Как компактное дерево может быть полезным? - PullRequest
0 голосов
/ 12 октября 2018

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

Если в узле компактного дерева мы сохраняем 3 целых числа и ссылку на объект String, это не спасетПамять вообще, если этот объект String также хранится в памяти?

Если это так, то компактный метод выгоден только тогда, когда мы сохраняем объект String на диске.

1 Ответ

0 голосов
/ 12 октября 2018

Компактное хранилище сжатого дерева может быть более эффективным, если вы уже храните строки для какой-либо другой цели.

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

Для некомпактного сжатого дерева:

  • У каждого узла будет строка, для которой требуется указатель (скажем, 4 байта) и длина (2 байта).Это дает нам 6 байтов.

  • Кроме того, нам нужно сохранить фактическую строку (даже если мы уже храним их в другом месте).

Для компактного сжатого дерева:

  • Каждый узел будет иметь 3 целых числа (по 2 байта каждый).Это дает нам 6 байтов.
  • Если мы рассчитываем и на сохранение строк, у нас будут фактические строки (такие же, как указано выше), в дополнение к накладным расходам (указатель и длина)из этих строк.
  • Учитывая эти числа (если мы считаем хранение строк), эта версия будет хуже.

Для несжатого файла: (то есть, где мы храним только один символ на узел)

  • Каждый узел напрямую хранит свой один символ.
  • Там не будет служебной строки.
  • Однако, если у вас длинные цепочки, у вас может быть намного больше узлов с этим представлением, поэтому это может привести к снижению затрат времени и места (особенно учитывая затраты времени на переход между кучами мест в памяти, а не простовозможность читать последовательный блок памяти).
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...