c#创建一个随机唯一整数列表

本文关键字：随机 唯一 整数 列表 一个 创建 | 更新日期: 2023-09-27 18:13:01

我需要创建一个包含十亿个整数的列表，并且它们必须都是唯一的。我还需要尽快完成。

创建一个列表，一个接一个地添加随机数，并检查每个数字是否重复，这是非常慢的。

如果我只是用随机数填充列表而不检查它们是否重复，然后使用distinct(). tolist()，则似乎相当快。我重复这个，直到没有重复的。然而，创建新列表所使用的额外内存并不是最优的。是否有一种方法来获得distinct()的性能，而不是创建一个新的列表，它只是修改源列表?

c#创建一个随机唯一整数列表

我发现在保持随机性的情况下，这是最快的:

        Random rand = new Random();
        var ints = Enumerable.Range(0, numOfInts)
                                     .Select(i => new Tuple<int, int>(rand.Next(numOfInts), i))
                                     .OrderBy(i => i.Item1)
                                     .Select(i => i.Item2);

…基本上是给每个int赋一个随机id，然后按id排序并选择结果的int列表

整数需要在一定范围内吗?如果是这样，您可以创建一个数组或列表，其中包含该范围内的所有数字(例如从1到1000000000)，并对该列表进行洗牌。

您可以在单独的HashSet<int>中跟踪重复项:

var set = new HashSet<int>();
var nums = new List<int>();
while(nums.Count < 1000000000) {
    int num;
    do {
        num = rand.NextInt();
    } while (!set.Contains(num));
    set.Add(num);
    list.Add(num);
}

您需要一个单独的List<int>来存储数字，因为哈希集不会保留您的随机顺序。

从字面上理解这个问题(一个有10亿个整数的列表，它们必须都是唯一的):

Enumerable<int>.Range(0, 1000000000)

但是按照CodeCaster的答案，您可以创建列表并同时洗牌:

var count = 1000000000;
var list = new List<int>(count);
var random = new Random();
list.Add(0);
for (var i = 1; i < count; i++)
{
    var swap = random.Next(i - 1);
    list.Add(list[swap]);
    list[swap] = i;
}

如果您从中绘制的可能整数的数量明显大于您想要的整数数量(例如因子2)，您可以简单地使用HashSet<T>来检查重复。

List<int> GetUniqueRandoms(Random random, int count)
{
  List<int> result = new List<int>(count);
  HashSet<int> set = new HashSet<int>(count);
  for(int i = 0; i < count; i++)
  {
    int num;
    do
    {
      num = random.NextInt();
    while(!set.Add(num));
    result.Add(num);
  }
  return result;
}

为集合分配正确的容量，以避免在增长过程中重新分配。由于您的集合很大，这应该是一个很大的改进。

您也可以一次使用Distinct:

IEnumerable<int> RandomSequence(Random random)
{
    while(true)
    {
      yield return random.NextInt();
    }
}
RandomSequence(rand).Distinct().Take(1000000000).ToList();

但是对于这两种解决方案，您都需要足够的HashSet<int>和List<int>内存。

如果你抽取的可能整数的数量和你想要的整数的数量差不多，你可以创建一个包含所有整数的数组，洗牌，最后去掉那些你不感兴趣的。

您可以使用Jon Skeet的shuffle实现

如果您以排序但仍然随机的方式创建列表(例如将随机数添加到列表的最后一个元素作为下一个元素)，然后使用Fisher-Yates-Durstenfeld对列表进行洗牌会怎么样?总的来说，这将在线性时间内执行，这几乎和列表生成一样好。然而，它可能有一些显著的偏差，会影响分布。

您可以通过向OrderBy提供一个随机数lambda来欺骗LINQ为您混淆数字:

Random rand = new Random();
var ints = Enumerable.Range(0, 1000000000).OrderBy(i => rand.Next());
相关文章：