如何生成一个不在IEnumerable中的新id

本文关键字：IEnumerable id 一个 何生成 | 更新日期: 2023-09-27 18:01:50

我有一个包含所有现有id的IEnumerable<int>。我想生成一个新的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;
}

更新:这里最好的定义为:

  • 符合要求
  • 可预测性能
  • 最小的大-哦可能
  • 应该适用于任何IEnumerable实现，尽管有些比其他更快
  • 应该是无状态的

如何生成一个不在IEnumerable中的新id

如果你不想使用最小的自由 ID，你可以简单地取当前最大ID的后继ID:

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

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

但是看看在Int32范围内有多少ID，这种情况应该很少发生，所以对于这种情况，实现一个更昂贵的算法是可以的。

如果您担心溢出，您可以通过先对序列进行排序，然后扫描间隙(而不是测试每个可能的int -值)来改进第一种方法:

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告诉我我的大错误，并相应地改进了第二种方法

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

existingIds.Contains(i)

复杂度为0 (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;
}

我只是想添加一些异常处理。这将不会得到范围中缺失的数字。

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;
}

如果你确定你不会有那么多的项目，你的Id等于Int32。

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

如果你的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
}

如果你有可能我认为你的解决方案好吧，也许可以添加检查以避免溢出

相关文章：