コーディングしたい問題があります。0 から n-1 までの数字を生成するプロセスがあり、最初の繰り返し要素を生成するときにそれを停止したいと考えています。* これを高速化するデータ構造を探しています。特に、新しい要素の追加と、要素が構造内にあるかどうかのテストは高速である必要があります。予想される挿入数は、およそ sqrt(n) (誕生日の問題) か、実際にはもう少し悪い (sqrt(2n) など) です。プロセスが一意の値をわずかに優先するからです。言い換えれば、かなりまばらです。10 億までの数値を扱う場合、約 3 万または 5 万の値しか使用されません。
ハッシュ セットまたはある種の自己均衡二分木が正しいアプローチのように思えますが、もっと良い方法があるのではないでしょうか? 小さい n の場合、ビット配列の方が優れていると思いますが、10 ^ 9 前後の n を見ていると、大きすぎて実用的ではないと思います。
* 実際には、すぐに停止する必要はありません。より効率的であれば、要素をブロックで生成し、時々チェックすることができます。
注: これはもともと math.se に投稿されたものですが、ここに再投稿することを勧められました。これは研究レベルではないため、cstheory.se には適していません。