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

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值对应于下层数组有任何空闲槽的情况。您可以使用二进制搜索来遍历此结构。