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

Question

У меня есть ситуация, когда мне нужно создать десятки тысяч уникальных чисел. Однако эти числа должны состоять из 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

Answer 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 для 1000000.И это даже без какого-либо параллелизма.Из-за использования HashSet<T> вместо List<T> этот алгоритм работает в O (n), то есть продолжительность будет расти линейно.Поэтому 1000000 значений занимают около 7 секунд.

Answer 2

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

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

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 действительных уникальных номеров.

Answer 3

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

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

Answer 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.

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

Я проверил его на своей машине, и генерация уникальных значений 400 КБ заняла ~ 1 секунду.

Answer 5

Мейбе, это будет быстрее:

        //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();

Answer 6

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

Answer 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);
            }
        }
    }

Answer 8

Как то так?

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;
        }

Answer 9

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

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

Answer 10

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

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