Chọn ngẫu nhiên một phần tử từ danh sách có trọng số

Question

Tôi có một danh sách 100.000 đối tượng. Mỗi phần tử danh sách đều có "trọng số" được liên kết với phần tử tích cực từ 1 đến N.

Cách hiệu quả nhất để chọn phần tử ngẫu nhiên trong danh sách là gì? Tôi muốn hành vi mà việc phân phối các phần tử được chọn ngẫu nhiên của tôi giống như phân bố trọng số trong danh sách.

Ví dụ: nếu tôi có danh sách L = {1,1,2,5}, tôi muốn phần tử thứ 4 được chọn 5/9thời gian, tính trung bình.

Giả sử chèn và xóa là phổ biến trong danh sách này, vì vậy bất kỳ phương pháp nào sử dụng "bảng tích phân" sẽ cần được cập nhật thường xuyên - hy vọng có giải pháp với thời gian chạy O (1) và O (1).

Answer 1

Bạn có thể sử dụng cây tìm kiếm nhị phân được tăng cường để lưu trữ các phần tử, cùng với tổng các trọng số trong mỗi cây con. Điều này cho phép bạn chèn và xóa các phần tử và trọng số theo bất kỳ cách nào bạn muốn. Cả hai mẫu và cập nhật yêu cầu thời gian O (lg n) cho mỗi hoạt động, và sử dụng không gian là O (n). Việc lấy mẫu được thực hiện bằng cách tạo một số nguyên ngẫu nhiên trong [1, S], trong đó S là tổng của tất cả các trọng số (S được lưu trữ ở gốc cây) và thực hiện tìm kiếm nhị phân bằng cách sử dụng các trọng lượng được lưu trữ cho mỗi cây con.

Answer 2

Một giải pháp chạy trong O (n) sẽ là bắt đầu bằng việc chọn phần tử đầu tiên. Sau đó, cho mỗi yếu tố sau đây hoặc giữ nguyên tố bạn có hoặc thay thế nó bằng phần tử tiếp theo. Hãy để w là tổng của tất cả các trọng lượng cho các yếu tố được xem xét cho đến nay. Sau đó giữ cái cũ với xác suất w/(w + x) và chọn cái mới với p = x/(w + x), trong đó x là trọng số của phần tử tiếp theo.

Answer 3

Nếu bạn biết tổng trọng lượng (trong trường hợp của bạn, 9) VÀ bạn sử dụng một cấu trúc dữ liệu truy cập ngẫu nhiên (danh sách ngụ ý O (n) thời gian truy cập), sau đó nó có thể được thực hiện nhanh chóng:

1) chọn một phần tử ngẫu nhiên (O (1)). Vì có 1/num_elems cơ hội cho một yếu tố được chọn ở bước này, nó cho phép chúng tôi sử dụng tăng cường num_elems* cho bước 2), do đó tăng tốc thuật toán.

2) tính toán xác xuất dự kiến ​​của nó: num_elems * (weight/total_weight)

3) lấy một số ngẫu nhiên trong phạm vi 0..1, và nếu nó là thấp hơn so với khả năng mong đợi, bạn có đầu ra. Nếu không, hãy lặp lại từ bước 1)

Answer 4

Tôi thực sự thích giải pháp của jonderry nhưng tôi tự hỏi liệu vấn đề này có cần cấu trúc phức tạp như cây tìm kiếm nhị phân được tăng cường hay không. Điều gì xảy ra nếu chúng ta giữ hai mảng, một với trọng số đầu vào, nói a = {1,1,2,5} và một với trọng số tích lũy (ý tưởng rất giống với giải pháp của jonderry) sẽ là b = {1,2,4 , 9}. Bây giờ tạo ra một số ngẫu nhiên trong [1 9] (nói x) và tìm kiếm nhị phân cho nó trong mảng tổng tích lũy. Vị trí i trong đó b [i] < = x và b [i-1]> x được ghi chú và [i] được trả về. Vì vậy, nếu số ngẫu nhiên là 3, chúng tôi sẽ nhận được i = 3, và [3] = 2 sẽ được trả về. Điều này đảm bảo độ phức tạp tương tự như giải pháp cây tăng cường với việc triển khai dễ dàng hơn.

Answer 5

Đây là những gì tôi đã làm để giải quyết nó:

def rchoose(list1, weights): 
    ''' 
    list1 : list of elements you're picking from. 
    weights : list of weights. Has to be in the same order as the 
       elements of list1. It can be given as the number of counts 
       or as a probability. 
    ''' 

    import numpy as np 

    # normalizing the weights list 
    w_sum = sum(weights) 
    weights_normalized = [] 
    for w in weights: 
     weights_normalized.append(w/w_sum) 

    # sorting the normalized weights and the desired list simultaneously 
    weights_normalized, list1 = zip(*sorted(zip(weights_normalized, list1))) 

    # bringing the sorted tuples back to being lists 
    weights_normalized = list(weights_normalized) 
    list1 = list(list1) 

    # finalizing the weight normalization 
    dummy = []; count = 0 
    for item in weights_normalized: 
     count += item 
     dummy.append(count) 
    weights_normalized = dummy 

    # testing which interval the uniform random number falls in 
    random_number = np.random.uniform(0, 1) 
    for idx, w in enumerate(weights_normalized[:-1]): 
     if random_number <= w: 
      return list1[idx] 

    return list1[-1]