Ris*_*uri 4 c algorithm data-structures
我有一个100万id的大数组/列表,然后我需要找到可以使用的第一个免费ID.可以假设有几个模块引用该数据结构并取一个id(在此期间它应标记为已使用),然后稍后返回(应标记为空闲).我想知道可以使用哪些不同的数据结构？我可以用什么算法有效地实现时间和空间(单独).请原谅,如果它已经存在,请在发布之前进行搜索.
可能有效的一个初步想法是存储所有未使用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)时间.
希望这可以帮助!
一种天真但有效的方法是将所有ID存储在堆栈中.获取id是一个恒定时间操作:弹出列表的第一项.当任务结束时,只需将ID推入堆栈即可.
如果必须返回最低的空闲id(而不是任何空闲id),则可以使用带插入的最小堆,并在O(log N)中弹出最低值.