Я думаю, что книга содержит серьезную ошибку в определении struct LinkedBlock.Давайте вернемся к этому позже и начнем с:
что такое издержки?
struct ListNode предназначен для хранения одного целого числа , но кроме тогоцелое число каждого узла имеет два указателя.Таким образом, для каждого узла вам нужно выделить 1 целое число + 2 указателя.Давайте предположим, что 4-байтовое целое и 4-байтовый указатель.Таким образом, каждому узлу потребуется 4 + 2x4 = 12 байтов.Таким образом, чтобы сохранить 1 элемент ваших реальных данных (1 целое число), вам нужно выделить 12 байтов.Вы потратили 8 байтов на указатели.Эти 8 «потраченных впустую» байтов называются издержками.Они используются только для бухгалтерии - не для данных.
Но это еще хуже ... При распределении динамической памяти (что вы обычно делаете при использовании связанного списка) возникают некоторые дополнительные издержки.Распределителю может потребоваться немного дополнительной памяти для каждого malloc для хранения информации о malloc.Другая проблема заключается в том, что malloc редактируемая память может быть выровнена по некоторому фиксированному размеру блока (например, 16 или 32 байта), поэтому, если вы выделяете 20 байтов, нет никакого способа использовать оставшиеся 12 байтов - они теряются.Это то, что книга называет «накладными расходами».«Расходы на выделение ресурсов» зависят от системы, но книга предполагает 8 дополнительных байтов служебных данных от каждого malloc.
Так что теперь каждый malloc 'ed struct ListNode занимает:
4 байтадля целого числа
8 байтов для 2 указателей
8 байтов для накладных расходов на выделение
Всего 20 байтов, где 4 байта для ваших данных и 16 байтов для заголовка.Таким образом, для каждого целого числа, которое вам нужно сохранить, вам понадобится 20 байтов.И если вы хотите хранить 1000 целых чисел, вы в конечном итоге тратите 16 КБ на служебные данные, чтобы хранить 4 КБ данных.
Теперь вернемся к struct LinkedBlock.В книге это выглядит так:
struct LinkedBlock {
struct LinkedBlock *next;
struct LinkedNode *head;
int nodeCount;
};
Я почти уверен, что в книге есть ошибка, и вместо этого она должна выглядеть следующим образом:
struct LinkedBlock {
struct LinkedBlock *next;
int *dataArray;
int nodeCount;
};
Путь киспользовать это что-то вроде:
struct LinkedBlock pNode = malloc(sizeof(struct LinkedBlock));
pNode->dataArray = malloc( 100 * sizeof(int) );
Первый malloc требует 4 + 4 + 4 + 8 = 20 байт.(указатель, указатель, int, издержки выделения)
Второй malloc требует 4 * 100 + 8 = 408 байтов.(100 int, накладные расходы на выделение)
Таким образом, в общей сложности 428 байт.
Однако, поскольку данные malloc 'могут содержать 100 целых чисел (соответствующих 400 байтам), ваши накладные расходы составляюттолько 28 байтов.Другими словами - в среднем вы используете 4,28 байта для каждого целого числа.Сравните это с первым методом, в котором для каждого целого числа требовалось 20 байтов.
Почему он указывает только 8 байтов служебной информации для массива 100 элементов?
Это произошло потому, чтомассив был выделен в одном вызове, и предполагается, что каждый вызов malloc имеет накладные расходы на выделение 8 байтов.