查找第一个空闲索引

Question

查找第一个空闲索引

4

我有一个包含100万个id的大数组/列表，需要找到可以使用的第一个空闲id。可以假设有几个模块引用了这个数据结构，并取一个id（此期间应标记为已使用），然后稍后返回它（应标记为可用）。我想知道可以使用哪些不同的数据结构？以及我可以使用什么算法来在时间和空间上高效地完成此操作（分别）。如果此问题已经在此处存在，请谅解。

- Rishabh Puri

2

在这个上下文中，“first”是什么意思？你只需要任何可用的免费ID还是最小的ID（假设有一个合理的顺序），或者是你ID列表中的第一个？每种情况都会得出不同的解决方案。 - Joel

这1百万个ID是否与某些特定内容相关，还是您只需要一个唯一的ID？如果您只需要唯一的ID，则有一些库可以在需要时生成唯一的GUID，并且在合理条件下具有0碰撞几率。 - log0

6个回答

6

一个天真但高效的方法是将所有id存储在堆栈中。获取id是一个常数时间操作：弹出列表的第一个项。当任务完成后，只需将id推到堆栈上。

如果必须返回最低的可用id（而不是任何可用id），则可以使用min heap，插入和弹出最低点档案的时间复杂度为O(log N)。

- log0

重新插入一个ID的成本不是O(n)吗？因为你必须扫描整个堆栈来找到正确的位置。 - templatetypedef

@templatetypedef 不，它应该是常数时间，因为列表中的所有id都应该是空闲的。只需在顶部插入即可。 - log0

2

哦 - 我认为我们对问题的解释不同。我以为 OP 所说的“第一”是指“最低”，而你则将其解释为“任何免费的东西”。在这种情况下，这是一个很好的答案！ - templatetypedef

1

看起来不错，但我认为最小堆具有O（log n）的时间弹出最低项，而不是O（1）弹出最低项。 - templatetypedef

@templatetypedef 当然，你是正确的！删除最小值的时间复杂度为O(log n)。 - log0

显示剩余2条评论

2

尝试使用链表（id的链表）。链接所有这些列表，并将头指向空闲列表（假设在初始化时所有都是空闲的）。每当被标记为已使用时，将其移除并放置在列表末尾，并使头指向下一个自由列表。以这种方式，您的列表将按“从空闲到已使用”的方式结构化。您还可以在O（1）中获得自由列表。此外，当id被标记为自由时-将其作为链表的第一个成员（因为它变为自由，因此可用），即使头指向该列表。希望这将有所帮助！

- rakib_

0

前言：二叉堆似乎确实是最好的答案。我在这里提出一种替代方案，可能在某些情况下具有优势。

一种可能的方法是使用Fenwick Tree。您可以在每个位置存储0或1，表示该位置已经被使用或未被使用。您可以使用二分查找找到第一个空位置（查找第一个范围[1..n]的和为n-1）。这个操作的复杂度是O(log^2 n)，比二叉堆更差，但这种方法还有其他优点：

您可以用不到10行代码实现Fenwick Tree
您现在可以在O(log n)的时间内计算范围的密度（已使用/总ID数）

- Juan Lopes

0

如果您不需要严格使用最低的ID，可以将模块的ID分批分配为1000个一组。释放ID时，它们可以添加到列表的末尾。偶尔您需要对列表进行排序，以确保再次分配的ID来自低端。

- Adrian Panasiuk

-1

嗯，数组可能不是最好的结构。至少就速度而言，哈希表会更好。至于每个“节点”的结构，我所能看到你需要的只是ID以及它是否被使用。

- Rui Brito

你会如何跟踪下一个可用的ID号码？ - templatetypedef

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

一种可能有效的初始想法是存储所有未使用ID的优先级队列，以使低ID在高ID之前出队。使用标准二叉堆，这将使返回未使用ID池中的ID的时间为O(log n)，并且查找下一个空闲ID的时间也为O(log n)。但是，这种方法的缺点是需要显式存储所有ID，如果ID数量非常大，则可能会浪费空间。

一种潜在的节省空间的优化方法是尝试将连续的ID值合并为ID范围。例如，如果您有自由ID 1、3、4、5、6、8、9、10和12，则可以仅存储范围1、3-6、8-10和12。这将要求您稍微更改底层数据结构。您可以使用存储范围的平衡二叉搜索树而不是使用二叉堆。由于这些范围不会重叠，因此可以将这些范围与其他范围进行比较。由于BST按排序顺序存储，因此可以通过获取树的最小元素（在O(log n)时间内）并查看其范围的低端来找到第一个空闲ID。然后，您将更新该范围以排除该第一个元素，这可能需要从树中删除一个空范围。当将ID返回到未使用ID池时，可以进行前驱和后继搜索以确定ID之前和之后的范围。如果其中任何一个可以扩展以包括该ID，则可以扩展范围（您可能还需要合并两个范围）。这也仅需要O(log n)时间。

希望这有所帮助！