О широком использовании realloc () в c?

Question

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

Я использую c.Сначала я построил свое дерево, используя структуры (node.properties, node.Left, nodeRight и т. Д.), Но для этого требуется слишком много памяти (если вы знакомы со структурами, вы, вероятно, поймете почему), поэтому я имеючтобы вернуться к некоторой «встроенной» организации моего дерева, сохраняя адрес дочерних узлов в первых двух слотах и ​​(в конечном итоге) остальную информацию в следующих слотах.

ИтакЯ думал о двух способах сделать это.Одним из способов является прогнозирование общего количества узлов (просто) и выделение достаточного количества памяти для хранения всех узлов как обычных узлов (2 слота для адресов дочерних узлов и 1 слот для информации).Еще один способ сделать это - перераспределить массив деревьев по мере того, как мы идем вниз по дереву.

Первый вопрос: действительно ли полезно широко использовать realloc () с точки зрения эффективности?

Второй вопрос: есть ли более умный (с точки зрения памяти) способ сделать это?

Answer 1

Чтобы проиллюстрировать смысл использования индексов вместо указателей, см. эту реализацию хеш-таблицы , которая использует (короткие) индексы int, сохраняя несколько ценных битов.Функция tiny_find () компилируется в эту сборку (GCC -O2):

        .globl  tiny_find
        .type   tiny_find, @function
tiny_find:
.LFB57:
        .cfi_startproc
        imull   $98765, %edi, %ecx
        movl    $274877907, %edx
        movl    %ecx, %eax
        mull    %edx
        movl    $-1, %eax
        shrl    $6, %edx
        imull   $1000, %edx, %edx
        subl    %edx, %ecx
        movzwl  %cx, %ecx
        movzwl  table+4(,%rcx,8), %edx
        cmpw    $-1, %dx
        je      .L12
        movzwl  %dx, %eax
        testb   $1, table+7(,%rax,8)
        jne     .L19
        jmp     .L13
        .p2align 4,,10
        .p2align 3
.L21:
        movzwl  table+4(,%rax,8), %eax
        cmpw    $-1, %ax
        je      .L20
        movzwl  %ax, %eax
        testb   $1, table+7(,%rax,8)
        je      .L13
.L19:
        cmpl    table(,%rax,8), %edi
        jne     .L21
.L13:
        movzbl  table+6(,%rax,8), %eax
.L12:
        rep
        ret
        .p2align 4,,10
        .p2align 3
.L20:
        movl    $-1, %eax
        ret
        .cfi_endproc
.LFE57:
        .size   tiny_find, .-tiny_find

Внутренний цикл (обход списка ссылок) является частью между L21 и L13.Я бы не сказал, что код неэффективен.

Answer 2

ОК, я нашел компромисс, я думаю. Размер дерева определяется в первую очередь, и массив указателей с размером 2 X количество узлов выделяется. Каждый узел будет иметь (1) [указатель на] массив целых чисел с индексом левого потомка, индекс правого потомка и количество точек, и (2) [указатель на] массив двойников, содержащий вся полезная информация. Когда подпрограмма создает дерево, пространство, выделенное для «двойного» массива, будет вычислено в соответствии с типом узла.

Пока что это «самое дешевое» решение, которое я мог придумать. Но если вы можете убедить меня, что преобразование (long) index_in_double быстрое, в массиве можно использовать только double.