Найти номер не в наборе

Question

Я пытаюсь найти разумно эффективный способ получить любое одиночное целое, но не в наборе. Например, если у меня есть numbers={1, 4, 9}, то действительным результатом будет 3. Я могу сделать это так:

n = random.randint(-100, 100) 
if n not in numbers: 
    return n 

Но я не хочу быть ограничены в произвольном диапазоне (например, -100 -> 100), так как я понятия не имею, как большой набор будет. Другой вариант - перебрать все целые числа, но это было бы ужасно неэффективно.

Есть ли у кого-нибудь какие-либо предложения относительно лучшего способа сделать это?

Редактировать: Из-за количества вопросов о том, что я пытаюсь сделать, я обновляю этот вопрос, чтобы объяснить некоторые из фона.

То, что я на самом деле пытается достичь, это отображение что-то вроде этого: {a: 1, b: 2, c: 1} где a, b и c являются экземплярами объектов. Значения в этом уникальном для группы, поэтому я могу сказать, что a и c находятся в группе 1, а b находится в группе 2. Фактическое число не имеет значения, это просто уникальный ключ для группы и не имеет отношения ни к чему вне эта структура. Фактическая структура представляет собой таблицу базы данных с двумя полями, обе из которых индексируются, так что я могу быстро узнать, например, что еще находится в той же группе, что и a.

Теперь, для чего мне нужен уникальный номер, это когда я хочу добавить группу. Это происходит не очень часто, поэтому это не должно быть невероятно эффективным, но поскольку объем данных может быть довольно большим, мне нужно сохранить количество итераций. Я понимаю, что есть несколько простых способов сделать это с приемлемыми ограничениями, например. используя randint с большим диапазоном (например, 1e6) или, возможно, даже с использованием функции базы данных. Но так как я думал об этом, стало интересно найти точное решение для заполнения значений без жестко заданных ограничений. Очевидно, что ограничения памяти (например, максимальный размер целого) все еще применяются.

Answer 1

любое одно целое число не в наборе

Но есть бесконечное число целочисленных значений, так что есть бесконечное число целочисленных значений не в конечном множестве. Если вы не говорите о целом в конечном диапазоне (например, 16 бит).

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

Если посмотреть на метод поиска, можно ускорить поиск путем разбиения данных: вычислить среднее значение M наименьшего и наивысшего индекса чисел в списке, если набор данных [M] < (M-dataset [0 ]), тогда есть пробел, в противном случае проверьте, установлен ли набор данных [последний] < (набор данных [0] + последний), в этом случае во втором тайме есть пробел, повторите процесс для половины данных, имеющих пробел.

Answer 2

что относительно max(numbers)+1 ??

Answer 3

def numnotinset(myset): 
    i = min(myset) 
    while True: 
    i += 1 
    if not i in myset: 
     return i 

Answer 4

Не полностью уверен, что именно то, что вам нужно

>>> numbers = {1, 4, 9} 
>>> from itertools import count 
>>> next(x for x in count() if x not in numbers) 
0 

Answer 5

Нет, это может быть любое количество. Я в основном пытаюсь сгенерировать ключи для использования в словаре.

Звучит как XY Problem.

Почему вы вводите словарь со случайными числами? Если вы даже используете словарь?

Если вам нужен индекс чисел, для словаря, самый простой способ сделать это - записать последний выданный ключ, а затем, когда вам понадобится другой, увеличьте это число и используйте его.

Вы игнорируете проблему отсутствия индексов, возникающих в результате делеций и/или иногда нумерации.