Как компактное дерево может быть полезным?

Question

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

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

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

Answer 1

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

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

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

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

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

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

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

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

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