Làm thế nào để chọn một phần tử ngẫu nhiên trong std :: set?

Question

Làm cách nào để chọn một phần tử ngẫu nhiên trong một số std::set?

Tôi ngây thơ cố gắng này:

int GetSample(const std::set<int>& s) { 
    double r = rand() % s.size(); 
    return *(s.begin() + r); // compile error 
} 

Nhưng operator+ không được phép theo cách này.

Answer 1

Bạn có thể sử dụng phương thức std::advance.

#include <set> 
#include <algorithm> 

int main() { 
    using namespace std; 
    // generate a set... 
    set<int> s; 
    for(int i = 0; i != 10; ++i) s.insert(i); 

    set<int>::const_iterator it(s.begin()); 

    // 'advance' the iterator 5 times 
    advance(it,5); 
} 

Answer 2

int GetSample(const std::set<int>& s) { 
    double r = rand() % s.size(); 
    std::set<int>::iterator it = s.begin(); 
    for (; r != 0; r--) it++; 
    return *it; 
} 

sẽ là một cách để làm việc đó, mặc dù không đẹp;

Answer 3

Nếu truy cập ngẫu nhiên là quan trọng và bạn có thể sống với nỗ lực trung bình O (N) để chèn, thì cách giải quyết được đưa ra trong this paper có thể thuận tiện.

Ý tưởng chính là sử dụng một véc tơ được sắp xếp, và sau đó để tra cứu hàm std::lower_bound. Điều này, tra cứu lấy O (log N) giống như trong một tập bình thường. Hơn nữa, (ngẫu nhiên) chèn lấy O (N), vì tất cả các phần tử sau đây phải được dịch chuyển giống như trong một vectơ bình thường (và có thể một sự tái phân bổ được thực hiện). Tuy nhiên, chèn ở phía sau là hằng số (ngoại trừ việc phân bổ lại. Bạn có thể tránh điều này bằng cách gọi số reserve() với bộ nhớ đủ lớn).

Cuối cùng, điểm chính của câu hỏi: Truy cập ngẫu nhiên là O (1). Chỉ cần vẽ một số ngẫu nhiên i từ phân phối đồng đều trong [0, V.size()-1] và trả về phần tử tương ứng V[i].

Đây là cơ sở mã trên giấy, thực hiện vectơ được sắp xếp này. Hãy mở rộng nó khi cần:

template <class T, class Compare = std::less<T> > 
struct sorted_vector { 
using std::vector; 
using std::lower_bound; 
vector<T> V; 
Compare cmp; 
typedef typename vector<T>::iterator iterator; 
typedef typename vector<T>::const_iterator const_iterator; 
iterator begin() { return V.begin(); } 
iterator end() { return V.end(); } 
const_iterator begin() const { return V.begin(); } 
const_iterator end() const { return V.end(); } 

//...if needed, implement more by yourself 

sorted_vector(const Compare& c = Compare()) : V(), cmp(c) {} 
template <class InputIterator> 
sorted_vector(InputIterator first, InputIterator last, Const Compare& c = Compare()) 
: V(first, last), cmp(c) 
{ 
std::sort(begin(), end(), cmp); 
} 

//... 

iterator insert(const T& t) { 
    iterator i = lower_bound(begin(), end(), t, cmp); 
    if (i == end() || cmp(t, *i)) 
     V.insert(i, t); 
     return i; 
} 
const_iterator find(const T& t) const { 
    const_iterator i = lower_bound(begin(), end(), t, cmp); 
     return i == end() || cmp(t, *i) ? end() : i; 
} 
}; 

Để thực hiện tinh vi hơn, bạn cũng có thể xem xét this page.

CHỈNH SỬA: hoặc thậm chí tốt hơn, sử dụng boost::container::flat_set, triển khai tập hợp bằng cách sử dụng ý tưởng ở trên, tức là vectơ được sắp xếp.

Answer 4

Giải pháp thứ nhất: O (log n) trong thời gian/ O (1) trong không gian

Một giả thuyết trong một chú thích ở trên, nó có thể được thực hiện trong O (log (không đồng đều!) (n)) (so với O (n) cho std::advance) mà không cần vector (sử dụng O (n) không gian) bằng cách sử dụng phương pháp tôi mô tả here.

Về cơ bản, bạn:

• kiểm tra nếu tập rỗng (nếu nó là, không có hy vọng)
• tạo ra một giá trị ngẫu nhiên
• nếu đã có gửi lại khác chèn nó
• lấy một trình lặp it trên đó
• lấy phần tử ngẫu nhiên là *(it++) hoặc *(set.begin()) nếu it ở cuối
• trở lại nó không trước khi xóa phần tử bạn chèn

n.b: Như đã chỉ ra bởi Aaron phần tử không được chọn thống nhất một cách ngẫu nhiên. Bạn cần xây dựng phần tử ngẫu nhiên với cùng phân phối hơn các phần tử trong tập hợp để tiếp cận một cuộc thăm dò đồng nhất.

Giải pháp thứ hai: O (1) trong thời gian/ O (n) trong không gian (thống nhất)

davidhigh đã đưa ra giải pháp với một vector nhưng có một vấn đề bởi vì khi bạn pop một phần tử của ngăn xếp, bạn sẽ phải thực hiện tìm kiếm tuyến tính trong O (n) hoặc bạn có thể tạo lại vectơ của mình mỗi khi bạn muốn lấy một phần tử ngẫu nhiên nhưng đó cũng là O (n).

Để tránh vấn đề này và giữ cho chèn/xóa để O (log n), bạn có thể giữ một std::unordered_set và sử dụng một similar method đến giải pháp đầu tiên để có được một yếu tố ngẫu nhiên trong O (1).

p.s: Nếu các phần tử của bạn lớn, bạn có thể sử dụng một bộ con trỏ không có thứ tự (với phần cắt đã sửa đổi) để tiết kiệm bộ nhớ.

Answer 5

C++ 17 std::sample

Đây sẽ là một thuận lợi, mặc dù không phải là rất hiệu quả (O (n)) Phương pháp:

#include <algorithm> 
#include <iostream> 
#include <random> 
#include <set> 
#include <vector> 

int main() { 
    std::set<int> in{1, 2, 3, 5, 7}; 
    std::vector<int> out; 
    std::sample(in.begin(), in.end(), std::back_inserter(out), 
       3, std::mt19937{std::random_device{}()}); 
    for (auto i : out) 
     std::cout << i << std::endl; 
} 

Nhưng tôi nghĩ rằng đối với hiệu quả bạn chỉ cần sao chép sang một loại cấu trúc khác: How to select a random element in std::set in less than O(n) time?