Если качество не влияет, то сделай обертку для доступа к массиву:

int f_xs(int i) { return xs[(i + seed) % N]; }

И на каждой итерации рандомизации просто вычисляй новый seed;

seed = random();

Все индексы массива сдвинуться на одно и то же число по модулю N :)

А как ты потом перемешанный массив используешь?

Как это правильно называется на английском языке

parallel random permutation

и какими алгоритмами реализуется?

Например вот https://arxiv.org/abs/1508.03167

Для монтекарло-моделирования ионизации электронным ударом, мне нужно убрать паразитную селективность скоростей для «жертв» связанную с тем в каком порядке они поступают в ячейку пространства.

Спасибо, погляжу.

не, я в другом, ...

в практическом смысле: изменил ты исходный массив xs. Что ты потом с ним делаешь? Весь используешь? Берешь отдельно взятые элементы? Записываешь в книжечку в файл?

Ок, поясню. Есть массив векторов vecs[N], сожержащий скорости и координаты, каждый вектор можно привязать к узлу сетки {x,y}. Есть массив ids[nx,ny,M], который хранит (0..M) привязок узлов сетки к элементам массива vecs. Заполняю его, соответственно, обходя vecs и добавляя элементы в ids пока там есть место. Потом использую эти индексы как ссылки на «жертв», работая с ними по принципу LIFO («жертв», заведомо меньше M). Из-за этого получается что в ids пишутся в основном вектора из начала массива. Положение же в массиве векторов по алгоритмическим причинам связано со скоростями которые они кодируют, из-за этого получается селективность в выборе «жертв», а выбор должен быть равномерным.

Я пробовал сделать в два этапа: сначала считать сколько всего векторов соответствует каждому узлу сетки, пусть K[nx,ny]; затем кидать случайное число между R=(0..K) и записывать индекс если R<M. Это ослабило селективность, но она осталась. Что бы полностью от неё избавиться, похоже что остаётся только рандомизация исходного массива векторов.

Если можно что-то ещё придумать, то буду рад совету.

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

• при тяге к перфекционизму начинаем с std::random_shuffle
• на каждой итерации циклически сдвигаем весь массив (например, первый становится вторым, а последний первым) и меняем первый элемент со случайным из остальных.
• при необходимости в каждом потоке можно запустить свой собственный prng (простой конгруэнтный сойдет) и начать со своей случайной перестановки.

если в ids пишутся вектора из

начала массива vecs, то, насколько я понимаю (а я начинаю запутываться уже со слов «массив векторов»), тебе нужно отсортировать vecs по скоростям, и далее следить, чтобы в ids сначала попадали из самого начала vecs (скажем с индексами 1-100), потом из участка vecs с меньшими скоростями (с индексами 100-200), потом еще меньшими и т.д.

Правда тогда не ясно при чем тут жертвы и как как сюда относится второй абзац :)

В общем «я - логопед, чем смог - помог» :)

При этом, «качество» рандомизации не играет роли

Для монтекарло-моделирования

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

Там где играет (при расчёте вероятностей) там нормальный честный рандом. А этот нужен что бы фон исправить, который считается неподвижным.

А что, фон тебе неважен? Погрешность в 1/sqrt(N) гарантируется только при правильном рандоме. Если рандом неправильный, то и результат бессмыссленный, фон это там или не фон.

Ну то есть тебе виднее конечно, я не в курсе твоего эксперимента, но удивление немного вызывает.

Null-collision, считаются не взаимные вероятности, а вероятность столкнуться с фоном, который в первом приближении характеризуется только концентрацией, во втором — ещё средней потоковой скоростью. А температурный (и любой другой) разброс скоростей для фона много меньше чем для электронов. Т.е. вообще-то говоря, из фона а мог бы брать частицы в любом порядке, но из-за особенностей работы алгоритма в массиве они расположены с некоторой селективностью по скоростям, в результате, особенно при больших частотах ионизации возникают артефакты.

А что, в этом перемешивании прямо такой боттлнек что его нужно делать параллельно? Стандартный линейный

for (i=0; i<vec.len()-1; i++) {
  swap(vec[i], vec[rand(i, vec.len())]);
}

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

А так не знаю, если идеальное качество не нужно, можно попробовать отдельными потоками перемешивать непересекающиеся выборки из массива, т.е. в случае двух потоков, например, один мешает только чётные элементы (с чётными), другой только нечётные. Конкретно это будет очень плохо дружить с кэшом и всё замедлит, но можно попробовать работать с бОльшими блоками (т.е. первый поток работает на элементах 0÷127, 256÷383, … второй - 128÷255, 384÷511, …). Нужно будет немного битовой магии чтобы вычислить индексы.

правильно называется на английском языке

parallel shuffle?

А может подойти такой алгоритм?

Предположим у нас есть алгоритм многопоточной сортировки и есть многопоточный алгоритм заполнения массива случайными числами.

Есть src[N] массив исходных данных. Заводим структуру Item с двумя полями index и priority.

index - будет ссылаться на некий элемент в src[N] priority - приоритет, нужен для вспомогательных нужд.

Заводим массив из Item dst[N].

Заполняем поля index по порядку, а priority случайным образом (многопоточно). Потом сортируем (многопоточно) по priority. В итоге получаем некое подобие индекса перемешиваний.