Ngày 15 tháng 8 năm 2020 bởi Chaofa Yuan - Dưới 1 phút đọc. Tài liệu phỏng vấn tải game bắn cá đổi thưởng tiền mặt quý báu.

Nội dung trang này:

• Thuật toán Reservoir Sampling

Thuật toán Reservoir Sampling là một thuật toán lấy mẫu ngẫu nhiên từ một tập hợp lớn mà kích thước của nó có thể không được biết trước. Điểm khó khăn trong thuật toán này không nằm ở cách thực hiện nó, mà nằm ở chỗ phải chứng minh rằng mỗi phần tử đều có xác suất được chọn như nhau.

Hai tài liệu hướng dẫn chứng minh tốt nhất cho thuật toán Reservoir Sampling là:

1. Một bài viết chi tiết về lý thuyết xác suất.
2. Một video giải thích trực quan với ví dụ cụ thể.

Các tài liệu khác thường không sunvip.club giải thích rõ ràng hoặc thiếu sót một số khía cạnh quan trọng.

Lôgic chính của thuật toán Reservoir Sampling:

Dưới đây là mã nguồn Python để thực hiện thuật toán Reservoir Sampling:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import random

def reservior_sampling(n, k):
    """
    Hàm này nhận đầu vào là n số và trả về k số được chọn ngẫu nhiên.
    """
    # Tạo danh sách các số từ 1 đến n
    nums = [i for i in range(1, n + 1)]
    
    # Khởi tạo danh sách kết quả với độ dài k
    res = []
    
    # Bước 1: Đặt k phần tử đầu tiên vào reservoir
    for i in range(k):
        res.append(nums[i])
    
    # Bước 2: Xử lý các phần tử tiếp theo từ vị trí k đến n-1
    for i in range(k, len(nums)):
        # Tính toán xác suất chọn phần tử thứ i
        replace_idx = random.randint(0, i)
        
        # Nếu chỉ số ngẫu nhiên nhỏ hơn k, thay thế phần tử trong reservoir
        if replace_idx < k:
            res[replace_idx] = nums[i]
    
    return res

# Ví dụ sử dụng hàm reservior_sampling
pool = reservior_sampling(100, 10)
print(pool)
# Kết quả có thể là: [78, 52, 41, 84, 66, 43, 25, 71, 45, 24]

Trong đoạn mã trên, chúng ta đã mô tả chi tiết từng bước của thuật toán Reservoir Sampling. Ban đầu, k phần tử đầu tiên được đưa thẳng vào reservoir. Sau đó, đối với mỗi phần tử tiếp theo, chúng ta tính toán xác suất nó sẽ thay thế một phần tử hiện có trong reservoir. Điều này đảm bảo rằng tất cả các phần tử đều có cùng xác suất được chọn vào cuối quá trình.

Đây là một phương pháp hiệu quả khi cần lấy mẫu từ một luồng dữ liệu lớn mà không thể lưu trữ toàn bộ dữ liệu trong bộ nhớ.