展开链表比链表好在哪里？

Question

我正在学习这本书 "Data Structure and algorithms made easy"，但我在学习时感到困惑 "Comparing Linked Lists and Unrolled Linked list"...

什么是开销？为什么他只说明 100 个元素数组的开销为 8 个字节？

Answer 1

开销是所有不属于您要存储的数据的内容。就像指向下一个和上一个元素的指针。

阻止列表是一个数组列表。每个数组包含多个元素。原则上，您的整个列表可以由一个块节点和一个包含所有元素的数组组成。开销更少。

LinkedBlock 中的 head 指向一个 ListNode 有点令人困惑——它应该指向任何数据（没有 prev 和 next 指针）。

Answer 2

在普通链表中，1个节点有1个元素和2个指针（8字节），2个指针是开销，因为它不是你的数据。在展开的链表中，1 个节点有 100 个元素和 2 个指针（8 字节），因此 100 个元素的开销为 8 字节。

Answer 3

我认为这本书在 struct LinkedBlock 的定义上有一个严重的错误。让我们稍后回过头来开始：

what is overhead?

struct ListNode被设计用于存储一个整数但是除了整数每个节点还有两个指针。因此，对于每个节点，您需要分配 1 个整数 + 2 个指针。让我们假设 4 字节整数和 4 字节指针。所以每个节点将需要 4 + 2x4 = 12 个字节。因此，为了存储 1 项真实数据（又名 1 个整数），您需要分配 12 个字节。你在指针上浪费了 8 个字节。这8"wasted"字节称为开销。它们仅用于簿记 - 不用于数据。

但情况比这更糟...分配动态内存时（您通常在使用链表时这样做）会有一些额外的开销。分配器可能需要为每个 malloc 分配一些额外的内存来存储有关 malloc 的信息。另一个问题是 malloc ed 内存可能与某些固定块大小（例如 16 或 32 字节）对齐，因此如果您分配 20 字节，则无法使用剩余的 12 字节 - 它们被浪费了。这就是书上所说的"allocation overhead"。 "allocation overhead" 是系统相关的，但本书假设每个 malloc.

有 8 个额外的开销字节

所以现在每个 malloc 编辑 struct ListNode 占用：

整数为 4 个字节

8 个字节用于 2 个指针

8 字节用于分配开销

总共 20 个字节，其中 4 个字节用于您的数据，16 个字节用于开销。因此，对于您需要存储的每个整数，您需要 20 个字节。如果你想存储 1000 个整数，你最终会浪费 16kb 的开销来存储 4kb 的数据。

现在回到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 个字节的第一种方法进行比较。

Why he is only stating 8 bytes of overhead for 100 elements array?

那是因为数组是在单个调用中分配的，并且假定每个 malloc 调用有 8 个字节的分配开销。

展开链表比链表好在哪里？

How is unrolled linked list better than linked list?

c

linked-list

overhead