范围内整数分配

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是范围的数目，它通常非常小。它从1开始，但最多可以是n/2，这取决于用户发布的数字。

如果您想变得非常棘手，可以在范围上添加第二次排序，这会使较小的范围更接近“前面”，更大的范围更接近“结束”，当用户提供“可用”数字时，可以在“最小”范围内给出第一个值，这将启发式地导致较小的集合被“消耗”，从而使集合总数减少，从而平均节省空间。然而，这增加了大量的复杂性，也增加了少量的空间和时间，因此最坏的情况会变得更糟。在尝试之前先测量一下。

值得一提的是，这确实使用了线性空间，尽管我非常肯定常量是<=1，因此内存开销将小于存储所有数字的开销。如果不对用户分配和释放整数的方式进行假设，就很难计算平均值，但我非常肯定，平均内存使用量实际上更接近对数而不是线性。但很难说，这可能是乐观。

一些动态内存调度处理与此类似的概念，通常将“未使用”部分存储为未使用内存中的链接列表。这样，就不需要额外的开销空间了。由于您处理的是整数范围，而不是堆内存，因此此优化可能无助于您。