C # создание списка случайных уникальных чисел - PullRequest
Новая
       17

C # создание списка случайных уникальных чисел

2 голосов
/ 02 ноября 2011

Мне нужно создать список из одного миллиарда целых чисел, и все они должны быть уникальными.Мне также нужно, чтобы это было сделано очень быстро.

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

Кажется, этодовольно быстро, если я просто заполняю список случайными числами, не проверяя, являются ли они дубликатами, и затем использую Different (). toList ().Я повторяю это, пока больше нет дубликатов.Однако дополнительная память, используемая для создания нового списка, не является оптимальной.Есть ли способ получить производительность Different (), но вместо создания нового списка он просто изменяет исходный список?

Ответы [ 6 ]

13 голосов
/ 02 ноября 2011

Должны ли целые числа находиться в определенном диапазоне? Если это так, вы можете создать массив или список со всеми числами в этом диапазоне (например, от 1 до 1000000000) и перемешать этот список.

4 голосов
/ 18 октября 2015

Я нашел это самым быстрым при сохранении случайности: 

        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, а затем сортирует по этому идентификатору и выбирает результирующий список целых чисел.

2 голосов
/ 02 ноября 2011

Буквально взяв вопрос (список из одного миллиарда целых чисел, и все они должны быть уникальными): 

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 голосов
/ 02 ноября 2011

Вы можете отслеживать дубликаты в отдельном 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> для хранения чисел, потому что хэш-набор не сохранит ваш случайный порядок.

1 голос
/ 02 ноября 2011

Если количество возможных целых чисел, из которых вы черпаете, значительно больше (скажем, фактор 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> и a List<int>.

Если количество возможных целых чисел, из которых вы рисуете, примерно равно количеству целых чисел, которое вы хотите, вы можете создать массив, содержащий все из них, перемешатьи, наконец, отключите те, которые вам не интересны.

Вы можете использовать Реализация перемешивания Джона Скита .

0 голосов
/ 02 ноября 2011

Что если вы создали список отсортированным, но все еще случайным образом (например, добавление случайного числа к последнему элементу списка в качестве следующего элемента), а затем перетасовали список с помощью Fisher-Yates-Durstenfeld?Это будет выполняться в целом за линейное время, что почти так же хорошо, как и при создании списка.Однако он может иметь существенное смещение, которое может повлиять на распределение.

...