Генерация всех индексов последовательности, как правило, является плохой идеей, поскольку это может занять много времени, особенно если отношение чисел, которые нужно выбрать, к MAX низкое (сложность становится доминируемой O(MAX)).Это ухудшается, если отношение чисел, которые будут выбраны, к MAX приближается к единице, так как тогда удаление выбранных индексов из последовательности всех также становится дорогим (мы приближаемся к O(MAX^2/2)).Но для небольших чисел это обычно работает хорошо и не особенно подвержено ошибкам.
Фильтрация сгенерированных индексов с использованием коллекции также является плохой идеей, поскольку некоторое время затрачивается на вставку индексов в последовательность,и прогресс не гарантируется, поскольку одно и то же случайное число может быть нарисовано несколько раз (но для достаточно большого MAX это маловероятно).Это может быть близко к сложности
O(k n log^2(n)/2), игнорируя дубликаты и предполагая, что коллекция использует дерево для эффективного поиска (но со значительными постоянными затратами k на выделение узлов дерева и, возможно, с ребалансировкой ).
Другой вариант - генерировать случайные значения уникальным образом с самого начала, гарантируя прогресс.Это означает, что в первом раунде генерируется случайный индекс в [0, MAX]:
items i0 i1 i2 i3 i4 i5 i6 (total 7 items)
idx 0 ^^ (index 2)
Во втором раунде генерируется только [0, MAX - 1] (так как один элемент уже выбран):
items i0 i1 i3 i4 i5 i6 (total 6 items)
idx 1 ^^ (index 2 out of these 6, but 3 out of the original 7)
Значения индексов затем необходимо скорректировать: если второй индекс попадает во вторую половину последовательности (после первого индекса), его необходимо увеличить, чтобы учесть разрыв.Мы можем реализовать это как цикл, позволяющий нам выбирать произвольное количество уникальных элементов.
Для коротких последовательностей это довольно быстрый алгоритм O(n^2/2):
void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); // !!
// b1: 3187.000 msec (the fastest)
// b2: 3734.000 msec
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
// get a random number
size_t n_where = i;
for(size_t j = 0; j < i; ++ j) {
if(n + j < rand_num[j]) {
n_where = j;
break;
}
}
// see where it should be inserted
rand_num.insert(rand_num.begin() + n_where, 1, n + n_where);
// insert it in the list, maintain a sorted sequence
}
// tier 1 - use comparison with offset instead of increment
}
Где n_select_numэто ваши 5 и n_number_num это ваш MAX.n_Rand(x) возвращает случайные целые числа в [0, x] (включительно).Это можно сделать немного быстрее, если выбрать много элементов (например, не 5, а 500) с помощью двоичного поиска, чтобы найти точку вставки.Для этого нам нужно убедиться, что мы удовлетворяем требованиям.
Мы выполним бинарный поиск со сравнением n + j < rand_num[j], которое совпадает с
n < rand_num[j] - j.Нам нужно показать, что rand_num[j] - j все еще является отсортированной последовательностью для отсортированной последовательности rand_num[j].К счастью, это легко показать, поскольку наименьшее расстояние между двумя элементами оригинального rand_num равно единице (сгенерированные числа уникальны, поэтому всегда есть разница не менее 1).В то же время, если мы вычтем индексы j из всех элементов
rand_num[j], различия в индексе будут ровно 1. Так что в «худшем» случае мы получим постоянную последовательность - но никогда не уменьшаться.Поэтому можно использовать бинарный поиск, в результате чего получается алгоритм O(n log(n)):
struct TNeedle { // in the comparison operator we need to make clear which argument is the needle and which is already in the list; we do that using the type system.
int n;
TNeedle(int _n)
:n(_n)
{}
};
class CCompareWithOffset { // custom comparison "n < rand_num[j] - j"
protected:
std::vector<int>::iterator m_p_begin_it;
public:
CCompareWithOffset(std::vector<int>::iterator p_begin_it)
:m_p_begin_it(p_begin_it)
{}
bool operator ()(const int &r_value, TNeedle n) const
{
size_t n_index = &r_value - &*m_p_begin_it;
// calculate index in the array
return r_value < n.n + n_index; // or r_value - n_index < n.n
}
bool operator ()(TNeedle n, const int &r_value) const
{
size_t n_index = &r_value - &*m_p_begin_it;
// calculate index in the array
return n.n + n_index < r_value; // or n.n < r_value - n_index
}
};
И наконец:
void RandomUniqueSequence(std::vector<int> &rand_num,
const size_t n_select_num, const size_t n_item_num)
{
assert(n_select_num <= n_item_num);
rand_num.clear(); // !!
// b1: 3578.000 msec
// b2: 1703.000 msec (the fastest)
for(size_t i = 0; i < n_select_num; ++ i) {
int n = n_Rand(n_item_num - i - 1);
// get a random number
std::vector<int>::iterator p_where_it = std::upper_bound(rand_num.begin(), rand_num.end(),
TNeedle(n), CCompareWithOffset(rand_num.begin()));
// see where it should be inserted
rand_num.insert(p_where_it, 1, n + p_where_it - rand_num.begin());
// insert it in the list, maintain a sorted sequence
}
// tier 4 - use binary search
}
Я проверил это на трех тестах.Во-первых, 3 числа были выбраны из 7 элементов, и гистограмма выбранных элементов была собрана за 10000 прогонов:
4265 4229 4351 4267 4267 4364 4257
Это показывает, что каждый из 7 элементов был выбран примерно одинаковое количество раз,и нет никакого очевидного смещения, вызванного алгоритмом.Все последовательности также были проверены на правильность (уникальность содержания).
Второй критерий включал выбор 7 чисел из 5000 наименований.За время нескольких версий алгоритма было накоплено более 10 000 000 прогонов.Результаты обозначаются в комментариях в коде как b1.Простая версия алгоритма немного быстрее.
Третий тест - выбор 700 номеров из 5000.Время нескольких версий алгоритма было снова накоплено, на этот раз более 10000 прогонов.Результаты обозначаются в комментариях в коде как b2.Бинарная поисковая версия алгоритма теперь более чем в два раза быстрее, чем простая.
Второй метод начинает работать быстрее при выборе более чем приблизительно 75 элементов на моем компьютере (обратите внимание, что сложность любого алгоритма делаетне зависит от количества предметов, MAX).
Стоит отметить, что приведенные выше алгоритмы генерируют случайные числа в порядке возрастания.Но было бы просто добавить другой массив, в который будут сохраняться числа в том порядке, в котором они были сгенерированы, и возвращать его вместо этого (при незначительных дополнительных затратах O(n)).Нет необходимости перетасовывать вывод: это было бы намного медленнее.
Обратите внимание, что исходники находятся в C ++, у меня нет Java на моей машине, но концепция должна быть ясной.
РЕДАКТИРОВАТЬ :
Для развлечения я также применил подход, который генерирует список со всеми индексами
0 .. MAX, выбирает их случайным образом и удаляет их из списка вгарантия уникальности.Так как я выбрал довольно высокий MAX (5000), производительность катастрофическая:
// b1: 519515.000 msec
// b2: 20312.000 msec
std::vector<int> all_numbers(n_item_num);
std::iota(all_numbers.begin(), all_numbers.end(), 0);
// generate all the numbers
for(size_t i = 0; i < n_number_num; ++ i) {
assert(all_numbers.size() == n_item_num - i);
int n = n_Rand(n_item_num - i - 1);
// get a random number
rand_num.push_back(all_numbers[n]); // put it in the output list
all_numbers.erase(all_numbers.begin() + n); // erase it from the input
}
// generate random numbers
Я также реализовал подход с set (коллекция C ++), которая на самом деле идет вторым послебенчмарк b2, только на 50% медленнее, чем подход с двоичным поиском.Это понятно, поскольку set использует двоичное дерево, где стоимость вставки аналогична двоичному поиску.Единственное отличие - это шанс получить дубликаты предметов, что замедляет прогресс.
// b1: 20250.000 msec
// b2: 2296.000 msec
std::set<int> numbers;
while(numbers.size() < n_number_num)
numbers.insert(n_Rand(n_item_num - 1)); // might have duplicates here
// generate unique random numbers
rand_num.resize(numbers.size());
std::copy(numbers.begin(), numbers.end(), rand_num.begin());
// copy the numbers from a set to a vector
Полный исходный код здесь .