在巨大的位图中搜索第一个设置位

Question

面试问题:

在一个可容纳数百万辆汽车的停车位,您需要找到一个免费的停车位.槽可以在哪里没有条件,即停车场可以有多个入口并且在入口附近找到槽等等无关紧要.问题是应该使用什么样的数据结构以及各种操作的复杂性.

我建议使用百位的位数组,0/1用于获取/空闲时隙,因此为了找到自由点,问题转化为找到第一个设置位.不要假设有多少汽车等等,即钻头阵列可能稀疏或密集.

在巨大的位图中找到设置位的最快方法是什么？我建议每个单词的二进制搜索+高效ffs()作为方案.

Answer 1

一百万个32位整数需要大约4MB的内存.所以我要说你保留一个免费插槽列表.每当汽车进入时,您从列表中取出一个项目并进行分配.每当汽车离开时,您将释放的插槽号放入列表中.

因为你只是操纵列表的末尾(所以这实际上是用作堆栈或LIFO结构),这为你提供了最佳的O(1)性能,既可用于查找空闲插槽,也可用于将插槽返回到空闲状态州.如果你使用原始内存块在低级别执行此操作,则需要一个指示列表当前结尾的指针.查找槽会减少该指针并返回其值.返回一个插槽指定指针并在之后递增.

如果您决定稍后添加其他要求,则可以对数据进行一些操作,例如将其转换为堆.使用0/1位的大映射,这样的扩展是不可能的.

Answer 2

你可以这样走：

将最后一个空闲槽的索引存储在变量中，然后查找下一个，不要从头开始扫描位图，而是从该值开始扫描。

如果需要释放一些槽，请将其分配给最后一个索引。

std::vector<bool>可以是您的位数组，因此您不需要自己处理位（布尔值在内部打包为整数）。

你可以引入一个mip-mapped结构：

``std::vector<bool>`` Bitmap;
``std::vector<bool>`` Bitmap2; // half-sized
``std::vector<bool>`` Bitmap4; // 1/4
``std::vector<bool>`` Bitmap8; // 1/8
// etc

free上层数组中的值对应于下层数组有任何空闲槽的情况。您可以使用二分搜索来遍历此结构。