Как рандомизировать отсортированный список?
Вот является странный вопрос для Вас парнями,
У меня есть хороший отсортированный список, который я хочу рандомизировать. Как я пошел бы о выполнении этого?
В моем приложении у меня есть функция, которая возвращает список точек, которые описывают схему дискретизированного объекта. Из-за пути проблема решена, функция возвращает хороший заказанный список. мне описали вторую границу в математике и хочу определить, пересекают ли два объекта друг друга. Я просто выполняю итерации по точкам и определяю, ли какая-либо точка в математической границе.
Метод работает хорошо, но я хочу увеличить скорость путем рандомизации данных точки. Так как вероятно, что та моя математическая граница будет перекрыта серией точек, которые являются правильными друг около друга, я думаю, что имело бы смысл проверять рандомизированный список вместо того, чтобы выполнить итерации по хорошему отсортированному одного (поскольку это только получает единственный удар для объявления пересечения).
Так, какие-либо идеи о том, как я пошел бы о рандомизации заказанного списка?
6 ответов
Используйте std :: random_shuffle . Если вы хотите реализовать метод самостоятельно, вам следует взглянуть на тасование Фишера-Йейтса .
Предполагая, что ваш «список» не означает связанный список, но вместо этого означает что-то, что поддерживает произвольный доступ (например, массив, std :: vector или std :: deque), std :: random_shuffle может быть полезным.
Вы можете попробовать алгоритм random_shuffle , но обратите внимание, что он не будет работать со списком , так как требует итераторов произвольного доступа. Однако вы можете использовать его в векторе или двухсторонней очереди .
std::random_shuffle(thelist.begin(), thelist.end());
Но ключевой вопрос будет заключаться в том, может ли время выполнения, необходимое для рандомизации списка, быть больше, чем время выполнения для его последовательного обхода.
Возможно, вам действительно нужно не рандомизировать его, а прочитать в каком-то порядке, а не от начала до конца. Например, если в списке n элементов, возможно, вам следует обработать 1, n, 2, n-1, 3, n-2 и т. Д. Или 1, n / 2, 2, n / 2 + 1, 3, n / 2 +2 и т. Д.
Если у вас всегда одинаковое количество баллов или если количество баллов попадает в небольшой конечный набор, вы можете заранее определить порядок оценки баллов для каждого возможного количества баллов, либо действительно случайным, либо, возможно, каким-то образом тщательно рассчитанным.
int array[N];
for(int i = N - 1; i > 0; i--) {
int j = rand() % i;
int tmp = array[i]; array[i] = array[j]; array[j] = i;
}