algorithm - 范围内的整数赋值

Question

我正在寻找一种从某个区间 [a,b] 分配和释放整数的算法。

每次我们请求赋值时，算法都会在 [a,b] 范围内生成一个以前未赋值过的整数。我们可以通过要求算法释放它们来释放之前分配的整数。这样做可以让它们再次用于分配。

总结一下:

• 一个整数赋值后，在释放之前不能再次赋值
• 如果没有分配一个或多个整数，则算法必须分配其中一个
• 当且仅当范围内的所有整数都被赋值时，算法不赋值

希望算法的时间和空间复杂度都是次线性的(对于 n = b - a)。

作为奖励要求，假设 [a,b] 中的某些特定整数需要进行初始分配。

Answer 1

首先想到的是从一个“可用”范围开始。当用户分配一个整数时，只需将其从范围中删除:

        [a,b]
a <---  [a+1,b]

这在所有情况下都是 O(1) 操作。由于返回步骤的工作方式，这意味着只有在没有其他数字可用时才分配最大数字，并且尽可能多地重复使用低数字。

当用户返回一个整数时，进行二分搜索以找出它在哪个范围之前，或者合并到:

[28][30-50]     <---- user is going to release 29
[28-50]
-or-
[26][30-50]     <----- user is going to release 28
[26][28][30-50]

这是一个 O(log m) 操作，其中 m 是范围的数量，通常非常小。它从 1 开始，但最多可以是 n/2，具体取决于用户释放的数字。

如果你想变得非常棘手，你可以在范围上添加第二个排序，将较小的范围移近“前面”，将较大的范围移近“末尾”，当用户输入数字时“available”，你给它们“最小”范围内的第一个值，这将试探性地导致更小的集合被“消耗”，留下更少的集合总数，从而平均节省空间。然而，这增加了很多复杂性，以及少量的空间和时间，所以最坏的情况会变得更糟。在尝试之前先测量。

值得一提的是，这确实使用了线性空间，尽管我很确定常量是<=1，所以内存开销会小于存储所有数字的开销。如果不对用户如何分配和释放整数做出疯狂的假设，很难计算出平均值，但我很确定平均内存使用率实际上更接近对数而不是线性。虽然很难说，但这可能是乐观的。

一些动态内存分配的工作原理与此类似，通常将“未使用”部分存储为未使用内存内部的链表。这样，就不需要额外的开销空间。由于您处理的是整数范围而不是堆内存，因此这种优化可能对您没有帮助。