如何生成不在 IEnumerable 中的新 ID？

Question

我有一个 IEnumerable<int>，其中包含所有现有 ID。我想生成一个新的 ID，它是现有 ID 中不存在的任何 int。我有一个解决方案，但我想知道最好的方法。

// Inefficient solution
public static int GetFreshId(this IEnumerable<int> existingIds)
{
    int i = Int32.MinValue;
    while (existingIds.Contains(i)) // There is a case where all ids are taken!
    {
        i += 1;
    }
    return i;
}

更新：此处 best 定义为：

满足要求
可预测的性能
尽可能小的大哦
应该适用于任何 IEnumerable 实施，尽管对某些人来说比其他人更快
应该是无状态的

Answer 1

如果您不想使用最低的免费 ID，您可以简单地使用当前最大ID的后继者：

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    return existingIds.Max() + 1;
}

当然如果Int32.MaxValue和Int32.MinValue已经包含了就会有问题，所以你需要对这种情况进行一些特殊处理。

但是看到 Int32 范围内有多少个 ID，这种情况应该很少发生，因此可以针对这种极端情况实施更昂贵的算法。

如果你害怕溢出，你可以通过首先对序列进行排序然后扫描间隙来改进你的第一种方法（而不是测试每个可能的 int-value）：

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    int i = Int32.MinValue;
    foreach(int id in existingIds.OrderBy(id => id))
    {
        if (id != i) return i;
        if (i == Int32.MaxValue)
            throw new Exception("We ran out of IDs!");
        i += 1;
    }

    return i; // this now one more than the last/biggest existing ID
}

编辑：感谢 Ivan 指出了我的大错误，相应地改进了第二种方法

Answer 2

如果您确定您的 Id 永远不会有这么多项目 Int32.MaxValue，那么下面的速度就足够快了

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    return existingIds.Max() + 1;
}

Answer 3

您的解决方案的问题是循环执行的这行代码：

existingIds.Contains(i)

复杂度为O(N2)。改进它的一种方法是使用使用散列而不是索引的集合。例如 HashSet<T> :

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    var hashedIds = new HashSet<int>(existingIds);

    int i = Int32.MinValue;

    while (hashedIds.Contains(i)) ++i;    // now it use fast O(1) lookups

    return i;
}

Answer 4

我只是想添加一些异常处理。这不会在范围内丢失数字。

public static int GetFreshId(this IEnumerable<int> existingIds)
{
    if (existingIds == null) {
        throw new ArgumentNullException(nameof(existingIds));
    }
    if (!existingIds.Any()){
        return int.MinValue;
    }
    var lastId = existingIds.Max();
    if (lastId == Int.MaxValue){
        throw new ApplicationException("Sorry there are no more int available. Consider switching to int64.");
    }
    return lastId+1;
}

Answer 5

如果您的 ID 列表中没有任何空白

public static int GetFreshId(IEnumerable<int> existingIds) {    
    if (existingIds.Any()) {
        int i = existingIds.Max();  
        if (i == Int32.MaxValue) {
                throw new Exception("Ups...");
        }

        return i++;
    }

    return 1; // or what else
}

如果你可能有我认为你的解决方案没问题，也许只需添加检查以避免溢出

如何生成不在 IEnumerable 中的新 ID？

How do I generate a new id which is not in an IEnumerable?

c#

linq

ienumerable