Как рандомизировать отсортированный список?

Question

Вот странный вопрос для вас, ребята,

У меня есть хороший отсортированный список, который я хочу рандомизировать. Как мне это сделать?

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

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

Итак, есть какие-нибудь идеи о том, как мне организовать рандомизацию упорядоченного списка?

Answer 1

Использование std::random_shuffle. Если вы хотите реализовать метод самостоятельно, посмотрите на Fisher-Yates shuffle .

Answer 2

Вы можете попробовать алгоритм random_shuffle , но обратите внимание, что он не будет работать на list, так как для него требуются итераторы произвольного доступа. Вы можете использовать его на vector или deque, однако.

Answer 3

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

Answer 4

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

Возможно, что вам действительно нужно сделать, это на самом деле не рандомизировать это, а скорее прочитать в каком-то порядке, отличном от спереди к спине. Например, если в списке есть n членов, возможно, вам следует обработать 1, n, 2, n-1, 3, n-2 и т. Д. Или 1, n / 2, 2, n / 2 + 1, 3, n / 2 +2 и т. Д.

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

Answer 5

Предполагая, что ваш «список» не означает связанный список, но вместо этого означает что-то, поддерживающее произвольный доступ (например, массив, std :: vector или std :: deque), std :: random_shuffle может быть полезным.

Answer 6

std::random_shuffle(thelist.begin(), thelist.end());