13
Có một thuật toán về cách thực hiện lấy mẫu hồ chứa khi các điểm trong luồng dữ liệu có trọng số liên kết không?Có một thuật toán để lấy mẫu hồ chứa có trọng số
A
Trả lời
13
Thuật toán bởi Pavlos Efraimidis và Paul Spirakis giải quyết chính xác vấn đề này. Tài liệu gốc với chứng minh hoàn chỉnh được xuất bản với tiêu đề "Lấy mẫu ngẫu nhiên có trọng số với một hồ chứa" trong Thư xử lý thông tin năm 2006, nhưng bạn có thể tìm thấy một bản tóm tắt đơn giản here.
Thuật toán hoạt động như sau. Đầu tiên quan sát rằng một cách khác để giải quyết lấy mẫu hồ chứa không cân bằng là gán cho mỗi phần tử một id ngẫu nhiên R giữa 0 và 1 và tăng dần (nói với một đống) theo dõi các id k hàng đầu. Bây giờ chúng ta hãy xem xét phiên bản có trọng số và giả sử phần tử thứ i có trọng số là w_i. Sau đó, chúng tôi sửa đổi thuật toán bằng cách chọn id của phần tử thứ i là R^(1/w_i) trong đó R được phân phối lại một lần nữa trong (0,1).
Một bài viết khác nói về thuật toán này là this one bởi những người Cloudera.
+4
Và triển khai python một dòng: 'heapq.nlargest (k, items, key = lambda item: math.pow (random.random(), 1/weight (item)))' –
+0
Có thể thực hiện điều này bằng cách thay thế ? – eleanora
+0
@eleanora Không có điểm để thực hiện việc này với sự thay thế vì phương thức bí danh tồn tại, trước tiên bạn cần tạo một bảng, có thời gian O (n), sau đó mỗi lựa chọn là O (1). Tuy nhiên, bí danh không giữ độ phức tạp của thời gian chạy trừ khi bạn sử dụng nó thay thế. – snb
5
Bạn có thể thử thuật toán A-ES từ this paper of S. Efraimidis. Nó khá đơn giản để mã hóa và rất hiệu quả.
Hope this helps,
Benoit
quá rộng? Tôi nghĩ câu hỏi là yêu cầu một thuật toán rất cụ thể. –
Hoàn toàn đồng ý với @ JuanA.Navarro - câu hỏi rất hữu ích cho luồng hoặc xử lý song song, và nên được mở cửa trở lại (câu trả lời của ông là rất tốt quá, BTW). –