Sẽ rất tốt nếu biết chúng ta đang nói về loại dữ liệu nào. Có bao nhiêu người dùng tồn tại? Trung bình có bao nhiêu người trực tuyến? Tỷ lệ "người dùng đã xem" so với tất cả người dùng (thưa thớt so với dày đặc) như thế nào?
Sửa đổi thuật toán của bạn Đừng bật cái đầu tiên mà hãy chọn một phần tử ngẫu nhiên từ nhóm người dùng trực tuyến. Điều này sẽ cải thiện việc cân đối và có thể giúp giảm bớt sự phức tạp trong phân bổ tùy thuộc vào tỷ lệ của hai tập hợp này!
Thuật toán thay thế (có cấu trúc hơn; vẫn là trường hợp xấu nhất; sẽ tốt nếu ít thấy )
- Giữ đã xem như một cây cân bằng (chèn O (log n))
- Giữ trực tuyến như một cây cân bằng.
- Mặc dù không có đủ người dùng được chọn:
- Tìm kiếm khoảng trống đầu tiên trong saw (ví dụ:[0,1,3,7] -> 2; O (log n) theo liên kết SO)
- Tìm kiếm người dùng đầu tiên> =gap-value (O (log n))
- Nếu người dùng
- -> chọn
- Khác
- -> thêm giá trị đã chọn tạm thời (cho thời điểm này; mô hình quyết định tần suất cập nhật trực tuyến ) đến đã xem HOẶC giới hạn tìm kiếm bằng cách nào đó thành> giá trị khoảng trống được chọn (O (log n))
Tùy thuộc vào dữ liệu, điều này sẽ hoạt động rất tốt nếu dữ liệu lớn và đã thấy thưa thớt!
