Создание случайной, не повторяющейся последовательности всех целых чисел в .NET.

Ответ 1

Есть ли способ в .NET

Собственно, это можно сделать на большинстве языков

чтобы сгенерировать последовательность всех 32-битных целых чисел (Int32)

Да.

в случайном порядке,

Здесь нам нужно договориться о терминологии, так как "случайный" - это не то, что большинство людей считают. Подробнее об этом через мгновение.

без повторений,

Да.

и эффективно с точки зрения памяти?

Да.

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

Хорошо, так будет ли использование почти без памяти приемлемым?; -)

Прежде чем перейти к предложению, нам нужно прояснить вопрос о "случайности". Что-то действительно случайное не имеет заметной картины. Следовательно, запуск алгоритма миллионы раз подряд может теоретически возвращать одинаковое значение во всех итерациях. Если вы входите в понятие "должно быть отличным от предшествующей итерации", то оно уже не является случайным. Однако, глядя на все требования вместе, кажется, что все, что действительно просят, это "разные шаблоны распределения целых чисел". И это выполнимо.

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

Генерировать различное случайное время в данном интервале

Впервые я узнал об этом понятии (генерировать, по-видимому, случайный уникальный числовой идентификатор в SQL Server), и вы можете использовать любой из следующих онлайн-калькуляторов, чтобы определить свой "Целое число" и "Модульные мультипликативные инверсии (MMI)":

• http://planetcalc.com/3311/
• http://www.cs.princeton.edu/~dsri/modular-inversion-answer.php

Применяя эту концепцию здесь, вы должны использовать Int32.MaxSize как значение Modulo.

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

Единственная начальная проблема заключается в том, что шаблон распределения всегда совпадает с тем же значением "Целое" и "MMI". Таким образом, вы можете придумать разные шаблоны путем добавления "случайного" генерируемого Int к стартовому значению (как я полагаю, я сделал в своем ответе о создании выборочных данных в SQL Server), или вы можете предварительно создать несколько комбинаций "Integer" и соответствующие значения "MMI", сохраните их в файле конфигурации/словаре и используйте случайную функцию .NET, чтобы выбрать один в начале каждого прогона. Даже если вы сохраняете 100 комбинаций, это почти не используется памятью (предполагается, что это не файл конфигурации). Фактически, если хранить как Int, так и словарь использует Int в качестве индекса, то 1000 значений составляют приблизительно 12k?

UPDATE

Примечания:

• В результатах есть образец, но он не заметен, если у вас их недостаточно в любой момент, чтобы посмотреть в целом. Для большинства случаев использования это приемлемо, поскольку ни один получатель значений не будет иметь большой набор из них или не знает, что они были назначены последовательно без каких-либо пробелов (и для этого требуется знание, чтобы определить, существует ли шаблон).
• В формуле для конкретного прогона требуется только одно из двух значений переменных - "Целое число" и "Модульный мультипликативный обратный (MMI)". Следовательно:
  • каждая пара дает две различные последовательности
  • При сохранении набора в памяти требуется только простой массив и предполагается, что индекс массива является просто смещением в памяти от базового адреса массива, тогда требуемая память должна быть только 4 байта * емкости (т.е. 1024 - только 4k, верно?)

Вот несколько тестовых кодов. Он написан в T-SQL для Microsoft SQL Server, так как именно там я работаю в первую очередь, и у него также есть преимущество, благодаря чему он действительно легко тестируется на уникальность, минимальные и максимальные значения и т.д., Без необходимости компилировать что-либо. Синтаксис будет работать в SQL Server 2008 или новее. Для SQL Server 2005 инициализация переменных еще не была введена, поэтому каждый DECLARE, содержащий =, просто должен быть разделен на DECLARE сам по себе и SET @Variable = ..., но эта переменная инициализируется. И SET @Index += 1; должен стать SET @Index = @Index + 1;.

Код ошибки будет ошибочным, если вы укажете значения, которые производят любые дубликаты. И последний запрос указывает, есть ли пробелы, поскольку можно сделать вывод, что если совокупность переменных таблицы не была ошибкой (следовательно, нет дубликатов), а общее число значений - ожидаемое число, тогда могут быть только пробелы (т.е. Отсутствует значения) Если оба или оба фактических значения MIN и MAX находятся за пределами ожидаемых значений.

ОБРАТИТЕ ВНИМАНИЕ, что этот тестовый код не означает, что любое из значений предварительно сгенерировано или необходимо сохранить. Код сохраняет только значения, чтобы проверить уникальность и минимальные/максимальные значения. На практике все, что необходимо, это простая формула, и все, что необходимо для ее прохождения, это:

• емкость (хотя в этом случае она также может быть жестко закодирована)
• значение MMI/Integer
• текущий "индекс"

Таким образом, вам нужно сохранить только 2 - 3 простых значения.

DECLARE @TotalCapacity INT = 30; -- Modulo; -5 to +4 = 10 OR Int32.MinValue
                                 -- to Int32.MaxValue = (UInt32.MaxValue + 1)
DECLARE @MMI INT = 7; -- Modular Multiplicative Inverse (MMI) or
                      -- Integer (derived from @TotalCapacity)

DECLARE @Offset INT = 0; -- needs to stay at 0 if min and max values are hard-set
-----------
DECLARE @Index INT = (1 + @Offset); -- start

DECLARE @EnsureUnique TABLE ([OrderNum] INT NOT NULL IDENTITY(1, 1),
                             [Value] INT NOT NULL UNIQUE);
SET NOCOUNT ON;

BEGIN TRY
    WHILE (@Index < (@TotalCapacity + 1 + @Offset)) -- range + 1
    BEGIN
        INSERT INTO @EnsureUnique ([Value]) VALUES (
                 ((@Index * @MMI) % @TotalCapacity) - (@TotalCapacity / 2) + @Offset
                                                   );
        SET @Index += 1;
    END;
END TRY
BEGIN CATCH
    DECLARE @Error NVARCHAR(4000) = ERROR_MESSAGE();
    RAISERROR(@Error, 16, 1);
    RETURN;
END CATCH;

SELECT * FROM @EnsureUnique ORDER BY [OrderNum] ASC;
SELECT COUNT(*) AS [TotalValues],
       @TotalCapacity AS [ExpectedCapacity],
       MIN([Value]) AS [MinValue],
       (@TotalCapacity / -2) AS [ExpectedMinValue],
       MAX([Value]) AS [MaxValue],
       (@TotalCapacity / 2) - 1 AS [ExpectedMaxValue]
FROM   @EnsureUnique;

Ответ 2

Если вам не нужны криптографически безопасные случайные числа, вы можете использовать Linear Congruential Generator.

LCG - это формула вида X_n + 1 = X_n * a + c (mod m), для каждой порожденной цифры требуется постоянная память и постоянное время. Если выбраны правильные значения для LCG, он будет иметь полную длину периода, то есть он будет выводить каждое число между 0 и выбранным модулем.

LCG имеет полный период тогда и только тогда, когда:

• Модуль и приращение взаимно просты, т.е. GCD(m, c) = 1
• a - 1 делится на все простые множители m
• Если m делится на 4, a - 1 должно делиться на 4.

Наш модуль равен 2 ^ 32, то есть a должен быть числом формы 4k + 1, где k - произвольное целое число, а c не должно делиться на 2.

В то время как это вопрос С#, я закодировал небольшую программу на С++, чтобы проверить скорость этого решения, так как мне удобнее на этом языке:

#include <iostream>
#include <stdlib.h>

class lcg {
private:
    unsigned a, c, val;
public:
    lcg(unsigned seed=0) : lcg(seed, rand() * 4 + 1, rand() * 2 + 1) {}
    lcg(unsigned seed, unsigned a, unsigned c) {
        val = seed;
        this->a = a;
        this->c = c;
        std::cout << "Initiated LCG with seed " << seed << "; a = " << a << "; c = " << c << std::endl;
    }

    unsigned next() {
        this->val = a * this->val + c;
        return this->val;
    }
};

int main() {
    srand(time(NULL));
    unsigned seed = rand();
    int dummy = 0;
    lcg gen(seed);
    time_t t = time(NULL);
    for (uint64_t i = 0; i < 0x100000000ULL; i++) {
        if (gen.next() < 1000) dummy++; // Avoid optimizing this out with -O2
    }
    std::cout << "Finished cycling through. Took " << (time(NULL) - t) << " seconds." << std::endl;
    if (dummy > 0) return 0;
    return 1;
}

Вы можете заметить, что я не использую операцию модуля в любом месте класса lcg, потому что мы используем 32-битное целочисленное переполнение для нашей работы модуля.
Это дает все значения в диапазоне [0, 4294967295] включительно.
Мне также пришлось добавить фиктивную переменную для компилятора, чтобы не оптимизировать все.
Без оптимизации это решение заканчивается примерно через 15 секунд, а при -O2 умеренная оптимизация заканчивается менее чем на 5 секунд.

Если "истинная" случайность не является проблемой, это очень быстрое решение.

Ответ 3

32-битный PRP в режиме CTR кажется единственным жизнеспособным подходом ко мне (ваш 4-й вариант).

Вы можете либо

• Используйте выделенный 32-разрядный блочный шифр.

  Skip32, 32-битный вариант Skipjack - популярный выбор.

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

• Шифрование с сохранением длины (частный случай шифрования с сохранением формата)

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

Обратите внимание, что многие из этих конструкций имеют значительный недостаток: они даже перестановки. Это означает, что после того, как вы увидели 2 ^ 32-2 выхода, вы сможете прогнозировать второй-последний вывод с уверенностью, а не только на 50%. Я думаю, что в документе AEZ Rogaways упоминается способ устранения этого недостатка.

Ответ 4

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

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

Ниже приведена основная схема алгоритма, который я предлагаю сгенерировать эти числа. Все 32-разрядные целые числа могут быть сохранены в ~ 16 ГБ дискового пространства (32 бит = 4 байта, 4 байта/целое число 2 2) 32 целых числа = 2 ^ 34 байта = 16 гигабайт, а также любые накладные расходы, требуемые операционной системой/файловой системой) и я взял "несколько сотен мегабайт", чтобы означать, что вы хотите читать в файле размером не более 256 мегабайт за раз.

• Генерировать 16 GiB/256 MiB = 64 текстовых файлов ASCII с 256 символами "нулевого" символа MiB (все биты равны 0). Назовите каждый текстовый файл "0.txt" через "64.txt"
• Петля последовательно от Int32.MinValue до Int32.MaxValue, пропуская 0. Это значение целого, которое вы в настоящее время сохраняете.
• На каждой итерации генерируйте случайное целое число от 0 до UInt32.MaxValue из источника случайности по вашему выбору (аппаратный истинный случайный генератор, псевдослучайный алгоритм, что угодно). Это индекс значения, которое вы в настоящее время сохраняете.
• Разделите индекс на два целых числа: 6 наиболее значимых бит и остальные 26. Используйте верхние биты для загрузки соответствующего текстового файла.
• Умножьте младшие 26 бит на 4 и используйте это как индекс в открывшемся файле. Если четыре байта, следующие за этим индексом, все еще являются "нулевым" символом, закодируйте текущее значение на четыре символа ASCII и сохраните эти символы в этой позиции. Если они не все "нулевой" символ, вернитесь к шагу 3.
• Повторяйте, пока не будут сохранены все целые числа.

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

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

(* Я понимаю, что случайность любого источника уменьшается, накладывая ограничение "единственности", но этот подход должен приводить к относительно близким по случайности числам к исходному источнику)

TL; DR - Перемешивание целых чисел заблаговременно, сохранение всех их на диске в нескольких меньших файлах, затем чтение из файлов по мере необходимости во время выполнения.

Ответ 5

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

Однако при вычислении шаблон просто должен быть не "заметным". Обычно система вычисляет случайное число, выполняя операции умножения с огромными предопределенными значениями и значениями таймера таким образом, что они переполняются и, таким образом, отображаются случайным образом. Так что либо вы используете свой третий вариант, либо вам нужно подумать о генерации этих псевдослучайных чисел таким образом, чтобы вы могли воспроизвести последовательность каждого сгенерированного числа и проверить, нет ли каких-либо повторений. Это, очевидно, было бы чрезвычайно вычислительно дорого, но вы попросили об эффективности памяти.

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

Так что-то вроде этого:

int seed = 123;
Int64 counter = 0;
Random rnd = new Random(seed);

int GetUniqueRandom()
{
    int newNumber = rnd.Next();
    Random rndCheck = new Random(seed);

    counter++;

    for (int j = 0; j < counter; j++)
    {
        int checkNumber = rndCheck.Next();

        if (checkNumber == newNumber)
            return GetUniqueRandom();
    }

    return newNumber;        
}

ОБНОВЛЕНИЕ: Было отмечено, что counter достигнет огромного значения, и нет никаких сведений о том, переполнится ли оно, прежде чем вы получите все 4 миллиарда значений или нет.

Ответ 6

Хорошая головоломка. Приходят в голову несколько вещей:

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

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

static ulong xorshift64star(ulong x)
{
    x ^= x >> 12; // a
    x ^= x << 25; // b
    x ^= x >> 27; // c

    return x * 2685821657736338717ul;
}

static void Main(string[] args)
{
    byte[] buf = new byte[512 * 1024 * 1024];
    Random rnd = new Random();

    ulong value = (uint)rnd.Next(int.MinValue, int.MaxValue);
    long collisions = 0;

    Stopwatch sw = Stopwatch.StartNew();

    for (long i = 0; i < uint.MaxValue; ++i)
    {
        if ((i % 1000000) == 0)
        {
            Console.WriteLine("{0} random in {1:0.00}s (c={2})", i, sw.Elapsed.TotalSeconds, collisions - 1000000);
            collisions = 0;
        }

        uint randomValue; // result will be stored here
        bool collision;

        do
        {
            value = xorshift64star(value);
            randomValue = (uint)value;

            collision = (buf[randomValue >> 4] & (1 << (int)(randomValue & 7))) != 0;
            ++collisions;
        }
        while (collision);

        buf[randomValue >> 4] |= (byte)(1 << (int)(randomValue & 7));
    }

    Console.ReadLine();
}

После примерно 1,9 миллиарда случайных чисел алгоритм начнет останавливаться.

1953000000 случайным образом в 283,74 с (с = 10005932) [...] 2108000000 случайным образом в 430,66 с (c = 52837678)

Итак, пусть аргумент говорит, что вы собираетесь использовать этот алгоритм для первых чисел +/- 2 миллиарда.

Далее вам нужно решение для остальных, что в основном является проблемой, описанной OP. Для этого я бы случайных чисел в буфер и объединить буфер с алгоритмом Knuth shuffle. Вы также можете использовать это право с самого начала, если хотите.

Это то, что я придумал (возможно, все еще глючит, поэтому сделайте тест...):

static void Main(string[] args)
{
    Random rnd = new Random();

    byte[] bloom = new byte[512 * 1024 * 1024];
    uint[] randomBuffer = new uint[1024 * 1024];

    ulong value = (uint)rnd.Next(int.MinValue, int.MaxValue);
    long collisions = 0;

    Stopwatch sw = Stopwatch.StartNew();
    int n = 0;

    for (long i = 0; i < uint.MaxValue; i += n)
    {
        // Rebuild the buffer. We know that we have uint.MaxValue-i entries left and that we have a 
        // buffer of 1M size. Let calculate the chance that you want any available number in your 
        // buffer, which is now:

        double total = uint.MaxValue - i;
        double prob = ((double)randomBuffer.Length) / total;

        if (i >= uint.MaxValue - randomBuffer.Length)
        {
            prob = 1; // always a match.
        }

        uint threshold = (uint)(prob * uint.MaxValue);
        n = 0;

        for (long j = 0; j < uint.MaxValue && n < randomBuffer.Length; ++j)
        {
            // is it available? Let shift so we get '0' (unavailable) or '1' (available)
            int available = 1 ^ ((bloom[j >> 4] >> (int)(j & 7)) & 1);

            // use the xorshift algorithm to generate a random value:
            value = xorshift64star(value);

            // roll a die for this number. If we match the probability check, add it.
            if (((uint)value) <= threshold * available)
            {
                // Store this in the buffer
                randomBuffer[n++] = (uint)j;

                // Ensure we don't encounter this thing again in the future
                bloom[j >> 4] |= (byte)(1 << (int)(j & 7));
            }
        }

        // Our buffer now has N random values, ready to be emitted. However, it 
        // still sorted, which is something we don't want. 
        for (int j = 0; j < n; ++j)
        {
            // Grab index to swap. We can do this with Xorshift, but I didn't bother.
            int index = rnd.Next(j, n);

            // Swap
            var tmp = randomBuffer[j];
            randomBuffer[j] = randomBuffer[index];
            randomBuffer[index] = tmp;
        }

        for (int j = 0; j < n; ++j)
        {
            uint randomNumber = randomBuffer[j];
            // Do something with random number buffer[i]
        }

        Console.WriteLine("{0} random in {1:0.00}s", i, sw.Elapsed.TotalSeconds);
    }

    Console.ReadLine();
}

Назад к требованиям:

Есть ли способ в .NET генерировать последовательность всех 32-разрядных целых чисел (Int32) в случайном порядке без повторений и с эффективностью памяти? Эффективность памяти будет означать использование не более нескольких сотен мегабайт основной памяти.

Стоимость: 512 МБ + 4 МБ. Повторения: нет.

Это довольно быстро. Это просто не "равномерно" быстро. Каждые 1 миллион номеров, вам нужно пересчитать буфер.

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

Ответ 7

Одним из самых простых решений является использование алгоритма блочного шифрования, такого как AES в контрмоде. Вам нужно семя, которое равно ключу в AES. Затем вам понадобится счетчик, который увеличивается для каждого нового случайного значения. Случайное значение является результатом шифрования счетчика с помощью ключа. Поскольку открытый текст (счетчик) и случайное число (зашифрованный текст) являются биективными, а из-за принципа голубинной дыры случайные числа уникальны (для блока).

Эффективность памяти: вам нужно хранить семя и счетчик.

Единственное ограничение состоит в том, что AES имеет размер блока 128 бит вместо 32 бит. Таким образом, вам может потребоваться увеличить до 128 бит или найти блочный шифр с 32-разрядным размером блока.

Для вашего IEnumerable вы можете написать обертку. Индекс - это счетчик.

Отказ от ответственности: вы просите не повторяться/уникально: это дисквалифицируется от случайного, потому что обычно вы должны видеть столкновения в случайных числах. Поэтому вы не должны использовать его для длительной последовательности. См. Также https://crypto.stackexchange.com/questions/25759/how-can-a-block-cipher-in-counter-mode-be-a-reasonable-prng-when-its-a-prp

Ответ 8

Вы можете попробовать этот блочный шифр доморощенного:

public static uint Random(uint[] seed, uint m)
{   
    for(int i = 0; i < seed.Length; i++)
    {
        m *= 0x6a09e667;
        m ^= seed[i];
        m += m << 16;
        m ^= m >> 16;
    }
    return m;
}

Тестовый код:

const int seedSize = 3; // larger values result in higher quality but are slower
var seed = new uint[seedSize];
var seedBytes = new byte[4 * seed.Length];
new RNGCryptoServiceProvider().GetBytes(seedBytes);
Buffer.BlockCopy(seedBytes, 0, seed, 0, seedBytes.Length);  

for(uint i = 0; i < uint.MaxValue; i++)
{
    Random(seed, i);
}

Я еще не проверял качество своих выходов. Работает через 19 секунд на моем компьютере для seedSize = 3.