Phương pháp hiệu quả để chọn ngẫu nhiên tất cả các phần tử của std :: vectơ chính xác một lần KHÔNG thay đổi lại

Question

Tôi đang tìm một phương pháp hiệu quả để chọn truy cập vào từng phần tử của std::vector<T> theo thứ tự ngẫu nhiên mà không cần thay đổi hoặc sao chép chúng. std::random_shuffle và đảm bảo rằng mỗi phần tử chỉ được chọn một lần.

Tôi không muốn sao chép hoặc cải tổ lại dưới dạng a) mỗi trường hợp T có thể là đối tượng rất lớn và b) cho các hoạt động khác mà tôi sẽ thực hiện trên các phần tử của vectơ. để giữ nguyên theo thứ tự.

Hơn nữa, tôi thực sự không muốn đi xuống con đường liên tục chọn và từ chối trùng lặp. Có thể tôi sẽ có rất nhiều đối tượng lớn được lưu trữ trong vector và hiệu quả là chìa khóa vì tôi sẽ tìm cách gọi phương thức chọn ngẫu nhiên này nhiều lần trong một giây.

Answer 1

Bạn không cho chúng tôi biết bạn có muốn lặp lại toàn bộ mảng một cách ngẫu nhiên hay không. .

Tôi giả định trường hợp đầu tiên. Bạn sẽ cần thêm bộ nhớ để lưu giữ sổ sách và bạn sẽ cần thời gian tuyến tính để xáo trộn. Vì vậy, tạo ra một hoán vị, và giữ cho bộ nhớ của nó còn sống để bạn có thể cải tổ nó như bạn muốn. Với 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; 
}; 

Cách sử dụng:

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

Bạn có thể thích ứng với mã để sử dụng C++ 03 std::random_shuffle, nhưng xin lưu ý rằng có rất ít bảo đảm trên bộ tạo số ngẫu nhiên.

Answer 2

Tạo vectơ có cùng kích thước với hình ảnh hiện tại sử dụng con trỏ đến các phần tử trong vectơ. Thay ngẫu nhiên các vector con trỏ thay vào đó và đọc từ đó - đó là chi phí thấp.

Answer 3

Tôi nghĩ giải pháp dễ nhất (và một trong những giải pháp hiệu quả hơn) là tạo một chỉ số nắm giữ std::vector<size_t> vào số vector<T> hoặc std::vector<T*> giữ con trỏ của bạn vào vector. Sau đó, bạn có thể xáo trộn một cái bằng cách sử dụng std::random_shuffle, lặp lại qua nó và chọn các phần tử tương ứng từ vectơ gốc của bạn. Bằng cách đó bạn không thay đổi thứ tự của vectơ gốc của bạn và các con trỏ ngẫu nhiên hoặc size_t là khá rẻ