Структура данных в виде очереди с быстрым поиском и вставкой - PullRequest
Новая
       31

Структура данных в виде очереди с быстрым поиском и вставкой

2 голосов
/ 16 апреля 2010

Мне нужна структура данных со следующими свойствами:

  1. Содержит целые числа.
  2. Дубликаты не допускаются (то есть, они хранят не более одного целого числа).
  3. После достижения максимального размера первый элемент удаляется. Итак, если емкость равна 3, то это будет выглядеть так, если ввести в нее последовательные числа: {}, {1}, {1, 2}, {1, 2, 3}, {2, 3, 4}, {3, 4, 5} и т. Д.
  4. Требуются только две операции: вставка номера в этот контейнер (INSERT) и проверка, если номер уже находится в контейнере (EXISTS). Ожидается, что количество операций EXISTS составит приблизительно 2 * числа операций INSERT.
  5. Мне нужно, чтобы эти операции были максимально быстрыми.

Какой была бы самая быстрая структура данных или комбинация структур данных для этого сценария?

Ответы [ 4 ]

3 голосов
/ 16 апреля 2010

Звучит как хеш-таблица, использующая кольцевой буфер для хранения.

2 голосов
/ 16 апреля 2010

O (1) как для вставки, так и для поиска (и, если понадобится, удалите) .

Структуры данных:

Очередь узлов, содержащих целые числа, реализована в виде связанного списка (queue)

и

HashMap отображает целые числа в узлы связанного списка очереди (hashmap)

Вставка: 

if (queue.size >= MAX_SIZE) {
    // Remove oldest int from queue and hashmap
    hashmap.remove(queue.pop());
} else if (!hashmap.exists(newInt)) { // remove condition to allow dupes.
    // add new int to queue and hashmap if not already there
    Node n = new Node(newInt);
    queue.push(n);
    hashmap.add(newInt, n);
}

Поиск: 

return hashmap.exists(lookupInt);

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

0 голосов
/ 16 апреля 2010

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

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

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

Кроме того, вы можете использовать отсортированный список и хеш-таблицу. Вместо того, чтобы просто помещать ваши значения в отсортированный список, вы можете поместить пары (id, value) и затем получить карту хэш-таблицы от значения до (id, value). id будет просто увеличиваться после каждой вставки. Когда вы находите совпадение в хеш-таблице, вы удаляете это (id, значение) из списка и добавляете новую пару (id, значение) в конец списка. В противном случае вы просто добавляете в конец списка и всплываете с самого начала, если он слишком длинный.

0 голосов
/ 16 апреля 2010

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

int *buffer = {0,0,0};
int start = 0;
int end = 0;
#define LAST_INDEX 2;

void insert(int data)
{
   buffer[end] = data;
   end = (end == LAST_INDEX) ? 0 : end++;
}
void remove_oldest()
{
   start = (start == LAST_INDEX) ? 0 : start++;    
}
void exists(int data)
{
   // search through with code to jump around the end if needed
}

начало всегда указывает на первый элемент конец всегда указывает на самый последний элемент список может переноситься через конец массива

поиск n логн вставить 1 удалить 1

Для истинных гиков, хотя и создайте фильтр Блума http://en.wikipedia.org/wiki/Bloom_filter не гарантируется точность на 100%, но быстрее, чем что-либо.

...