1

我正在使用 C#，但即使您不知道，也应该很容易理解这个问题。

这是我的问题：我想将一些对象保存在类似哈希集的数据结构中，以便可以根据intID 查找它们。这些对象具有可变属性，因此对它们进行散列不是一种选择（我需要一些关于它们的常量来散列，是吗？）。

我所做的是开发以下接口：

public interface IUniqueIDCollection
{
    // Can return any int that hasn't been requested yet.
    public int RequestUniqueID();

    // Undos the requesting of an int
    public int ReleaseUniqueID(int uniqueID);
}

我最初的想法是在请求 ID 时将内部计数器存储在IUniqueIDCollection增量中。但是，一旦 ID 被释放，我将不得不跟踪已删除的范围或单个 ID。我认为后者会更好。但是，如果我使用计数器（或任何循环函数）来生成 ID，我将遇到一个问题，即必须检查已连续请求的 ID 序列，一旦计数器回绕，则未释放。

启发式是这样的：假设一次最多请求 5,000 个 ID。但是，ID 通常会请求然后发布。释放往往会在范围内发生——即可能会一次请求全部 100 个，然后在很短的时间间隔内释放所有 100 个。

我知道我可以使用 GUID 或其他东西而不是 int，但我想节省 ID 的空间/带宽/处理时间。

所以我的问题是：就伪代码而言，给定启发式方法，我上面给出的接口中的请求和释放方法应该是什么样子？

4

2 回答 2

5

如果您确定已发布的 ID 可以安全地立即重复使用（即，如果新对象分配了最近发布的 ID，则不会有对旧 ID 的陈旧引用会混淆），您可以使用首次发布ID。所以当一个 ID 被释放时，你把它放在队列的末尾。当请求新 ID 时，您使用队列中的第一个 ID。如果队列为空，则增加内部计数器并给出新数字。

这种实现的优点：

  • 所有操作都是 O(1)。您永远不会迭代集合或范围。您只能在队列的末尾插入、从队列的前面删除或增加您的计数器。
  • 内存占用应该相当低，因为您正在尝试尽快用完队列。
  • 实施很简单。

缺点：

  • 您将快速重用 ID，因此您不会使用整个索引范围来防止新对象使用与最近发布的对象相同的 ID。
  • 您甚至无法通过查看对象的 ID 来猜测对象的年龄。
于 2012-09-06T17:36:57.057 回答
1

在几乎所有情况下，这可能比上面的Tom Panning更糟糕，但您可以使用 BitArray 来跟踪正在使用的 ID。内存使用量与您拥有实时 ID 的总位数一样多；最坏的情况是 512MB 用于映射所有 32 位整数。释放很容易：只需将相应的位设置为 0。获取（或请求）ID 需要搜索 0 位，如果找不到，则扩展 BitArray。

如果您仍然可以选择扩展您的 BitArray（即您还没有达到 512MB），您可能不想在决定扩展之前搜索所有 BitArray - 一直这样做会很慢。您当然不会总是希望从同一个索引开始：跟踪您找到的最后一个 0 并从那里开始搜索可能是个好主意。

我可以看到的一个优点是一旦所有或几乎所有对象被释放，内存使用情况。那么 Tom Panning 的解决方案需要的内存至少是这个的 32 倍。但是，我希望在典型用法中该解决方案使用较少。

于 2012-09-06T18:40:48.257 回答