Как создать новый идентификатор, который не находится в IEnumerable?

Question

У меня есть IEnumerable<int>, который содержит все существующие идентификаторы. Я хотел бы создать новый идентификатор, который является любым 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 реализация, albiet быстрее для некоторого t хань другие
• Должно быть без гражданства

Answer 1

Если вы не заботитесь, чтобы использовать наименьшую свободную ID вы можете просто взять преемника в настоящее время крупнейшим ID:

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

Конечно, есть будет проблемой, если Int32.MaxValueиInt32.MinValue уже содержатся, поэтому вам понадобится специальная обработка для этого случая.

Но, видя, сколько идентификаторов существует в диапазоне Int32, это редко случается, поэтому было бы неплохо реализовать более дорогой алгоритм для этого углового случая.

---

Если вы боитесь переполнения, вы можете улучшить свой первый подход сортировкой последовательности в первом, а затем сканирования для разрыва (вместо тестирования для каждого возможного 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 
} 

EDIT: Спасибо Иван бить меня в моей большой ошибкой, улучшил второй подход соответственно

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

, если у вас нет каких-либо пробелов в списке идентификаторов

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 
} 

, если вы, вероятно, я думаю, что ваше решение ОК, может быть, просто добавить проверку, чтобы избежать переполнения