очередь с ограниченным пространством: ищем хороший алгоритм

Question

Это не домашняя работа.

Я использую небольшую «очередь с приоритетами» (в настоящее время реализованную в виде массива) для хранения последних N элементов с наименьшим значением. Это немного медленно - O (N) время вставки предмета. Текущая реализация отслеживает самый большой элемент в массиве и отбрасывает любые элементы, которые не помещаются в массив, но я все же хотел бы еще больше сократить количество операций.

ищет алгоритм очереди приоритетов, который соответствует следующим требованиям:

1. очередь может быть реализована как массив, который имеет фиксированный размер и _cannot_ растут. Динамическое распределение памяти во время любой операции очереди строго запрещено.
2. Все, что не помещается в массив, отбрасывается, но в очереди хранятся все самые маленькие элементы, которые когда-либо встречались.
3. Время вставки O (log (N)) (то есть добавление элемента в очередь должно составлять до O (log (N))).
4. (необязательно) O (1) доступ для * самого большого * элемента в очереди (в очереди хранятся * наименьшие * элементы, поэтому самый большой элемент будет отброшен первым, и мне понадобится их, чтобы уменьшить количество операций)
5. Легко реализовать / понять. В идеале - что-то похожее на бинарный поиск - как только вы понимаете это, вы запоминаете это навсегда.
6. Элементы не нужно сортировать никоим образом. Мне просто нужно сохранить N наименьшее значение, когда-либо встречавшееся. Когда они понадобятся, я получу доступ ко всем сразу. Так что технически это не обязательно должна быть очередь, мне просто нужно сохранить N последних наименьших значений.

Сначала я думал об использовании двоичных куч (они могут быть легко реализованы с помощью массивов), но, видимо, они плохо себя ведут, когда массив больше не может расти. Связанные списки и массивы потребуют дополнительного времени для перемещения. Очередь приоритетов stl растет и использует динамическое распределение (хотя я может ошибаться в этом).

Итак, есть еще идеи?

- EDIT -
Я не заинтересован в реализации STL. Реализация STL (предложенная несколькими людьми) работает немного медленнее, чем используемый в настоящее время линейный массив из-за большого количества вызовов функций.

Меня интересует приоритетная очередь алгоритмы , а не реализации.

Answer 1

Кучи на основе массива кажутся идеальными для ваших целей. Я не уверен, почему вы их отвергли.

Вы используете максимальную кучу.

Скажем, у вас есть куча N элементов (реализованная в виде массива), которая содержит N самых маленьких элементов, которые мы когда-либо видели.

Когда элемент входит, вы проверяете максимальное (O (1) время) и отклоняете, если оно больше.

Если входящее значение меньше, вы изменяете корень на новое значение и уменьшаете это измененное значение - время O (log N) в худшем случае.

Процесс sift-down прост: начиная с root, на каждом шаге вы обмениваетесь этим значением с его более крупным потомком, пока не восстановится свойство max-heap.

Таким образом, вам не нужно будет удалять , что вам, вероятно, придется, если вы используете std :: priority_queue. В зависимости от реализации std :: priority_queue это может привести к выделению / освобождению памяти.

Таким образом, вы можете иметь следующий код:

• Выделенный массив размера N.
• Заполните его первыми N элементами, которые вы видите.
• heapify (вы должны найти это в стандартных учебниках, он использует sift-down). Это O (N).
• Теперь любой новый элемент, который вы получаете, вы либо отклоняете в O (1) раз, либо вставляете, отсеивая в худшем случае O (logN).

В среднем, тем не менее, вам, вероятно, не придется полностью уменьшать новое значение, и оно может быть лучше, чем среднее время вставки O (logn) (хотя я не пытался это доказать). *

Вы выделяете массив размера N только один раз, и любая вставка выполняется путем замены элементов массива, поэтому динамическое выделение памяти после этого не происходит.

Посетите вики-страницу с псевдокодом для heapify и sift-down: http://en.wikipedia.org/wiki/Heapsort

Answer 2

Используйте std::priority_queue с самым большим предметом в голове. Для каждого нового элемента откажитесь от него, если это >= элемент головы, в противном случае вытолкните элемент головы и вставьте новый элемент.

Примечание: стандартные контейнеры будут расти, только если вы их сделаете. Пока вы удалите один элемент перед вставкой нового элемента (конечно, после того, как он достигнет максимального размера), этого не произойдет.

Answer 3

Большинство приоритетных очередей, с которыми я работаю, основаны на связанных списках. Если у вас есть заранее определенное количество уровней приоритета, вы можете легко создать очередь приоритетов со вставкой O (1), имея массив связанных списков - один связанный список на уровень приоритета. Предметы с одинаковым приоритетом, конечно, выродятся в FIFO, но это можно считать приемлемым.

Добавление и удаление становится чем-то вроде (ваш API может отличаться) ...

listItemAdd (&list[priLevel], &item);      /* Add to tail */
pItem = listItemRemove (&list[priLevel]);  /* Remove from head */

Получение первого элемента в очереди становится проблемой поиска непустого связанного списка с наивысшим приоритетом. Это может быть O (N), но есть несколько приемов, которые вы можете использовать, чтобы ускорить его.

1. В структуре очередей с приоритетами сохраняйте указатель или индекс или что-то в связанном списке с текущим наивысшим приоритетом. Это необходимо будет обновлять каждый раз, когда элемент добавляется или удаляется из очереди с приоритетами.
2. Используйте растровое изображение, чтобы указать, какие связанные списки не пусты. В сочетании с алгоритмом поиска старшего значащего бита или алгоритма поиска младшего значащего бита вы обычно можете протестировать до 32 списков одновременно. Опять же, это нужно будет обновлять при каждом добавлении / удалении.

Надеюсь, это поможет.

Answer 4

Найдено решение («разница» означает «приоритет» в коде, а maxRememberedResults - 255 (может быть любым (2 ^ n - 1)):

template <typename T> inline void swap(T& a, T& b){
    T c = a;
    a = b;
    b = c;
}


struct MinDifferenceArray{
    enum{maxSize = maxRememberedResults};
    int size;
    DifferenceData data[maxSize];
    void add(const DifferenceData& val){
        if (size >= maxSize){
            if(data[0].difference <= val.difference)
                return;

            data[0] = val;

            for (int i = 0; (2*i+1) < maxSize; ){
                int next = 2*i + 1;
                if (data[next].difference < data[next+1].difference)
                    next++;
                if (data[i].difference < data[next].difference)
                    swap(data[i], data[next]);
                else
                    break;
                i = next;
            }
        }
        else{
            data[size++] = val;
            for (int i = size - 1; i > 0;){
                int parent = (i-1)/2;
                if (data[parent].difference < data[i].difference){
                    swap(data[parent], data[i]);
                    i = parent;
                }
                else
                    break;
            }
        }
    }

    void clear(){
        size = 0;
    }

    MinDifferenceArray()
        :size(0){
    }
};

1. построить очередь на основе макс. (Корень самый большой)
2. пока не заполнится, заполните нормально
3. когда он заполнен, для каждого нового элемента
   1. Проверьте, меньше ли новый элемент, чем root.
   2. если он больше или равен корню, отклонить.
   3. в противном случае замените корень новым элементом и выполните обычную кучу «sift-down».

И мы получаем вставку O (log (N)) в худшем случае.

Это то же решение, которое предоставлено пользователем с ником "Moron". Спасибо всем за ответы.

P.S. По-видимому, программирование без достаточного количества сна не было хорошей идеей.

Answer 5

Вопросы вычислительной см. Стр. 158. Сама реализация довольно хороша, и вы можете даже немного ее настроить, не делая ее менее читабельной. Например, когда вы вычисляете левого потомка как:

int left = i / 2;

Вы можете вычислить правого ребенка следующим образом:

int right = left + 1;

Answer 6

Если вы создаете очередь приоритетов STL с максимальным размером (возможно, из вектора, инициализированного заполнителями), а затем проверяете размер перед вставкой (предварительно удаляя элемент при необходимости), у вас никогда не будет динамического выделения во время операций вставки. Реализация STL довольно эффективна.

Answer 7

Если количество приоритетов мало и фиксировано, вы можете использовать кольцевой буфер для каждого приоритета. Это приведет к пустой трате пространства, если объекты большие, но если их размер сопоставим с указателем / индексом, то варианты с сохранением дополнительных указателей в объектах могут увеличить размер массива таким же образом.
Или вы можете использовать простой односвязный список внутри массива и хранить 2 * M + 1 указатели / индексы, один будет указывать на первый свободный узел, а другие пары будут указывать на заголовок и хвост каждого приоритета. В этом случае вам придется сравнить в среднем. O (M), прежде чем вынуть следующий узел с O (1). И вставка займет O (1).