Эффективный метод случайного выбора всех элементов std :: vector ровно один раз БЕЗ перетасовки

Question

Я ищу эффективный метод выбора доступа к каждому элементу std::vector<T> в случайном порядке без перестановки или копирования, т.е. без использования std::random_shuffle и убедитесь, что каждый элемент выбран только один раз.

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

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

Answer 1

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

Я принимаю первый случай. Вам понадобится дополнительное хранилище для бухгалтерии, и вам все равно потребуется время для перетасовки. Поэтому создайте перестановку и сохраните ее память, чтобы вы могли перетасовать ее по своему усмотрению. С C++ 11:

#include <algorithm> 
#include <random> 
#include <numeric> 

struct permutation 
{ 
    permutation(size_t n) 
     : perm(n), g(std::random_device()) 
    { 
     std::iota(perm.begin(), perm.end(), size_t(0)); 
    } 

    void shuffle() { std::shuffle(perm.begin(), perm.end(), g); } 

    size_t operator[](size_t n) const { return perm[n]; } 

private: 
    std::vector<size_t> perm; 
    std::mt19937 g; 
}; 

Использование:

std::vector<huge_t> v; 
... 

permutation sigma(v.size()); 
sigma.shuffle(); 

const huge_t& x = v[sigma[0]]; 

... 
sigma.shuffle(); // No extra allocation 
const huge_t& y = v[sigma[0]]; 

Вы можете адаптировать код для использования 03 std::random_shuffle C++, но обратите внимание, что существует очень мало гарантий на генератор случайных чисел.

Answer 2

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

Answer 3

Я думаю, что решение простого (и один из более эффективных) было бы либо создать std::vector<size_t> удерживающие индексы в ваш vector<T> или std::vector<T*> держит указатели на ваш vector. Затем вы можете перетасовать тот, который использует std::random_shuffle, перебирайте его и выбирайте соответствующие элементы из вашего исходного вектора. Таким образом, вы не меняете порядок своих исходных векторов и указателей перетасовки или size_t довольно дешево