C++ повторить вектор случайным образом

Question

Я работаю над многопоточной программой, где все потоки разделяют вектор (только для чтения). Цель каждого потока - перемещение всего вектора. Тем не менее, все потоки должны посещать этот вектор по-другому.

Поскольку вектор является const и используется для всех потоков, я не могу использовать random_shuffle и просто перебирать его. Сейчас мое решение построить вектор CrossRef, который будет содержать индексы по общему вектору, а затем перетасовать этот вектор, т.е.

 std::vector<int> crossref(SIZE) ; // SIZE is the size of the shared vector 
    std::iota (std::begin(crossref), std::end(crossref), 0); // Fill with indices ref 
    std::mt19937 g(SEED); // each thread has it own seed. 
    std::shuffle (crossref_.begin(), crossref_.end(), g); // Shuffle it 

Тем не менее, делать это выявить некоторые проблемы (1) он не очень эффективен, так как каждый поток должен получить доступ к своему вектору crossref перед доступом к совместно используемому, (2) у меня есть некоторые проблемы с производительностью из-за объема требуемой памяти: общий вектор очень большой, и у меня много потоков и процессоров.

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

Answer 1

Вы можете использовать алгебраическое понятие primitive root modulo n. В основном

Если п является положительным целым числом, целые числа от 1 до N - 1, которые взаимно просты с п образуют группу примитивных классов по модулю п. Эта группа циклично тогда и только тогда, когда п равно 2, 4, р^к, или 2р^к, где р^к является степень нечетного простого числа

Википедия показывает, как вы можете создать номера ниже 7 используя 3 как генератор.

Из этого утверждения вы черпаете алгоритм.

1. Возьмите свой номер n
2. Найти следующее простое число m, которое больше, чем n
3. Для каждого из вашего потока выбрать уникальное случайное число F(0) между 2 и m
4. вычислит следующий индекс, используя F(i+1) = (F(i) * F(0)) mod m. Если этот индекс находится в пределах диапазона [0, n], обратитесь к элементу. Если не перейти к следующему индексу.
5. Стоп после m - 1 итераций (или когда вы получаете 1, это то же самое).

Поскольку m простое, каждое число от 2 до М-1 взаимно просто с m так является генератором последовательности {1 ... m}. Вам гарантировано, что в первых повторения не будет повторяться число, и все номера m - 1 появятся.

Сложность:

• Шаг 2: Готово один раз, сложность эквивалентна нахождению простых чисел до п, т.е. sieve of Eratosthenes
• Шаг 3: Готово один раз, вы можете выбрать 2, 3, 4, 5 , и т. д. ... O(thread count)
• Шаг 4: O(m) время, O(1) в пространстве на резьбу. Вам не нужно хранить F (i). Вам нужно знать только первое значение и последнее значение. Это те же свойства, что и приращение

Answer 2

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

E.g. C++ std::vector<bool> (http://en.cppreference.com/w/cpp/container/vector_bool) - это бит-массив, который достаточно эффективен для памяти.

Каждая нить может иметь свой собственный vector<bool>, указывающий на то, что она посетила определенный индекс. Затем вам придется использовать циклы CPU, чтобы случайно выбрать индекс, который он еще не посетил, и завершить, когда все bool s - true.

Answer 3

Если я правильно понимаю, вы хотите, чтобы генерировать случайную перестановку в инкрементном образе, т.е. вы хотите позвонить п раз в функции х так, что он генерирует все переставленных числа от 1 до н, так что функция имеет постоянную память.

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

Если это так, вы можете сгенерировать перестановку, принимая число р прайм с п и вычислить для каждого я в [1, п]: i.p (mod n). Например, если у вас есть n = 5 и p = 7, то 7% 5 = 2, 14% 5 = 4, 21% 5 = 1, 28% 5 = 3, 35% 5 = 0. Вы можете объединить несколько таких функций, чтобы получить что-то удовлетворяющее для вас ...

Answer 4

Это не полный ответ, но он должен привести нас к правильному решению.

Вы написали некоторые вещи, которые мы могли бы принять в качестве допущений:

(1) это не очень эффективно, так как каждый поток должен получить доступ к его CrossRef вектора перед обращением к разделяемым один,

Это вряд ли будет правдой. Мы говорим об одном косвенном поиске. Если ваши ссылочные данные действительно являются вектором ints, это будет представлять собой бесконечно малую часть вашего времени выполнения. Если справочные данные вектор Интс, то просто сделать N копий этого и перетасовать их ...

(2) У меня есть некоторые перформансы проблемы из-за объема памяти требуется: общий вектор является очень большой, и у меня много потоков и процессоров.

Насколько велика? Вы его измеряли? Сколько дискретных объектов есть в векторе? Насколько велика каждая из них?

Сколько потоков?

Сколько процессоров?

Сколько у вас памяти?

Профилировали ли вы код? Вы уверены, что, где узкое место производительности? Вы считали более элегантный алгоритм?

Answer 5

Кажется, this парень решил вашу проблему очень красиво.

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

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