С++ итерационный вектор случайным образом

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

Так как вектор является 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) у меня возникли некоторые проблемы с производительностью из-за объема требуемой памяти: общий вектор очень большой, и у меня много потоков и процессоров.

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

Ответ 1

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

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

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

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

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

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

Сложность:

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

Ответ 2

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

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

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

Ответ 3

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

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

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

Ответ 4

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

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

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

Ответ 5

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

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

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

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

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

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

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

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

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

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