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

Question

Я ищу упорядоченную структуру данных, которая позволяет очень быстро вставлять.Это единственное обязательное свойство.Данные будут доступны и удаляться только из верхнего элемента.

Чтобы быть более точным, мне нужны 2 структуры:

1) Первая структура должна разрешать упорядоченную вставку с использованием значения int.После завершения вставки он должен сообщить ранг вставленного элемента .

2) Вторая структура должна позволять вставку с указанным рангом.

Количество элементовбыть сохраненным, вероятно, в тысячах или десятках тысяч.

[править] Я должен изменить гипотезу объема: даже если в любой момент размер упорядоченной структуры, вероятно, будет вв диапазоне десятков тысяч общее число вставок может составлять десятки миллионов за цикл.

Время вставки в O (1) было бы неплохо, хотя O (log (log (n)))) тоже очень приемлемо.В настоящее время у меня есть несколько интересных кандидатов только для первой структуры, но либо в log (n), либо без возможности сообщить ранг вставки (что является обязательным).

Answer 1

А как насчет формы skip-list , в частности, "индексированного skiplist" в связанной статье. Это должно дать O (LG N) вставки и поиска, и O (1) доступ к первому узлу для обоих ваших вариантов использования.

- Edit -

Когда я думаю об O (1) алгоритмах, я думаю о основанных на основаниях методах. Вот вставка O (1) с возвращенным рангом. Идея состоит в том, чтобы разбить ключ на кусочки и вести учет всех вставленных элементов, имеющих этот префикс. К сожалению, константа высока (<= 64 разыменований и дополнений), а объем памяти равен O (2 x 2 ^ INT_BITS), что ужасно. Это версия для 16-битных значений, расширение до 32-х бит должно быть простым. </p>

int *p1;int *p2;int *p3;int *p4;
void **records;
unsigned int min = 0xFFFF;

int init(void)     {
   p1 = (int*)calloc(16,sizeof(int));
   p2 = (int*)calloc(256, sizeof(int));
   p3 = (int*)calloc(4096, sizeof(int));
   p4 = (int*)calloc(65536,sizeof(int));
   records = (void**)calloc(65536,sizeof(void*));
   return 0;
}

//records that we are storing one more item, 
//counts the number of smaller existing items
int Add1ReturnRank(int* p, int offset, int a) {
   int i, sum=0;
   p+=offset;
   for (i=0;i<a;i++)
      sum += p[i];
   p[i]++;
   return sum;
}

int insert(int key, void* data) {
   unsigned int i4 = (unsigned int)key;
   unsigned int i3= (i4>> 4);
   unsigned int i2= (i3>> 4);
   unsigned int i1= (i2>> 4);
   int rank = Add1ReturnRank(p1,0, i1&0xF);
   rank += Add1ReturnRank(p2,i2&0xF0,i2&0xF);
   rank += Add1ReturnRank(p3,i3&0xFF0,i3&0xF);
   rank += Add1ReturnRank(p4,i4&0xFFF0,i4&0xF);
   if (min>key) {min = key;}
   store(&records[i4],data);
   return rank;
}

Эта структура также поддерживает O (1) GetMin и RemoveMin. (GetMin мгновенный, Remove имеет константу, аналогичную Insert.)

void* getMin(int* key) {
    return data[*key=min];
}

void* removeMin(int* key)  {
   int next = 0;
   void* data = records[min];
   unsigned int i4 = min;
   unsigned int i3= (i4>> 4);
   unsigned int i2= (i3>> 4);
   unsigned int i1= (i2>> 4);

   p4[i4]--;
   p3[i3]--;
   p2[i2]--;
   p1[i1]--;
   *key = min;
   while (!p1[i1]) {
      if (i1==15) { min = 0xFFFF; return NULL;}
      i2 = (++i1)<<4;
   }
   while (!p2[i2])
      i3 = (++i2)<<4;
   while (!p3[i3])
      i4 = (++i3)<<4;
   while (!p4[i4])
      ++i4;
   min = i4;
   return data;
}

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

Другой идеей улучшения хранилища было бы объединить эту идею с чем-то вроде Extendable Hash . Используйте целочисленный ключ в качестве значения хеша и сохраняйте количество вставленных узлов в каталоге. Выполнение суммы над соответствующими записями словаря на вставке (как указано выше) все равно должно быть O (1) с большой константой, но объем памяти уменьшится до O (N)

Answer 2

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

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

Что это?

Answer 3

Дерево статистики заказов , кажется, соответствует вашим потребностям во время O (LogN). Ссылка

Дерево статистики заказов - это расширенная (см. AugmentedDataStructures) версия
BinarySearchTree, поддерживающий дополнительные операции Rank (x), возвращающие ранг x (то есть количество элементов с ключами, меньшими или равными x) и FindByRank (k), который возвращает k-й наименьший элемент дерева.

Если у вас есть только десятки тысяч элементов, разница в производительности между временем O (LogN) и O (1) асимптотической сложностью не так значительна, как вы думали. Например, рассмотрим 100000 элементов, метод logN медленнее всего в 16 раз.

log (100 000) / log (2) = 16.6096405

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

Вы должны сравнить (на самом деле) протестировать различные реализации кучи, чтобы найти одну с наилучшей реальной производительностью .

Answer 4

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

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

Или вы можете просто использовать двусвязный список, в котором вам гарантированно будут вставлены и удалены O (1). для ранжирования вы можете встраивать эту информацию в узлы.