有效地选择与列表的所有元素不同的整数

Question

我有一个对象的链接列表,每个对象包含一个32位整数(可证明少于2 ^32个这样的对象),我想有效地选择一个不在列表中的整数,而不使用任何额外的存储(所以将它们复制到一个数组,排序数组,并选择不在数组中的最小值将不是一个选项).但是,列表元素的结构定义在我的控制之下,因此我可以(在合理范围内)为每个元素添加额外的存储,作为解决问题的一部分.例如,我可以添加一组额外的prev/next指针并对列表进行合并排序.这是最好的解决方案吗？或者有更简单或更有效的方法吗？

Answer 1

考虑到您在注释中概述的条件,尤其是您对许多相同值的期望,您必须期望使用稀疏的已分配值.

因此,实际上最好只是随机猜测一个值,然后检查它是否与列表中的值一致.即使使用了一半的可用值范围(从您的评论中看起来极不可能),您也只能平均两次遍历列表.并且您可以通过同时检查一次通过的多个猜测来大幅减少此因素.如果做得恰当,因素应始终接近1.

这种概率方法的优点是您可以免受不良值序列的影响.使用基于范围的方法总是可以实现这样的序列:如果计算数据的最小值和最大值,则存在风险,即数据包含0和2^32-1.如果按顺序细分一个间隔,则存在始终在间隔中间获取值的风险,这可以在32个步骤中将其缩小为零.使用概率方法,这些序列不会伤害您.

我想,对于非常小的列表,我会使用类似于四个猜测的东西,并且当列表的大小接近极限时,将其调整到大约16.高起始值是由于任何此类算法都将受内存限制,即您的CPU在等待下一个值从内存到达时有足够的时间来检查值,因此您最好充分利用它时间减少所需的通行证数量.

进一步的优化会立即用新的猜测替换已被破坏的猜测并跟踪替换发生的位置,这样您就可以避免完成第二次数据传输.此外,将已破坏的猜测移动到猜测列表的末尾,这样您只需要检查循环中第一个猜测的起始位置,以便尽早停止.

Answer 2

如果你可以在每个对象中省略一个指针,那么你O(n)很容易得到最坏情况的算法(标准分而治之):

1. 平均划分可能的ID范围.
2. 制作一个涵盖每个子范围的单链表.
3. 如果一个子范围为空,请选择其中的任何ID.
4. 否则重复使用最少元素的子范围的元素.

每次迭代使用两个子范围的示例代码:

unsigned getunusedid(element* h) {
    unsigned start = 0, stop = -1;
    for(;h;h = h->mainnext)
        h->next = h->mainnext;
    while(h) {
        element *l = 0, *r = 0;
        unsigned cl = 0, cr = 0;
        unsigned mid = start + (stop - start) / 2;
        while(h) {
            element* next = h->next;
            if(h->id < mid) {
                h->next = l;
                cl++;
                l = h;
            } else {
                h->next = r;
                cr++;
                r = h;
            }
            h = next;
        }
        if(cl < cr) {
            h = l;
            stop = mid - 1;
        } else {
            h = r;
            start = mid;
        }
    }
    return start;
}

还有一些评论:

1. Beware of bugs in the above code; I have only proved it correct, not tried it.
2. 使用更多的桶(最好保持2的幂,以便轻松有效地处理)每次迭代可能会更快,因为更好的数据位置(尽管只有尝试和测量,否则它不够快),正如@MarkDickson 正确评论.
3. 如果没有这些额外的指针,你需要在每次迭代时完全扫描,将边界提高到O(n*lg n).

另一种方法是每个元素使用2+个额外指针来维护平衡树.这将加速id-search,代价是一些内存和插入/删除时间开销.

Answer 3

一种可能的解决方案是通过简单的迭代获取列表的最小值和最大值，然后选择和O(n)之间的数字。这很简单，因为无符号整数的上溢/下溢行为是明确定义的：maxmin + (1 << 32)

uint32_t min, max;
// TODO: compute min and max here

// exclude max from choice space (min will be an exclusive upper bound)
max++;

uint32_t choice = rand32() % (min - max) + max; // where rand32 is a random unsigned 32-bit integer

当然，如果不需要是随机的，那么你可以只使用比列表最大值多一个的值。

注意：唯一失败的情况是 if minis 0 且maxis UINT32_MAX（又名 4294967295）。