Есть ли способ уменьшить использование памяти в этой очереди?

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|
    +---+  +---+      +---+
*/

Это дает O (1) для всех обходов push / pop / peek и O (n), но использует 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 по-разному для каждого узла, чтобы получить еще лучшую производительность, но я думаю, что сейчас это за мной.

Answer 2

Если ваша очередь имеет максимальную емкость , а вы манипулируете только ее передней или хвостовой частью , я бы использовал Circular Array .Следующее изображение со ссылочного сайта и иллюстрирует идею круговых массивов:

круговой массив http://lcm.csa.iisc.ernet.in/dsa/img42.gif

Цитата:

• Сзадиочередь находится где-то по часовой стрелке от передней части
• Чтобы поставить элемент в очередь, мы перемещаем его на одну позицию назад по часовой стрелке и записываем элемент в эту позицию
• Для удаления из очереди мы просто перемещаем одну позицию вперед по часовой стрелке
• Очередь перемещается в направлении по часовой стрелке, поскольку мы ставим в очередь и вытесняем пустоту и заполненность для тщательной проверки.

При такой структуре данных Вы, очевидно, не можете вставлять элементы между двумяпоследовательные элементы уже сохранены, и вы не можете превзойти определенную максимальную емкость - я надеюсь, что она соответствует вашим потребностям.