1

我正在寻找一种数据结构来帮助我管理整数池。这是一个池，我从池中删除整数一会儿，然后将它们放回原处，期望它们会再次被使用。但是，它还有一些其他奇怪的限制，因此常规池不能很好地工作。

硬性要求：

  • 恒定时间访问最大的使用整数。
  • 整数的稀疏性需要有界（即使只是原则上）。
    我希望整数彼此接近，因此我可以使用范围内最少的未使用整数快速迭代它们。

如果它们有助于选择数据结构，请使用它们，否则请忽略它们：

  • 池中的整数基于 0 且连续。
  • 池的大小可以是恒定的。
  • 池中的整数仅用于短期高流失率。

我有一个可行的解决方案，但感觉不优雅。
我的（次优）解决方案

恒定大小的池。
将所有可用的整数放入一个有序集合（free_set）。
当请求一个新整数时，从 free_set 中检索最小的整数。
将所有使用中的整数放入另一个排序集（used_set）。
当请求最大时，从 used_set 中检索最大的。

有一些优化可能有助于我的特定解决方案（优先队列、记忆等）。但我的整个方法似乎很浪费。

我希望有一些深奥的数据结构完全适合我的问题。或者至少是更好的池化算法。

4

2 回答 2

0

为什么不使用平衡二叉搜索树？您可以存储指向 min 元素的指针/迭代器并免费访问它，并在插入/删除后更新它是 O(1) 操作。如果你使用自平衡树，插入/删除是 O(log(n))。详细说明：

insert：只需将新元素与前一个元素进行比较；如果最好使迭代器指向新的最小值。

delete：如果 min 被删除，则在删除之前找到后继者（您可以通过将迭代器向前移动 1 步来完成），然后将该人作为新的 min。

虽然理论上可以使用某种复杂的超级堆数据结构（即斐波那契堆）做得更好，但在实践中，我认为您不会为了节省一个小日志因子而想要处理实现类似的东西。此外，作为奖励，您可以免费获得快速的顺序遍历——更不用说现在大多数编程语言^都带有开箱即用的自平衡二叉搜索树的快速实现（如红黑树/avl等.)。

^ 除了 javascript :P

编辑：想到一个更好的答案。

于 2012-04-18T19:37:21.897 回答
0

伪类：

class IntegerPool {

  int size = 0;
  Set<int> free_set = new Set<int>();

  public int Acquire() {
    if(!free_set.IsEmpty()) {
      return free_set.RemoveSmallest();
    } else {
      return size++;
    }
  }

  public void Release(int i) {
    if(i == size - 1) {
      size--;
    } else {
      free_set.Add(i);
    }
  }

  public int GetLargestUsedInteger() {
    return size;
  }
}

编辑

RemoveSmallest并不是那么有用。RemoveWhatever已经足够好了。所以Set<int>可以替换LinkedList<int>为更快的替代方案（甚至Stack<int>）。

于 2012-04-18T16:11:04.430 回答