Realtime theo dõi của top 100 từ twitter mỗi phút/giờ/ngày

Question

Gần đây tôi đi qua này câu hỏi phỏng vấn:

Given a continuous twitter feed, design an algorithm to return the 100 most 
frequent words used at this minute, this hour and this day. 

Tôi đã nghĩ đến một hệ thống với một bản đồ băm của word -> count liên quan đến 3 min-heap cho phút, giờ và ngày hiện tại.

Mỗi tin nhắn gửi đến được tokenized, vệ sinh và đếm từ được cập nhật trong bản đồ băm (và tăng-key trong đống nếu từ đó đã tồn tại trong nó)

Nếu bất cứ từ nào không tồn tại trong heap (và kích thước heap == 100) kiểm tra nếu frequency > min value của chúng trong heap và nếu vậy thì trích xuất-min và chèn vào heap.

Có cách nào tốt hơn để thực hiện việc này không?

Answer 1

Thuật toán của bạn là một khởi đầu tốt, nhưng nó sẽ không tạo ra kết quả chính xác. Vấn đề là các bảng băm theo cách bạn mô tả chúng là một con đường một chiều: một khi một từ được thêm vào, nó sẽ được tính mãi mãi.

Bạn cần một mảng 1440 (24 * 60) word+count bản đồ băm được tổ chức theo cách bạn mô tả; đây là số đếm từng phút của bạn. Bạn cần thêm hai bản đồ băm - cho tổng số giờ và ngày.

Xác định hai thao tác trên bản đồ băm - add và subtract, với ngữ nghĩa kết hợp số lượng từ giống nhau và loại bỏ các từ khi số đếm của chúng giảm xuống 0.

Mỗi phút bạn bắt đầu bản đồ băm mới và cập nhật số lượng từ nguồn cấp dữ liệu. Vào cuối phút, bạn đặt bản đồ băm đó vào mảng cho phút hiện tại, thêm nó vào tổng số cuộn cho giờ và trong ngày, sau đó trừ bản đồ băm của một giờ trước từ tổng số giờ chạy, và trừ bản đồ băm của 24 giờ trước từ tổng số hoạt động hàng ngày.

Cuối cùng, bạn cần một cách để tạo ra 100 từ hàng đầu được cung cấp một bản đồ băm. Đây phải là một nhiệm vụ tầm thường - thêm các mục vào một mảng của các mục nhập word+count, sắp xếp theo số lượng và giữ nguyên giá trị đầu 100.

Answer 2

dasblinkenlight làm điểm tốt cho một lỗi không loại trừ các mục khỏi bản đồ băm của bạn. Tuy nhiên, có thêm một điều nữa để tính toán các từ K đầu tiên cho một phút/giờ/ngày, sử dụng phân vùng (O (n)) nhanh hơn là phân loại (O (nlgn)):

1. đổ một hashmap của từ một phút/giờ/ngày của đếm vào một mảng: O (n)
2. sử dụng trung bình-of-trung bình lựa chọn để có được những elem K-thứ: O (n)
3. phân vùng xung quanh elem thứ K: O (n)

HTH.