algorithm - 有没有办法减少这个队列的内存使用？

Question

在自由 C 中:

/* i'm using this */

struct QueueItem
    {
    QueueItem* next;
    void* data;
    }

struct Queue
    {
    QueueItem* head;
    QueueItem* tail;
    }

/*
    +---+    +---+
    |0 0|    |* *|  len 1
    +---+    +|-|+
              v v
     len     +---+
      0      |d 0|
             +---+
    
    +---+
    |* *---------...---+
    +|--+              |  len n
     v                 v
    +---+  +---+      +---+
    |a *-->|b *--...->|z 0|
    +---+  +---+      +---+
*/

这为所有 push/pop/peek 和 O(n) 遍历提供了 O(1)，但使用了 2+2n 内存。 朴素的数组版本给出最小值 2+n (大约最优)，但通常是 更糟的是，有时会导致修改花费更长的时间(用于重新分配)。

struct Queue
    {
    size_t len;
    size_t head;
    void (*data)[];
    }

/*
    +-----+
    |* * *-----~~~-+
    +|-|--+        |
     v +-+         |
    +----v-----~~~-v+
    |0 0 a b c . . z|
    +----------~~~--+
*/

看起来没有办法通过牺牲性能来提高内存使用率，但我想至少把它放在那里，以防有人知道解决这个问题的方法。

编辑(因为我不能在注释中有代码):

struct QueueItem
{
    QueueItem* next;
    size_t len;
    void (*data)[];
    }

struct Queue
    {
    QueueItem* head;
    QueueItem* tail;
    size_t start;
    size_t end; //edit: need to know where to push data. edit: not per-item
    }

/*
    +-----+
    |* * *------------------------------+
    +|-|--+                             |
     v +---+        (2x longer)         v (much longer)
    +------v----+  +-----------+       +---------------+
    |@ 0 0 a b *-->|@ c . . h *-->...->|@ . . . x y z 0|
    +-----------+  +-----------+       +---------------+
*/

Answer 1

首先，我认为您忽略了分配 QueueItems 的成本。因此，您的两种方法之间的分配成本是相同的。 (有比较了解内存分配的人，如果我错了请大声说出来。)

你可以这样做来减少数组中弹出/未填充项目的空间浪费。混合使用列表和数组。让每个列表节点包含一个大小为 K 的数组。

struct QueueItem
    {
    QueueItem* next;
    void (*data)[K];
    }

struct Queue
    {
    QueueItem* head;
    QueueItem* tail;
    size_t head;
    size_t end;
    }

现在您的性能取决于您为阵列选择的大小。它越小，你浪费的空间就越少。它越大，您的 QueueItem 开销占总空间的百分比就越少。例如，如果您知道队列的大小通常为 N，那么您可能会选择 K 为 N/10。在这种情况下，总内存成本为 N/K + 4 + N。您可以在数组中浪费在未使用元素上的最大空间量为 2*K - 2。

使用模式将决定实际性能。但是如果你能预见到你的使用模式，你就可以选择一个效果很好的 K。甚至可能有一种方法可以为每个节点自适应地选择不同的 K 以获得更好的性能，但我认为这现在超出了我的范围。