我有一个包含 100 万个 id 的大数组/列表，然后我需要找到第一个可以使用的空闲 id。可以假设有几个模块引用该数据结构并获取一个id（在此期间应标记为已使用），然后稍后返回（应标记为空闲）。我想知道可以使用哪些不同的数据结构？以及我可以使用什么算法在时间和空间上（分别）有效地做到这一点。如果它已经在这里，请原谅，我在发布之前进行了搜索。
问问题
358 次
6 回答
7
一个可能可行的初始想法是存储所有未使用 ID 的优先级队列，排序后低 ID 在高 ID 之前出列。使用标准二叉堆，这可以在 O(log n) 时间内将 ID 返回到未使用的 ID 池，并在 O(log n) 时间内找到下一个空闲 ID。这样做的缺点是它需要您显式存储所有 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) 时间。
希望这可以帮助！
于 2013-06-12T18:12:01.823 回答
6
一种天真的但有效的方法是将所有 id 存储在堆栈中。获取 id 是一个恒定时间操作：弹出列表的第一项。当任务结束时，只需将 id 压入堆栈。
如果必须返回最低的空闲 id（而不是任何空闲 id），您可以使用最小堆插入并在 O(log N) 中弹出最低。
于 2013-06-12T18:11:12.830 回答
2
尝试使用链表（id 的链表）。链接所有这些列表，并且头部应该指向空闲列表（让我们说在初始化时都是免费的）。每当它被标记为已使用时，将其删除并将其放在列表的末尾，并使头部指向下一个空闲列表。这样，您的列表将以“从免费到使用”的方式构建。您还可以在 O(1) 中获得免费列表。此外，当一个 id 被标记为空闲时 - 将其作为链接列表的第一个成员（当它变得空闲时，它变得可用），即让 head 指向这个列表。希望这会有所帮助！
于 2013-06-12T18:16:45.640 回答
0
序言：二叉堆似乎确实是最好的答案。我将在这里提出一个替代方案，它在某些情况下可能具有优势。
一种可能的方法是使用Fenwick Tree。您可以在每个位置存储 0 或 1，表示某个位置已被使用或未使用。您可以通过二分搜索找到第一个空位置（找到第一个范围 [1..n] 的总和为 n-1）。这个操作的复杂度是O(log^2 n)，比二叉堆还差，但是这种方式还有另外一个优点：
- 不到 10 行代码就可以实现一棵 Fenwick 树
- 您现在可以计算 O(log n) 范围内的密度（已使用的数量/总 ID）
于 2013-06-12T20:37:39.733 回答
0
如果不严格要求最低的id，可以1000个为模块批量分配id。释放id的时候，可以加到list的后面。有时您会对列表进行排序，以确保您分配的 id 来自低端。
于 2013-06-12T22:08:43.160 回答
-1
好吧，数组可能不是最好的结构。至少在速度方面，哈希会更好。至于每个“节点”的结构，我可以看到你需要的只是 id，以及它是否正在使用。
于 2013-06-12T18:10:53.520 回答