Проблема производительности с генерацией случайных уникальных номеров

У меня есть ситуация, когда мне нужно создавать десятки тысяч уникальных чисел. Однако эти цифры должны быть 9 цифр и не могут содержать никаких 0. Мой текущий подход состоит в том, чтобы сгенерировать 9 цифр (1-9) и объединить их вместе, и если номер еще не внесён в список, добавив его в него. Например.

public void generateIdentifiers(int quantity)
{
    uniqueIdentifiers = new List<string>(quantity);
    while (this.uniqueIdentifiers.Count < quantity)
    {
        string id = string.Empty;
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += " ";
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += " ";
        id += random.Next(1,10);
        id += random.Next(1,10);
        id += random.Next(1,10);
        if (!this.uniqueIdentifiers.Contains(id))
        {
            this.uniqueIdentifiers.Add(id);
        }
    }
}

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

Изменить: - Я генерирую их - http://www.nhs.uk/NHSEngland/thenhs/records/Pages/thenhsnumber.aspx

Ответ 1

Как упоминалось выше, используйте HashSet<T> вместо List<T>.
Более того, использование StringBuilder вместо простых операций с цепочкой приведет к еще 25%. Если вы можете использовать числа вместо строк, вы выигрываете, потому что это занимает только третью или четвертую часть времени.

var quantity = 400000;
var uniqueIdentifiers = new HashSet<int>();
while (uniqueIdentifiers.Count < quantity)
{
    int i=0;
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    i = i*10 + random.Next(1,10);
    uniqueIdentifiers.Add(i);
}

Для моей машины требуется около 270 мс для 400 000 номеров и около 700 для 1 000 000. И это даже без каких-либо parallelism. Из-за использования HashSet<T> вместо List<T> этот алгоритм работает в O (n), т.е. Продолжительность будет линейной. Поэтому 10 000 000 значений занимают около 7 секунд.

Ответ 2

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

Я бы сгенерировал сто тысяч чисел - не должен занимать очень много времени, может быть, несколько секунд? Затем используйте Parallel LINQ, чтобы сделать Distinct() для устранения дубликатов. Затем используйте другой запрос PLINQ для запуска регулярного выражения против остатка, чтобы устранить любые с нулями в них. Затем возьмите верхнюю x тысячу. (PLINQ блестящий для копирования таких больших задач). Если необходимо, промойте и повторите, пока у вас не будет достаточно для ваших нужд.

На достойной машине это займет у вас больше времени, чтобы написать эту простую функцию, чем потребуется для ее запуска. Я бы также спросил, почему у вас есть 400K записей, чтобы проверить, когда вы заявляете, что вам действительно нужны "десятки тысяч"?

Ответ 3

Фокус в том, что вам нужно всего десять тысяч уникальных номеров. Теоретически вы могли бы иметь почти 9,0E + 08 возможностей, но зачем заботиться, если вам нужно так много меньше?

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

long[] numbers = { 1, 3, 5, 7 }; //note that we just take a few numbers, enough to create the number of combinations we might need
var list = (from i0 in numbers
            from i1 in numbers
            from i2 in numbers
            from i3 in numbers
            from i4 in numbers
            from i5 in numbers
            from i6 in numbers
            from i7 in numbers
            from i8 in numbers
            from i9 in numbers
            select i0 + i1 * 10 + i2 * 100 + i3 * 1000 + i4 * 10000 + i5 * 100000 + i6 * 1000000 + i7 * 10000000 + i8 * 100000000 + i9 * 1000000000).ToList();

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

Ответ 4

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

static char[] base9 = "123456789".ToCharArray();

static string ConvertToBase9(int value) {
    int num = 9;
    char[] result = new char[9];
    for (int i = 8; i >= 0; --i) { 
        result[i] = base9[value % num];
        value = value / num;
    }
    return new string(result);
}

public static void generateIdentifiers(int quantity) {
    var uniqueIdentifiers = new List<string>(quantity);
    // we have 387420489 (9^9) possible numbers of 9 digits in base 9.
    // if we choose a number that is prime to that we can easily get always
    // unique numbers
    Random random = new Random();
    int inc = 386000000;
    int seed = random.Next(0, 387420489);
    while (uniqueIdentifiers.Count < quantity) {
        uniqueIdentifiers.Add(ConvertToBase9(seed));
        seed += inc;
        seed %= 387420489;
    }
}

Я попытаюсь объяснить идею с небольшими номерами...

Предположим, что у вас есть не более 7 возможных комбинаций. Выберем число, которое является простым с 7, например. 3 и случайным стартовым номером, например. 4.

В каждом раунде мы добавляем 3 к нашему текущему числу, а затем берем результат по модулю 7, поэтому получаем следующую последовательность:

4 → 4 + 3% 7 = 0
0 → 0 + 3% 7 = 3
3 → 3 + 3% 7 = 6
6 → 6 + 6% 7 = 5

Таким образом, мы произвольно генерируем все значения от 0 до 6. В моем примере мы делаем то же самое, но у нас есть 9 ^ 9 возможных комбинаций, а в качестве числа, простого с тем, что я выбираю 386000000 (вам просто нужно избегать кратных 3).

Затем я подбираю число в последовательности и преобразую его в базу 9.

Надеюсь, это ясно:)

Я тестировал его на своей машине и генерировал уникальные значения 400k, заняв ~ 1 секунду.

Ответ 5

Глядя на уже опубликованные решения, мой кажется довольно простым. Но он работает и генерирует 1 миллион значений в приблизительном 1 с (10 миллионов в 11 секунд).

public static void generateIdentifiers(int quantity)
{
    HashSet<int> uniqueIdentifiers = new HashSet<int>();

    while (uniqueIdentifiers.Count < quantity)
    {
        int value = random.Next(111111111, 999999999);
        if (!value.ToString().Contains('0') && !uniqueIdentifiers.Contains(value))
            uniqueIdentifiers.Add(value);
    }
}

Ответ 6

Meybe это будет быстрее:

        //we can generate first number wich in 9 base system will be between 88888888 - 888888888 
        //we can't start from zero becouse it will couse the great amount of 1 digit at begining

        int randNumber = random.Next((int)Math.Pow(9, 8) - 1, (int)Math.Pow(9, 9));


        //no we change our number to 9 base, but we add 1 to each digit in our number
        StringBuilder builder = new StringBuilder();

        for (int i=(int)Math.Pow(9,8); i>0;i= i/9)
        {
            builder.Append(randNumber / i +1);
            randNumber = randNumber % i;
        }

        id = builder.ToString();

Ответ 7

использовать строковый массив или stringbuilder, wjile работает со строковыми дополнениями.

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

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

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

    public static Random RANDOM = new Random();
    public static List<int> randomNumbers = new List<int>();
    public static List<string> randomStrings = new List<string>();

    private void fillRandomNumbers()
    {
        int i = 100;
        while (i < 1000)
        {
            if (i.ToString().Contains('0') == false)
            {
                randomNumbers.Add(i);
            }
        }
    }

Ответ 8

Я думаю, что первым делом было бы использовать StringBuilder, а не конкатенацию - вы будете приятно удивлены. Antoher - используйте более эффективную структуру данных, например HashSet < > или HashTable.

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

Ответ 9

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

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

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

Ответ 10

Что-то вроде этого?

public List<string> generateIdentifiers2(int quantity)
        {
            var uniqueIdentifiers = new List<string>(quantity);
            while (uniqueIdentifiers.Count < quantity)
            {
                var sb = new StringBuilder();
                sb.Append(random.Next(11, 100));
                sb.Append(" ");
                sb.Append(random.Next(11, 100));
                sb.Append(" ");
                sb.Append(random.Next(11, 100));

                var id = sb.ToString();
                id = new string(id.ToList().ConvertAll(x => x == '0' ? char.Parse(random.Next(1, 10).ToString()) : x).ToArray());

                if (!uniqueIdentifiers.Contains(id))
                {
                    uniqueIdentifiers.Add(id);
                }
            }
            return uniqueIdentifiers;
        }