python - セットにない数を見つける

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}where a、bandcはオブジェクト インスタンスです。このグループの値は一意であるため、グループ 1 にaあり、グループ 2 にあることがわかります。実際の数は関係ありません。グループの一意のキーに過ぎず、この構造の外部には何にも関連しません。実際の構造は 2 つのフィールドを持つデータベース テーブルであり、両方ともインデックスが付けられているため、たとえば と同じグループに他に何があるかをすぐに見つけることができます。cba

一意の番号が必要なのは、グループを追加するときです。これは頻繁に発生するわけではないので、それほど効率的である必要はありませんが、データ量が非常に大きくなる可能性があるため、反復回数を抑える必要があります。許容できる制限付きでこれを行う簡単な方法がいくつかあることを認識しています。たとえばrandint、大きな範囲 (1e6 など) を使用したり、場合によってはデータベース関数を使用したりすることもできます。しかし、私はこれについて考えてきたので、ハードコーディングされた制限なしで値を入力するためのきちんとした解決策を見つけることが興味深い問題になりました. 明らかに、メモリの制限 (整数の最大サイズなど) は引き続き適用されます。

Answer 1

セットにない任意の単一の整数

しかし、整数値は無限にあるため、有限集合に含まれない整数値も無限に存在します。有限範囲内の整数について話している場合を除きます（例：16ビット）。

最も効率的な解決策は、整数のセットがどれだけ完全であるかによって異なります。それがまばらな場合、ランダムに数値を選択すると、セットにない数値が返される可能性が高くなります。ギャップが少ない場合は、最適化された検索がより効率的になります。これらは両方とも、セットのソートされたリストを持つことに依存しています。

検索方法を見ると、データを分割することで検索を高速化できます。リスト内の数値の最小インデックスと最大インデックスの平均 M を計算します。データセット[M]<(M-dataset[0]) の場合、そうでない場合は、dataset[last]<(dataset[0]+last) かどうかを確認します。この場合、後半にギャップがあり、ギャップがあるデータの半分に対してプロセスを繰り返します。

Answer 2

どうmax(numbers)+1ですか??

Answer 3

必要なものが正確にわからない

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

Answer 4

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

Answer 5

いいえ、どんな数字でもかまいません。基本的に、辞書で使用するキーを生成しようとしています。

XY 問題のように聞こえます。

なぜ乱数で辞書をキーイングしているのですか? 辞書を使うべきですか？

ディクショナリの数値インデックスが必要な場合、最も簡単な方法は、最後に発行されたキーを記録し、別のキーが必要になったときに、この数値をインクリメントして使用することです。

削除や場合によっては再番号付けによってインデックスが欠落する問題は無視します。