数据结构推荐 [英] Data structure recommendation

问题描述

使用Java开发时，我需要一个数据结构来选择0到999999之间的N个不同的随机数？

Developing in Java, I need a data structure to select N distinct random numbers between 0 and 999999 ?

我希望能够快速分配N个数字并确保他们不会重复自己。

I want to be able to quickly allocate N numbers and make sure they don't repeat themselves.

主要目标是不使用过多的内存并保持性能合理。

Main goal is not to use too much memory and still keep performance reasonable.

我正在考虑使用 BitSet 但是我不确定内存是否有影响。
有人可以告诉我此类的内存​​要求与位数还是与设置位数有关吗？

I am considering using a BitSet But I am not sure if the memory implications. Can someone tell me if the memory requirements of this class are related to the number of bits or to the number of set bits? and what is the complexity to setting/testing a bit ?

更新：
感谢到目前为止的所有答复。

UPDATE: Thanks for all the replies so far.

我认为我在此Q的最初措词中有此内容，但是当我第一次看到BitSet类时将其删除。
无论如何，我想添加以下信息：
当前，我正在查看的最多是几千个N（最有可能在1000-2000附近），范围是0到999999。
但是我希望选择将范围增加到8位（即0到99 999 999），同时将N保持在大致相同的范围（可能将其增加到5K或10K）的选择。
因此使用的值非常稀疏。

I Think I had this in my initial wording of this Q but removed it when I first saw the BitSet Class. Anyway I wanted to add the following info: Currently I am looking at N of a few thousands at most (most likely around 1000-2000) and a number range of 0 to 999999. But I would like my choice to take into consideration the option of increasing the range to 8 digits (i.e. 0 to 99 999 999) while keeping N at roughly the same ranges (maybe increase it to 5K or 10K). So the "used values" are quite sparse.

推荐答案

这取决于的大小N 是。

对于较小的 N ，可以使用 HashSet< Integer> 来保存您已经发出的号码。这样可以查找 O（1）和 O（N）空间。

For small values of N, you could use a HashSet<Integer> to hold the numbers you have already issued. This gives you O(1) lookup and O(N) space usage.

A BitSet 在范围0-999999中将使用大约125Kb，无论 N 。对于 N 足够大的值，这将比 HashSet 更加节省空间。我不确定 N 的确切值是 BitSet 将使用更少的空间的地方，但是我的客户评价会是10,000到20,000。

A BitSet for the range 0-999999 is going to use roughly 125Kb, regardless of the value of N. For large enough values of N, this will be more space efficient than a HashSet. I'm not sure exactly what the value of N is where a BitSet will use less space, but my guestimate would be 10,000 to 20,000.




有人可以告诉我<$ c的内存要求吗？ $ c> BitSet 与位数或设置位数有关？

Can someone tell me if the memory requirements of BitSet are related to the number of bits or to the number of set bits?

大小由设置的最大位决定，或者由 nBits 参数决定（如果使用 BitSet（int nBits）构造函数。

The size is determined either by the largest bit that has ever been set, or the nBits parameter if you use the BitSet(int nBits) constructor.

设置/测试位的复杂性是什么？

and what is the complexity to setting/testing a bit ?

测试位 B 是 O（1）。

设置位 B 是 O（1）的最佳情况，而 O（B）如果需要扩展位集支持数组。但是，由于支持阵列的大小是2的第二大幂，因此通常可以通过多次 BitSet 操作来摊销扩展成本。

Setting bit B is O(1) best case, and O(B) if you need to expand the bitset backing array. However, since the size of the backing array is the next largest power of 2, the cost of expansion can typically be amortized over multiple BitSet operations.

这篇关于数据结构推荐的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！