C ++ Как сгенерировать 10000 уникальных случайных целых чисел для хранения в BST? - PullRequest
Новая
       58

C ++ Как сгенерировать 10000 уникальных случайных целых чисел для хранения в BST?

1 голос
/ 24 марта 2019

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

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

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random) i--;
        }
    }

Ответы [ 3 ]

1 голос
/ 24 марта 2019

В вашем коде есть пара проблем. Но давайте прямо к больно.

В чем главная проблема?

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

Итак, где-то в вашем коде вы должны иметь: 

tree1Ptr = new Node;   // or whatever the type of your node is called

Однако в вашем внутреннем цикле вы просто используете его, как если бы это был массив: 

for (int i = 0; i < 10000; i++) 
{
    int random = rand() % 20000;
    tree1Ptr->add(random);
    for (int j = 0; j < i; j++) {
        if (tree1Ptr[j]==random)  //<============ OUCH !!
            i--;
    }
}

Компилятор не будет жаловаться, потому что это правильный синтаксис: вы можете использовать индексирование массива по указателю. Но вам нужно убедиться, что вы не выходите за пределы (так что здесь, j остается <1). </p>

Другие замечания

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

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

Как это решить?

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

0 голосов
/ 25 марта 2019

Есть два способа, которыми вы можете выбрать случайные уникальные числа из последовательности без проверки по ранее выбранным номерам (т. Е. Уже в вашем BST).

Использовать random_shuffle

Простой способ - перетасовать отсортированный массив из 1 ... 20 000 и просто выбрать первые 10000 элементов: 

#include <algorithm>
#include <vector>

std::vector<int> values(20000);
for (int i = 0; i < 20000; ++i) {
  values[i] = i+1;
}
std::random_shuffle(values.begin(), values.end());

for (int i = 0; i < 10000; ++i) {
  // Insert values[i] into your BST
}

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

Использоватьiform_int_distribution

Если размер выбираемых случайных чисел намного меньше размера общих чисел, то можно использовать альтернативный способ: 

#include <chrono>
#include <random>
#include <vector>

// Use timed seed so every run produces different random picks.
std::default_random_engine reng(
    std::chrono::steady_clock::now().time_since_epoch().count());

int num_pick  = 1000;   // # of random numbers remained to pick
int num_total = 20000;  // Total # of numbers to pick from

int cur_value = 1;  // Current prospective number to be picked
while (num_pick > 0) {
  // Probability to pick `cur_value` is num_pick / (num_total-cur_value+1)
  std::uniform_int_distribution<int> distrib(0, num_total-cur_value);

  if (distrib(reng) < num_pick) {
    bst.insert(cur_value);  // insert `cur_value` to your BST
    --num_pick;
  }
  ++cur_value;
}
0 голосов
/ 25 марта 2019

Для множества уникальных «случайных» чисел я обычно использую Формат сохраняющего шифрование . Поскольку шифрование является взаимно-однозначным, вам гарантированы уникальные выходные данные, если они являются уникальными. Другой ключ шифрования будет генерировать другой набор выходных данных, то есть другую перестановку входных данных. Просто зашифруйте 0, 1, 2, 3, 4, ... и выходы гарантированно уникальны.

Вам нужны числа в диапазоне [1 .. 20 000]. К сожалению, для 20000 требуется 21 бит, и большинство схем шифрования имеют четное количество бит: в вашем случае 22 бита. Это означает, что вам нужно будет ездить на велосипеде; повторно зашифруйте вывод, если число слишком велико, пока не получите число в нужном диапазоне. Поскольку ваши входные данные доходят только до 10 000, а количество циклов выше 20 000, вы все равно избегаете дубликатов.

Единственный известный мне стандартный шифр, который допускает 22-битный размер блока, - это шифр Hasty Pudding. В качестве альтернативы достаточно просто написать свой собственный простой шифр Фейстеля . Четыре раунда достаточно, если вы не хотите криптографическую безопасность. Для защиты на криптографическом уровне вам необходимо использовать AES / FFX, который одобрен NIST.

...