Làm cách nào để triển khai thuật toán giống Digg?

Question

Làm cách nào để triển khai trang web có hệ thống đề xuất tương tự như stackoverflow/digg/reddit? Tức là, người dùng gửi nội dung và trang web cần tính toán một số loại "nóng" theo mức độ phổ biến của mục. Dòng chảy như sau:

• Người dùng gửi nội dung
• người dùng khác xem và bỏ phiếu về nội dung (giả định 90% số người dùng chỉ xem nội dung và 10% chủ động bỏ phiếu lên hoặc xuống trên nội dung)
• Nội dung mới liên tục được gửi

Làm cách nào để triển khai thuật toán tính toán "độ nóng" của mục được gửi, tốt nhất là trong thời gian thực? Có bất kỳ thực hành hay mẫu thiết kế nào tốt nhất?

tôi sẽ giả định rằng các thuật toán mất sau đây vào xem xét:

• Khi một mục đã được gửi
• Khi mỗi phiếu được đúc
• Khi mục được xem

Ví dụ: một vật phẩm nhận được một số phiếu bầu liên tục sẽ ở lại phần nào "nóng" liên tục trong khi một mục nhận được số phiếu bầu khi lần đầu tiên được gửi sẽ nhảy lên đầu danh sách "nóng" nhưng sau đó giảm xuống khi phiếu bầu dừng lại sắp tới.

(Tôi đang sử dụng MySQL + PHP nhưng tôi quan tâm đến các mẫu thiết kế chung).

Answer 1

Bạn có thể sử dụng một cái gì đó tương tự như Reddit algorithm - nguyên tắc cơ bản trong số đó là bạn tính toán giá trị cho bài đăng dựa trên thời gian nó được đăng và điểm số. Điều gọn gàng về thuật toán Reddit là bạn chỉ cần tính lại giá trị khi điểm số của bài đăng thay đổi. Khi bạn muốn hiển thị trang chủ của mình, bạn chỉ nhận được n bài đăng hàng đầu từ cơ sở dữ liệu của mình dựa trên điểm số đó. Theo thời gian, điểm số sẽ tăng tự nhiên, vì vậy bạn không phải thực hiện bất kỳ xử lý đặc biệt nào để xóa các mục khỏi trang chủ.

Answer 2

Trên trang web của riêng tôi, tôi chỉ định mỗi mục nhập một số nguyên duy nhất từ ​​một chuỗi tăng đơn điệu (các bài đăng mới hơn có số cao hơn). Mỗi phiếu bầu tăng số lượng một, và mỗi phiếu bầu giảm xuống một số (bạn có thể tinh chỉnh các giá trị này, tất nhiên). Sau đó, chỉ cần sắp xếp theo số để hiển thị các mục 'nóng nhất'.

Answer 3

tôi đã phát triển một trang web đánh dấu trang xã hội, Sites Favoritos, và sử dụng một thuật toán phức tạp:

1. Thứ nhất, số phiếu là hữu hạn, một người sử dụng chỉ có một số giới hạn số phiếu, và số phiếu biểu quyết phụ thuộc vào điểm người dùng. Để kiếm điểm, mỗi người dùng phải thêm các liên kết nhận phiếu bầu tích cực.
2. Sau đó, người dùng có thể bỏ phiếu -3, -2, -1,1,2 hoặc 3 phiếu bầu cho mỗi liên kết. Vì số phiếu bầu bị giới hạn, mỗi người dùng sẽ chỉ bỏ phiếu cho những liên kết mà họ thích.
3. Để ngăn người dùng bỏ phiếu chỉ trên các liên kết cho cùng một người dùng, tạo nhóm hỗ trợ, các điểm mà mỗi phiếu bầu thêm vào liên kết phụ thuộc vào racio giữa tổng số phiếu bầu và phiếu bầu cho liên kết của chủ sở hữu của liên kết bình chọn. Nếu bạn luôn bỏ phiếu trên cùng một liên kết người dùng, phiếu bầu của bạn sẽ mất giá trị.
4. Phiếu bầu mất giá trị theo thời gian.
5. Các liên kết mới từ người dùng không có điểm (người dùng mới) sẽ có điểm khởi đầu 0 điểm. Các liên kết mới từ người dùng cũ sẽ có điểm tùy thuộc vào điểm của họ. Khác nhau, từ +3 đến vô hạn. Liên kết từ người dùng có điểm tiêu cực sẽ có điểm bắt đầu tiêu cực, liên kết từ người dùng có điểm tích cực sẽ có điểm bắt đầu tích cực.

Người dùng sẽ nhận được điểm ngẫu nhiên khi liên kết của họ được bỏ phiếu. Phiếu tích cực cho điểm tích cực, số phiếu âm cho các điểm âm.

Answer 4

Paul Graham đã viết một bài luận về những gì ông đã học được trong developing Hacker News. Sự nhấn mạnh là nhiều hơn vào những người/tương tác mà anh ta đang cố gắng thu hút/tạo ra hơn là trên thuật toán, nhưng vẫn đáng để đọc. Ví dụ, ông thảo luận về các kết quả khác nhau khi những câu chuyện bong bóng từ phía dưới (HN) so với bùng nổ lên đầu trang (Digg) của trang đầu. (Mặc dù từ những gì tôi đã nhìn thấy của HN, có vẻ như những câu chuyện nổ tung đến đỉnh đó cũng vậy).

Ông đưa ra câu nói này:

Chìa khóa để thực hiện là sang trọng, không tiểu đoàn các trường hợp đặc biệt.

mà trong ánh sáng của purported algorithm để tạo ra các trang HN trước:

(p - 1)/(t + 2)^1,5

nơi

p = một điểm bài viết và

t = thời gian gửi bài viết

có thể là điểm khởi đầu tốt.

Answer 5

tôi thực hiện một phiên bản SQL của thuật toán xếp hạng Reddit cho một aggregator video như vậy:

SELECT id, title 
FROM videos 
ORDER BY 
    LOG10(ABS(cached_votes_total) + 1) * SIGN(cached_votes_total) 
    + (UNIX_TIMESTAMP(created_at)/300000) DESC 
LIMIT 50 

* cached_votes_total * được cập nhật bởi một nút bấm bất cứ khi nào một cuộc bỏ phiếu mới là diễn viên. Nó chạy đủ nhanh trên trang web hiện tại của chúng tôi, nhưng tôi đang lên kế hoạch thêm cột giá trị xếp hạng và cập nhật nó với cùng một trình kích hoạt như cột * cached_votes_total *. Sau khi tối ưu hóa, nó phải đủ nhanh cho hầu hết mọi trang web có kích thước.