具有极快插入时间的结构

Question

我正在寻找一种允许非常快速插入的有序数据结构。这是唯一需要的属性。数据只能从顶部元素访问和删除。

更准确地说，我需要 2 个结构：

1）第一个结构应该允许使用 int 值进行有序插入。完成插入后，它应报告插入元素的排名。

2) 第二个结构应该允许在指定的等级插入。

要存储的元素数量可能是数千或数万。

[编辑] 我必须修改体积假设：即使在任何时刻，有序结构的大小可能在数万范围内，插入的总数也可能在数千万个范围内跑步。

O(1) 内的插入时间会很好，尽管 O(log(log(n))) 也很容易接受。目前，我仅对第一个结构有一些有趣的候选，但要么在 log(n) 中，要么无法报告插入排名（这是强制性的）。

Answer 1

skip-list 的形式怎么样，特别是链接文章中的“索引跳过列表” 。这应该为您的两个用例提供 O(lg N) 插入和查找，以及 O(1) 对第一个节点的访问。

--编辑--

当我想到 O(1) 算法时，我想到的是基于基数的方法。这是一个 O(1) 插入并返回了排名。这个想法是将密钥分解为半字节，并记录所有具有该前缀的插入项的计数。不幸的是，常量很高（<=64 次取消引用和添加），并且存储空间为 O(2 x 2^INT_BITS)，这很糟糕。这是 16 位整数的版本，扩展到 32 位应该很简单。

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，但代价是当存在许多相似值时，最坏情况插入会更高。

改进存储的另一个想法是将这个想法与可扩展哈希之类的东西结合起来。使用整数键作为哈希值，并记录目录中插入的节点的数量。对插入中的相关字典条目进行求和（如上所述）应该仍然是 O(1) 且具有较大的常数，但存储空间将减少到 O(N)

Answer 2

订单统计树似乎可以满足您在 O(LogN) 时间内的需求。 链接

订单统计树是一个增强（参见 AugmentedDataStructures）版本的
BinarySearchTree 支持附加操作 Rank(x)，返回排名
x（即键小于或等于 x 的元素数量）和 FindByRank(k)，
返回树中第 k 个最小的元素。

如果你只有几万个元素，O(LogN) 时间和 O(1) 时间渐近时间复杂度之间的性能差异并不像你想象的那么显着。例如，考虑 100000 个元素，logN 方法仅慢 16 倍。

日志（100 000）/日志（2）= 16.6096405

在这种情况下，系数（实现、开销）的差异可能是优化的真正目标。由于继承的复杂性，花哨的数据结构通常具有更高的开销（有时慢数千倍）。它们更有可能来自不太精细的实现，因为它们很少被使用。

您应该对不同的堆实现进行基准测试（实际测试），以找到具有最佳实际性能的堆实现。

Answer 3

你说你需要一个有序的数据结构，在我看来，你需要一些可以在 O(n) 时间内生成所有元素的东西。

但随后你说你只会访问顶部（最少？）元素，这表明你实际上只需要能够重复产生最小值的东西 - 打开通向具有部分排序的东西的大门。

是哪一个？

Answer 4

如果我正确理解你的问题，我建议你使用一个字典，其键是排名，值是链接列表。

使用键，您可以拥有排名，使用链表作为值，您可以拥有 O(1) 插入时间。另外，作为删除，您可以拥有 O(1)。您可以使用链表实现堆栈或队列，这就是您想要的。

或者您可以只使用双向链表，保证插入和删除的时间复杂度为 O(1)。为了排名，您可以将该信息嵌入到节点中。