Генерировать случайные числа без повторений

Я хочу сгенерировать список из N различных случайных чисел:

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

Но я чувствую, что есть лучший способ. Этот do...while цикл особенно делает это уродливым. Любые предложения о том, как улучшить это?

84 голоса | спросил Kao 28 PM00000050000000931 2014, 17:35:09

16 ответов


79
  

Обновленный ответ в ответ на награду: см. Это ваш окончательный ответ? в конце и другие изменения - в основном ответ значительно переписан.


Чтобы решить проблему, выполните следующие действия:

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

Ваш текущий код указывает, что диапазон случайных чисел указан Random.Next(), который возвращает значения в диапазоне [0 .. Int32.MaxValue) (обратите внимание, что исключает Int32.MaxValue). Это важно для этого вопроса, потому что другие ответы предполагают, что диапазон настраивается и «мал».

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

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

Стиль кода

do ... while

Наиболее вопиющими проблемами здесь являются нестрочный цикл do-while. Вы уже это знали, но этот код уродливый:

    do number = random.Next();
    while (randomNumbers.Contains(number));

Он действительно должен быть привязан :

    do
    {
        number = random.Next();
    } while (randomNumbers.Contains(number));

Это делает утверждение понятным и значительно уменьшает путаницу. Всегда используйте брекеты для 1-лайнеров.

Конструкция списка

Класс List позволяет использовать начальную емкость, которая будет использоваться . Поскольку емкость должна быть просто count, имеет смысл инициализировать список этой емкостью:

List<int> randomNumbers = new List<int>(count);

Текущий алгоритм

Здесь можно сделать самые интересные наблюдения. Давайте проанализируем ваш текущий алгоритм:

  • Создайте контейнер для результатов
  • повторите, пока вы не выбрали значения N:
    • Выберите случайное значение
    • проверьте, был ли он ранее выбран
    • , если он «новый», а затем добавьте его в контейнер

Этот алгоритм будет производить случайные значения в произвольном порядке и с хорошими случайными характеристиками (без ошибок, смещений, пробелов и т. д.).

Другими словами, ваши результаты хороши.

Проблема с производительностью ....

Здесь есть две проблемы с производительностью: одна маленькая, другая большая:

  1. цикл do-while, чтобы избежать столкновений
  2. контейнер списка

do-while performance

До-пока очень мало влияет на производительность ... почти незначительно. Это горячо обсуждается, но реальность такова, что вам понадобится очень, очень большой count, прежде чем это станет проблемой. Обоснование таково:

Столкновения происходят, когда случайное значение было ранее выбрано. Для указанного диапазона [0 .. Int32.MaxValue) вам понадобится очень большой count, прежде чем столкновения действительно произойдут. Например, count должно быть около 65 000, прежде чем вероятность того, что будет хоть один столкновение, будет лучше, чем 50%.

В общем смысле, учитывая диапазон \ $ N \ $, выберите числа \ $ M \ $. Если \ $ M <\ sqrt {N} \ $, то вероятность единственного столкновения равна <50%. Поскольку диапазон очень велик, вероятность мала.

Очевидно, если диапазон был мал, то вероятности были бы существенно затронуты. Но диапазон зафиксирован в Int32.MaxValue, так что все в порядке.

Кроме того, если число count велико, тогда также будут затронуты вероятности. Насколько велика будет большая? Ну, вы столкнулись бы с очень большими массивами, прежде чем столкнетесь с серьезными проблемами ..... Я бы рискнул, что вы попадаете близко к \ $ \ frac {Int32.MaxValue} {2} \ $, прежде чем заходить в значительная проблема с производительностью.

Производительность списка

Это, без сомнения, ваша самая большая забота. Вы используете вызов randomNumbers.Contains(number), чтобы определить, было ли ранее выбрано значение. Для этого требуется проверка всех ранее выбранных значений. Как уже упоминалось, это почти всегда возвращает false и, следовательно, придется сканировать весь список.

По мере того, как значение count увеличивается, продолжительность выполнения Contains будет возрастать с квадратичной скоростью, \ $ O (n ^ 2) \ $, где n - n.

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

Совмещение

Проблема, которую вы имеете в своем коде, заключается в том, что вы пытаетесь сделать слишком много сразу, вы используете список, потому что это ваше возвращаемое значение, когда HashSet будет лучше. Если вы нарушитепроблема вниз к этапам, вы сможете решать вещи более элегантно.

Если вы добавляете дублирующее значение в HashSet, оно не растет, и производительность операции не зависит от количества данных в HashSet (это \ $ O (1) \ $). Вы можете использовать count для HashSet для управления уникальностью данных.

Как только у вас есть чистый набор уникальных случайных чисел, вы можете сбросить их в список, а затем перетасовать список, используя эффективную перетасовку.

Сочетание этих структур данных, в правильном направлении, приводит к общему решению \ $ O (n) \ $, которое будет достаточно хорошо масштабироваться.

Вот какой код, который работает в Ideone слишком . Заметьте, мой C # слаб, поэтому я попытался сделать логику понятной.

Count

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

Второй альтернативный алгоритм

Проблема с указанным алгоритмом трижды:

  1. Когда счетчик очень велик, вероятность столкновения увеличивается, а производительность может быть затронута.
  2. В какой-то момент данные должны быть как в HashSet, так и в List, поэтому использование пространства удваивается.
  3. Перемешивание в конце необходимо для хранения данных в произвольном порядке (HashSet не сохраняет данные в каком-либо конкретном порядке, а алгоритм хеширования приведет к смещению порядка и искажению).

Это только проблемы с производительностью, когда счетчик очень большой. Обратите внимание, что только столкновения при большом количестве будут влиять на масштабируемость решения (при больших значениях он больше не является вполне $ $ (n) \ $, и он будет становиться все хуже, когда count приближается к using System; using System.Collections.Generic; public class Test { static Random random = new Random(); public static List<int> GenerateRandom(int count) { // generate count random values. HashSet<int> candidates = new HashSet<int>(); while (candidates.Count < count) { // May strike a duplicate. candidates.Add(random.Next()); } // load them in to a list. List<int> result = new List<int>(); result.AddRange(candidates); // shuffle the results: int i = result.Count; while (i > 1) { i--; int k = random.Next(i + 1); int value = result[k]; result[k] = result[i]; result[i] = value; } return result; } public static void Main() { List<int> vals = GenerateRandom(10); Console.WriteLine("Result: " + vals.Count); vals.ForEach(Console.WriteLine); } } . Обратите внимание, что в реальной жизни это вряд ли когда-либо произойдет ... и память станет проблемой до того, как производительность будет выполнена.

@JerryCoffin указал на альтернативный алгоритм Боба Флойда, где трюк играет, чтобы избежать столкновения. Это решает проблему масштабируемости при очень больших значениях. Это не решает проблему как для HashSet, так и для List, и это не решит необходимость перетасовки.

Представленный алгоритм:

Int32.MaxValue

предполагает, что initialize set S to empty for J := N-M + 1 to N do T := RandInt(1, J) if T is not in S then insert T in S else insert J in S возвращает значения включительно .

Чтобы понять описанный выше алгоритм, вам нужно понять, что вы выбираете случайное значение из диапазона, который меньше, чем полный диапазон, а затем после каждого значения вы расширяете его, чтобы включить еще один. В случае столкновения вы можете безопасно вставить max, потому что никогда не было возможности включить его раньше.

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

Это почти окончательный ответ? Нет

Итак, используя приведенное выше решение, в C # будет выглядеть как (в Ideone) (обратите внимание, код теперь отличается от Ideone):

RandInt(1, J)

Обратите внимание, что вам нужно все равно перетасовать результаты, чтобы проблема HashSet была устранена. Также обратите внимание на необходимость выполнения фэнтези-контура public static List<int> GenerateRandom(int count) { // generate count random values. HashSet<int> candidates = new HashSet<int>(); for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++) { Console.WriteLine(top); // May strike a duplicate. if (!candidates.Add(random.Next(top + 1))) { candidates.Add(top); } } // load them in to a list. List<int> result = candidates.ToList(); // shuffle the results: int i = result.Count; while (i > 1) { i--; int k = random.Next(i + 1); int value = result[k]; result[k] = result[i]; result[i] = value; } return result; } , потому что во время переполнения все становится беспорядочным.

Вы можете избежать тасования?

Итак, это решает необходимость выполнить цикл столкновений, но как насчет тасования. Это можно решить, поддерживая одновременно HashSet и List . Нет! Рассмотрим эту функцию (также в Ideone) :

top > 0

Вышеприведенный ответ никогда не позволит первому значению в результате иметь любой из значений public static List<int> GenerateRandom(int count) { List<int> result = new List<int>(count); // generate count random values. HashSet<int> candidates = new HashSet<int>(); for (Int32 top = Int32.MaxValue - count; top < Int32.MaxValue; top++) { // May strike a duplicate. int value = random.Next(top + 1); if (candidates.Add(value)) { result.Add(value); } else { result.Add(top); candidates.Add(top); } } return result; } до Max - Count (потому что никогда не будет столкновения по первому значению, а диапазон не является полным в этой точке), и это, таким образом, является разбитым случайным генератором.

Даже с помощью этого алгоритма избегания столкновений вам все равно нужно перетасовать результаты, чтобы обеспечить чистое смещение чисел.


TL; DR

Это ваш последний ответ? Да!

Играя с этим кодом много, очевидно, что полезно иметь вход на основе диапазона, а также систему Int32.MaxValue. Мессинг с большими диапазонами приводит к потенциальному переполнению в 32-разрядном целочисленном пространстве.

Работа с @mjolka, следующий код будет лучшим из обоих миров:

Max
ответил rolfl 28 PM00000080000004531 2014, 20:18:45
35

Да, определенно есть.

Вы создаете коллекцию элементов, затираете их и начинаете вытаскивать элементы из него. Быстрая oneliner будет:

Enumerable.Range(0,100).OrderBy(x => Guid.NewGuid()).Take(20);

или, альтернативно,

Enumerable.Range(0,100).OrderBy(x => random.Next()).Take(20);

Это даст вам 20 уникальных случайных значений в диапазоне от 0 до 100.

Разница с вашим подходом заключается в том, что у вас есть наихудший сценарий бесконечности: что делать, если вам не повезло и в конечном итоге с тем же значением постоянно? Вы никогда не получите требуемое количество случайных значений.

Мой подход с другой стороны сначала сгенерирует 100 значений, а затем возьмет подмножество, из которого вы можете критиковать влияние своей памяти. Учитывая, что вы использовали random.Next(), который использует половину целочисленного диапазона, на самом деле вы должны быть осторожны, так как он будет иметь огромное влияние на память.

Это также зависит от конкретной ситуации: если у вас очень большой пул значений (1.000.000), и вам нужны 2 случайных значения, ваш подход будет намного лучше. Но когда вам нужно 999.999 значений из того же пула, мой подход будет намного лучше по-прежнему быть спорным.

Потребуется некоторое время для создания этих последних значений; a lot , так как вы можете сами убедиться в этом:

void Main()
{
    var random = new Random();
    var times = new TimeSpan[512];
    var values = new bool[512];
    var sw = new Stopwatch();

    for(int i = 0; i < times.Length; i++) 
    {   
        sw.Restart();
        while(true) {
            int rand = random.Next();

            if(rand > 7894500 && rand < 7894512) 
            {
                int index = rand - 7894500;
                if(!values[index])
                {
                    values[index] = true;
                    break;
                }
            }
        }
        sw.Stop();
        times[i] = sw.Elapsed;
        Console.WriteLine ("Elapsed time: " + sw.Elapsed);
    }

    var orderedTime = times.OrderBy(x => x);
    for(int i = 0; i < 512; i++)
    {
        Console.WriteLine (orderedTime.ElementAt(i));
    }
}

Он будет циклически перемещаться по 512 раз через список значений и считать элемент найденным после того, как он обнаружит (случайно выбранные мной) значения между 7894500 и 7894512 , Впоследствии это значение считается посещенным, чтобы правильно имитировать реальность (в более ранней версии все 512 оборотов имели 512 значений, доступных для них). Когда вы выполняете это, вы заметите, что для получения последних значений требуется много времени (иногда это быстро и требуется 39 мс, а иногда - более минуты). Очевидно, что это быстро в начале и замедляется в конце.

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

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

В конечном итоге, в экстремальной ситуации, когда вам нужно 32 миллиона уникальных значений в рандомизированном порядке из общей численности населения 32 миллиона + 1, вам придется либо принять накладные расходы большой памяти, либо большие накладные расходы.


Последнее редактирование до того, как эта тема может быть отложена с моей стороны: я говорил об этом с @rolfl в чате, и мы пришли к выводу, что у любого из наших решений есть использование, но это зависит от вашей ситуации в точку. Подводя итог, он пришел к следующему:

Если у вас большой диапазон значений (например, от 0 до int.MaxValue), тогда мое решение будет есть любую память вашего ПК. Вы просматриваете две коллекции с целыми числами в 2,1 миллиарда, которые вы затем берете с сайта.

В моем решении вы сначала выделяете всю эту совокупность, затем сортируете по ней (разные структуры данных), а затем берете некоторые из них. Если этот «некоторый» не близок к 2,1 миллиарду, вы потратите огромные средства на распределение данных, не используя его.

Как это соотносится с ответом @ rolfl ? Он в основном выделяет данные по мере необходимости: если ему нужно 32 миллиона значений, то он будет выделять только 32 миллиона (x2) и не более. Если ему нужно 2,1 миллиарда, то у него будет след на память, как у меня, но это необычный худший сценарий, хотя для меня это стандартное поведение.

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

Итак, когда вы должны использовать мое решение? Как и большинство вещей, существует компромисс между читабельностью и производительностью. если тыпо моему мнению, имеют относительно небольшую численность населения и большой набор данных, а затем, по моему мнению, наглядно демонстрирует влияние производительности. И когда население относительно невелико, и количество ценностей, которое мы хотим, близко к этому, мое решение будет иметь эффект памяти, аналогичный влиянию другого подхода, но также позволит избежать многих столкновений.

Возьмите свой выбор в зависимости от вашей ситуации.

ответил Jeroen Vannevel 28 PM00000050000004431 2014, 17:44:44
21

Вместо использования List<int> вы должны использовать HashSet<int>. HashSet<> запрещает несколько одинаковых значений. И метод Add возвращает bool, который указывает, был ли элемент добавлен в список, таким образом вы могли бы изменить этот код:

public static List<int> GetRandomNumbers(int count)
{
    List<int> randomNumbers = new List<int>(); 

    for (int i=0; i<count; i++) 
    {    
        int number;

        do number = random.Next();
        while (randomNumbers.Contains(number));

        randomNumbers.Add(number);
    }

    return randomNumbers;
}

:

public static IEnumerable<int> GetRandomNumbers(int count)
{
    HashSet<int> randomNumbers = new HashSet<int>();

    for (int i = 0; i < count; i++) 
        while (!randomNumbers.Add(random.Next()));

    return randomNumbers;
}

Обратите внимание, что я изменил возвращаемое значение из List<int> на IEnumerable<int>, если вы не планируете добавлять /удалять значения из своего списка, вы должны вернуть IEnumerable<int>, если вы планируете это сделать, верните ICollection<int>. Вы не должны возвращать List<int>, потому что это деталь реализации и что List<> не является расширяемым.

ответил IEatBagels 28 PM00000060000002931 2014, 18:19:29
18

Расширение моего комментария. Это называется линейным конгруэнтным генератором. Я использовал общие параметры, которые исходят из того, что, на мой взгляд, называется минимальным стандартом. Можно выбрать другие параметры, но это сложная задача. Последовательность начинается с семени, доходит до всех остальных чисел от 0 до M-1, а затем перезапускается, как только она снова достигает семени. Это псевдослучайно. 507111939 всегда следует за 285719. Поскольку последовательность достигает всех M чисел, на любых M последовательных выходах последовательности не будет дубликатов.

код:

class RandomSequence {

  int actual;
  static final int M = (1<<31) -1;

  public RandomSequence(int seed) {
    this.actual = seed
  }

  public int next() {
    return this.actual = (16807 * this.actual) % RandomSequence.M
  }

}

Использование:

//...
List<int> awesomeList = new List<int>();
RandomSequence sq = new RandomSequence( RandomUtil.getRandomPositiveIntSmallerThanM() );
for(int i = 0; i < n; i++) {
  awesomeList.add(sq.next());
}
ответил Olivier 30 AM000000110000004031 2014, 11:54:40
13

Алгоритм отлично выглядит для меня. Он не показывает явных недостатков и прекрасно работает в обычных случаях.
Для крайних случаев выбора большинства чисел в очень большом интервале это будет очень неэффективно. Но если это не ожидаемый вариант использования, я бы не стал менять код на более сложные подходы.

Но я предлагаю вам всегда использовать явные скобки вокруг блоков, даже если у них есть один оператор:

do
{
    bar();
}
while (foo);

Я бы также переименовал метод в GetNRandomNumbers, чтобы имя метода совпадало с его целью.

ответил ANeves 28 PM00000050000003031 2014, 17:40:30
9

Другим решением является использование шифрования шифрования форматирования (например, AES с использованием режима FFX), настроенного для сопоставления от 32-битных целых чисел до 32-битных целых чисел.

Взять его случайным образом, а затем просто зашифровать первые целые числа.

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

ответил BenGoldberg 29 PM000000110000005931 2014, 23:40:59
8

Я обновляю свой ответ, чтобы провести анализ алгоритма BobFloyd и подытожить все недостатки, которые я смог обнаружить на нем. Некоторые из них были в моем предыдущем ответе, они также упоминаются в некоторых комментариях пользователей, таких как @rolfl и @firda. Пожалуйста, следуйте всему ответу, потому что у вас будет сюрприз в конце.

Позвольте мне определить некоторые термины, которые я буду использовать в своем ответе. Рассмотрим определение метода:

static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
  • диапазон длина = макс - мин + 1
  • принятых элементов = count

Первая проблема: Последние элементы элементов не могут быть в индексе 0 результата.

Вторая проблема: Результаты приближаются к линейной последовательности, поскольку range length - taken elements приближаются к длине диапазона taken elements. Это легче увидеть, когда они одинаковы, но результат не является случайным вообще, когда они близки.

Третий вопрос: Существует также третья проблема, но я просто упомянул об этом в конце моего ответа.

Я реализовал три алгоритма для возврата не повторяющихся чисел:

Чистый алгоритм перетасовки, чистый алгоритм Боба Флойда и алгоритм Боба Флойда с перетасовкой. Они появятся позже, когда я сравню и протестирую их.

Я также внедрил тест для проверки случайности выводимого списка любым алгоритмом. Хотя он имеет некоторые ограничения, этого будет достаточно для полноты /правильности ответа. По большому счету, это может быть мое определение быть случайным. Здесь я в основном рассчитываю время, в которое каждая комбинация возникает, и посмотрите, находится ли среднее значение в допустимом диапазоне.

range length

Итак, давайте начнем с проверки случайности нашего алгоритма перетасовки, это мой первый алгоритм:

public void TestRandomness(Func<List<int>> getRandomList, int rangeLength, int count)
{
    long combinations = (long)(rangeLength.Factorial(rangeLength - count + 1));
    long iterations = combinations * 100;
    var partitioner = Partitioner.Create(0, iterations, iterations / 4);
    ConcurrentDictionary<long, int> ocurrences = new ConcurrentDictionary<long, int>(Environment.ProcessorCount, (int)combinations);

    Parallel.ForEach(partitioner, new ParallelOptions() {MaxDegreeOfParallelism = Environment.ProcessorCount},
        range =>
        {
            //hopefully having a private dictionary will help concurrency
            Dictionary<long, int> privateOcurrences = new Dictionary<long, int>();
            for (long i = range.Item1; i < range.Item2; ++i)
            {
                var list = getRandomList();
                long acc = 0;
                //this will only work when numbers are between 0 and 88
                foreach (var value in list)
                {
                    acc = (value + 11) + acc*100;
                }
                privateOcurrences.AddOrUpdate(acc, 1, v => v + 1);
            }
            foreach (var privateOcurrence in privateOcurrences)
            {
                ocurrences.AddOrUpdate(privateOcurrence.Key, 
                    privateOcurrence.Value,
                    (k, v) => v + privateOcurrence.Value);
            }
        });

    double averageOcurrences = iterations / combinations;
    double currentAverage = ocurrences.Values.Average();
    Debug.WriteLine("The average ocurrences of this implementation is {0} comparing to {1} in the 'perfect' scenario", currentAverage, averageOcurrences);
    Assert.Less(currentAverage, averageOcurrences * 1.05);
    Assert.Greater(currentAverage, averageOcurrences * 0.95);
}

Пройти, пройти, пройти. Этот алгоритм оценивает мое тестовое определение случайности. Это очень близко к тому, что указывал @Jeroen Vannevel, за исключением части, для которой это не требует случайности, и не работает в O (n log n) времени (мне нужно обратиться к @Andrew Piliser, потому что он был единственным, кто комментировал об этом).

Как мы знаем, этот алгоритм будет считать память эквивалентной O (длина диапазона), и это его главный недостаток. Однако он не создает коллизий и гарантирует случайность.

Пришло время доказать первые и две проблемы с алгоритмом Боба Флойда:

[Test]
public void TestShuffleRandomness()
{
    TestRandomness(() => Enumerable.Range(0, 16).ToList().Shuffle().Take(4).ToList(), 16, 4);    
}

Отлично, теперь мы доказали, что алгоритм Боба Флойда по своему усмотрению не решает эту проблему, и, конечно же, он не прошел бы мой тест на случайность.

public static IEnumerable<int> BobFloydNonRepeatingSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    return values;
}

[Test]
public void TestLastCountElementsAreNotInIndex0()
{
    for (int i = 0; i < 1000000; ++i)
    {
        var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList();
        Assert.IsFalse(new[] { 12, 13, 14, 15 }.Contains(list[0]));
        Assert.AreEqual(4, list.Count);
    }
}

[Test]
public void TestBobFloydBecomesLinear()
{
    var list = Sequence.BobFloydNonRepeatingSequence(0, 15, 16).ToList();
    for (int i = 0; i < list.Count; ++i)
    {
        Assert.AreEqual(i, list[i]);
    }
}

Наш единственный вариант - перетасовать результаты и надеяться на лучшее.

[Test]
public void TestBobFloydRandomness()
{
    TestRandomness(() => Sequence.BobFloydNonRepeatingSequence(0, 15, 4).ToList(), 16, 4);
}

Посмотрим, что говорит об этом мой тест на случайность:

public static IEnumerable<int> NonRepeatingRandomSequence(int min, int max, int count, int? seed = null)
{
    Random random;
    if (seed != null)
    {
        random = new Random(seed.Value);
    }
    else
    {
        random = new Random();
    }
    long length = max - min + 1;
    INonRepeatingList values = NonRepeatingListFactory.GetNonRepeatingList(min, max, count);
    for (int i = (int)(length - count); i < length; ++i)
    {
        if (!values.Add(random.Next(min, i+min+1)))
        {
            values.Add(i+min);
        }
    }
    values.Shuffle();
    return values;
}

Надеюсь, вы не слишком сильно возлагали свои надежды. Мой случайный тест терпит неудачу , это третий и последний номер с Бобом Флойдом вообще, потому что он не будет случайным. Или, по крайней мере, это не соответствует определению случайности, которое я предоставил.

Этот бит будет просто обсуждать мою реализацию алгоритма Боба Флойда vs rolfl one

Итак, скажем, мое определение случайности является немного строгим или алгоритм перетасования Боба Флойда достаточно случайен для ваших целей. Я действительно не знаю, чего не хватает в реализации, чтобы результаты были более случайными, поэтому он остается только об эффективности.

Как вы видели в моей реализации, я получаю INonRepeatingList из метода [Test] public void TestBobFloydWithShuffleRandomness() { TestRandomness(() => Sequence.NonRepeatingRandomSequence(0, 15, 4).ToList(), 16, 4); } .

NonRepeatingListFactory.GetNonRepeatingList

Этот метод определяет, какой список использовать на основе занимаемой памяти. Если вы используете HashSet всегда, как @rolfl, вы предполагаете, что вы будете занимать много памяти, когда принимаемые элементы большие, а дальность действия также велика. В этой ситуации вы можете просто скорректировать значение. Какая разница в этом? Это примерно 1 КБ памяти для каждой длины диапазона 8 КБ. С другой стороны, если мы берем несколько элементов из широкого диапазона, мы должны использовать HashSet.

public class NonRepeatingListFactory
{
    public static INonRepeatingList GetNonRepeatingList(int min, int max, int count)
    {
        long length = max - min + 1;
        if (length / 8 > count * 2 * sizeof(int))
        {
            //if the amount of bytes occupied by the array is greater then the dictionary
            return new RandomIndexNonRepeatingList();
        }
        return new NonRepeatingList(min, max);
    }
}

Полный код pastebin

ответил Bruno Costa 3 rdEurope/Moscowp30Europe/Moscow09bEurope/MoscowWed, 03 Sep 2014 00:39:46 +0400 2014, 00:39:46
6

Хотя решение byr @Jeroen Vannevel довольно простое и работает для большинства целей и задач, вы увидите особенно плохую производительность, если вы просто хотите, чтобы несколько номеров были из очень большого диапазона.

В этом случае я рекомендую следующий алгоритм:

  1. Выберите один номер из диапазона
  2. Выберите один номер из оставшегося диапазона
  3. и т. д.

Реализация может выглядеть так:

  1. Выберите число от 0 до N
  2. Выберите число от 0 до N-1
  3. И так далее
  4. Определите, какой номер каждого из ваших рисунков представляет

Пример для 0-10

  1. draw 4
  2. draw 7
  3. ...
  4. Результаты: 4 представляет 4, 7 представляет 8, так как теперь это седьмой доступный номер.
ответил Dennis Jaheruddin 28 PM00000060000005531 2014, 18:09:55
5

По внешнему виду, то, что вы хотите, называется (псевдо) случайной перестановкой все значения int. Обратите внимание, что вам необязательно хранить эти значения в массиве и перетасовывать их, потребляя память; вы можете генерировать их по требованию через «идеальную» хэш-функцию битов в «count ".

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

ответил Alan King 29 PM00000070000001931 2014, 19:33:19
4

У вас есть два параметра: число N целых чисел, которое вы хотите, и их максимальный размер M> = N. Если N близко к M, например, вы хотите, чтобы 500 номеров находились в диапазоне 1..1000, тогда ваши лучшие ставка заключается в (частично) перетасовке чисел 1..M. Например, вы можете запустить первые N шагов в Shuffle Fisher-Yates на 1..M и получить нужные вам номера.

В противном случае, если M намного больше, чем N, вам лучше будет генерировать все ваши случайные числа одновременно (а не проверять, находятся ли они в списке один за другим), сортировка, удаление дубликатов, добавление новые элементы, необходимые для замены, а затем перетасовывание.

Вы можете создать более N номеров для обработки ожидаемого количества дубликатов. Ожидаемое количество дубликатов равно N (N-1) /2M, поэтому вы можете генерировать, скажем, N + 1.1N (N-1) /2M номера в вашем первоначальном списке.

Сортировка и удаление дубликатов является стандартным.

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

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

Если производительность важна, вы можете закодировать оба метода (и, возможно, несколько вариантов второго, как описано) и тест, чтобы найти обрезание между методами. Если это не так, второй метод будет работать во всех случаях - хотя, если он вам не нужен, первый проще программировать.

ответил Charles 29 AM000000120000002631 2014, 00:21:26
4

Прежде всего, существует одна неопределенная переменная random, и лучше всего предположить, что она System.Random и Следующий метод возвращает

  

32-разрядное целое число со знаком, большее или равное нулю и меньшее, чем    MaxValue .

Я прошу автора сделать это ясно в вопросе . В этом предположении мы имеем алгоритм, который работает для count < int.MaxValue, но получает очень медленно для count рядом с этим значением, но это будет означать, что вы едите почти 8 ГБ памяти (2G * 4B). Мы можем попытаться сделать это быстрее для count больше некоторого порога, например. 20 (с учетом бенчмаркинга), исключение для какого-то смешного подсчета и переписать его следующим образом:

public static List<int> GetRandomNumbers(int count) {
    if(count > int.MaxValue/8)
        throw new MyException("count too big");

    List<int> randomNumbers = new List<int>(count); 
    if(count < 20) for (int i=0; i<count; i++) {
        int number; do number = random.Next(); // I will address the 'uglyness' later
        while (randomNumbers.Contains(number));
        randomNumbers.Add(number);
    } else {
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number; do number = random.Next();
            while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}

do..while может показаться уродливым, но разделяется двумя пустыми строками (в исходном коде), что делает его достаточным, но все еще подлежит дальнейшему переосмыслению относительно того, кто может поддерживать код , Я не буду говорить об этом, потому что это зависит от того, сколько людей может поддерживать настройки кода и программиста (я не буду рассматривать стиль кода, пока вижу его). Я не настолько строг в этом и для меня, две пустые строки (один до и один после) достаточно, чтобы сигнализировать, что нужно больше думать, когда сталкиваешься, и я никогда не коснусь кода, который работает и является оптимальным. Комментарии могут помочь описать намерение, код должен быть просмотрен, когда что-то не так (не работает или работает медленно). Следующее может выглядеть лучше, используя {}, больше конец строки и несколько комментариев:

public static List<int> GetRandomNumbers(int count) {
//  eating too much memory is not desired
    if(count > int.MaxValue/8)
        throw new MyException("count too big");

    List<int> randomNumbers = new List<int>(count);
    if(count < 20) {
    //  list is fast enough for small count
        for (int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (randomNumbers.Contains(number));
            randomNumbers.Add(number);
        }
    } else {
    //  but HashSet is faster for longer sequence
        HashSet<int> included = new HashSet<int>();
        for(int i=0; i<count; i++) {
            int number;
            do {
                number = random.Next();
            } while (!included.Add(number));
            randomNumbers.Add(number);
        }
    }
    return randomNumbers;
}
ответил firda 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSun, 07 Sep 2014 00:13:39 +0400 2014, 00:13:39
4

Я дам короткий ответ.

Так как ваши случайные числа - это 32-битные целые числа, вероятность столкновения очень низкая. В этом случае цикл do ... while будет цикл только изредка и не вызовет каких-либо проблем с производительностью.

Проблема заключается в том, как вы проверяете наличие столкновения. Проверка того, принадлежит ли номер к списку, требует последовательного чтения списка. Это медленно. Вам лучше использовать HashMap. Вставьте каждое сгенерированное число в HashMap и проверьте новые числа на HashMap.

Поскольку вы хотите вернуть числа в виде списка, вам также нужно будет собрать номера в списке. Вы можете либо скомпилировать список по мере создания чисел, либо создать список позже, из HashMap. Но второе решение ставит под угрозу случайность, и вам придется снова перетасовать цифры. И чтобы фактически сохранить память, вы должны очистить HashMap при создании списка. Опорожнение HashMap по одному элементу за раз добавляет служебные данные.

Альтернативное решение

Полное решение, минимизирующее использование памяти, должно генерировать N случайных чисел в диапазоне от 0 до Int32.MaxValue-N + 1, сортировать список, добавлять i-й элемент и снова перетасовывать список. Это минимизирует использование памяти, но время O (N log N).

Решение List + HashMap - это почти время работы O (N), но требует как минимум вдвое больше памяти.

ответил Florian F 5 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowFri, 05 Sep 2014 00:26:19 +0400 2014, 00:26:19
3

Если есть 1-4 возможных номера, и вы уже произвели 1 номер, это означает, что осталось (4 - 1) 3 возможных числа. Сделайте случайное число между 3, для каждого порождающего числа оно больше или равно, увеличивайте созданный номер на 1.

позволяет сказать, что число равно 2, и вы хотите создать другое:

Сгенерированные числа: [1,2,3] Возможное число: [1,3,4]

Решение:

public static int[] GetRandomNumbers(int count, int minValue, int maxValue)
{
    int[] randomNumbers = new int[count]; 

    for (int i=0; i < count; ++i) 
    {      
        //Given (min - max) is the range, there can only be (range - i) unique number left
        int number = random.Next(minValue, maxValue - i);

        //if the number is greater than or equal to, then increase the number
        for (int j=0; j < i; ++j)
            if(number >= randomNumbers[j])
                ++number; 

        randomNumbers.Add(number);
    }

    return randomNumbers;
}
ответил Kris 29 AM000000100000003131 2014, 10:50:31
3

Вместо использования do-while мы не можем делать это поочередно с меньшим количеством строк кода, используя Linq?

Заполните список цифрами от 1 до 100 (или любым лимитом) и перетасуйте список.

Вам нужно добавить с помощью пространства имен System.Linq. Он должен присутствовать по умолчанию.

static void PrintRandom(int limit)
{

        List<int> original = Enumerable.Range(1, limit).ToList();
        Random rand = new Random ();

        //shuffle the list

        List <int> sorted = original.OrderBy(item => rand.Next()).ToList ();
        foreach (int i in sorted)
        {
            Console.WriteLine(i);   
        }
        Console.ReadKey();
}
ответил BSG 30 Jam1000000amFri, 30 Jan 2015 08:27:17 +030015 2015, 08:27:17
1

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

    public static IEnumerable<int> GetRandomNumbers(int count, int minValue, int maxValue)
    {
        if (count < 1)
        {
            throw new ArgumentException("Count must be greater then 0", "count");
        }

        if (count > Math.Abs(maxValue - minValue))
        {
            throw new ArgumentException("MaxValue must be greater than count", "maxValue");
        }

        var segmentSize = (maxValue - minValue) / count;
        var random = new Random();
        var steps = Enumerable.Range(0, count).ToList();

        while (steps.Count != 0)
        {
            var currentIndex = random.Next(0, steps.Count);
            var index = steps[currentIndex];
            steps.RemoveAt(currentIndex);

            yield return random.Next((index * segmentSize) + minValue, ((index + 1) * segmentSize) + minValue);
        }
    }

    public static IEnumerable<int> GetRandomNumbers(int count)
    {
        return GetRandomNumbers(count, 0, int.MaxValue);
    }
ответил Peter Kiss 7 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowSun, 07 Sep 2014 11:05:59 +0400 2014, 11:05:59
0

List содержит is \ $ O (n) \ $. HashSet содержит is \ $ O (1) \ $.

private static Random rand = new Random();
public static IEnumerable<int> GetRandomNumbers(int count)
{
    HashSet<int> randomNumbers = new HashSet<int>();
    while(randomNumbers.Count < count)
    {
        int r = rand.Next();
        if (randomNumbers.Add(r))
            yield return r;
    }
}
ответил paparazzo 24 J000000Monday17 2017, 06:41:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132