Kiến trúc MySQL cho n * (n - 1)/2 thuật toán

Question

Tôi hiện đang phát triển một trang web nơi người dùng có thể tìm kiếm người dùng khác dựa trên thuộc tính (độ tuổi, chiều cao, thị trấn, giáo dục, v.v.). Bây giờ tôi muốn triển khai một số loại xếp hạng giữa hồ sơ người dùng. Đánh giá được tính toán thông qua thuật toán riêng dựa trên sự tương đồng giữa 2 cấu hình đã cho. Người dùng A có xếp hạng "xếp hạng so khớp" là 85 với Người dùng B và 79 với Người dùng C chẳng hạn. B và C có xếp hạng là 94 và tương tự ....

Người dùng có thể tìm kiếm các thuộc tính nhất định và lọc kết quả theo xếp hạng.

Vì xếp hạng khác với cấu hình và cũng phụ thuộc vào người dùng thực hiện tìm kiếm, tôi không thể thêm trường vào bảng người dùng của mình và sử dụng ORDER BY. Cho đến nay tôi đã đưa ra 2 giải pháp:

• giải pháp đầu tiên của tôi là có một công việc lô hàng đêm, cho phép tính giá cho mỗi kết hợp sử dụng càng tốt và lưu trữ nó trong một bảng riêng biệt (user1, user2, xếp hạng) . Sau đó tôi có thể tham gia bảng này với bảng người dùng và sắp xếp kết quả theo xếp hạng. Sau khi làm một số toán học, tôi đã tìm ra rằng giải pháp này không mở rộng tốt.

  Dựa trên công thức n * (n - 1)/2 có 45 kết hợp có thể cho 10 người dùng. Đối với 1.000 người dùng, tôi đột nhiên phải chèn 499.500 kết hợp xếp hạng vào bảng xếp hạng của tôi.

• Giải pháp thứ hai là rời khỏi MySQL và chỉ tính toán xếp hạng khi đang bay trong ứng dụng của tôi. Điều này cũng không quy mô tốt. Giả sử tìm kiếm chỉ trả lại 100 kết quả cho giao diện người dùng (có xếp hạng cao nhất ở trên cùng). Nếu tôi có 10.000 người dùng và tôi muốn thực hiện tìm kiếm cho mọi người dùng sống ở New York được xếp hạng theo xếp hạng, tôi phải tải mọi người dùng đang sống ở NY vào ứng dụng của tôi (giả sử 3.000), áp dụng thuật toán và chỉ trả lại 100 người dùng hàng đầu. Bằng cách này tôi đã nạp 2.900 đối tượng người dùng vô dụng từ DB và CPU bị lãng phí vào thuật toán mà không bao giờ làm bất cứ điều gì với nó.

Bất kỳ ý tưởng nào tôi có thể thiết kế điều này trong MySQL db hoặc ứng dụng web để người dùng có xếp hạng cá nhân với người dùng khác theo cách mà hệ thống vượt quá vài nghìn người dùng?

Answer 1

Nếu bạn phải đối sánh mọi người dùng với mọi người dùng khác, thuật toán là O (N^2), bất kể bạn làm gì.

Nếu bạn có thể khai thác một số loại "chỉ số" 1 chiều, thì bạn có thể thử và kết hợp từng người dùng với một giá trị tổng hợp duy nhất. Nhưng đó là khó xử và có thể là không thể.

Nhưng những gì bạn có thể làm là lưu ý người dùng nào yêu cầu thay đổi trong tiểu sử của họ (bất kỳ khi nào có thông số dựa trên kết hợp, thay đổi). Tại thời điểm đó bạn có thể tính toán lại bảng cho những người dùng đó, do đó làm việc trong O (N): nếu bạn có 10000 người dùng và chỉ cần 10 lần tính toán lại, bạn phải kiểm tra 100.000 bản ghi thay vì 100.000.000.

Các chiến lược khác sẽ chỉ chạy thuật toán chính cho các bản ghi có cơ hội được so sánh cao hơn: trong ví dụ của bạn, "cùng một thành phố". Hoặc khi cập nhật hồ sơ (nhưng điều này sẽ yêu cầu phải lưu trữ (user_1, user_2, ranking, last_calculated), chỉ tính toán lại các bản ghi đó với thứ hạng cao, rất cũ hoặc không bao giờ được tính toán. lên đầu trong một thời gian ngắn.

CẬP NHẬT

Vấn đề cũng đang hoạt động với O (N^2) không gian lưu trữ .

Làm cách nào để giảm không gian này? Tôi nghĩ tôi có thể thấy hai cách tiếp cận. Một là để không đặt một số thông tin trong bảng đối sánh ở tất cả. Hàm "match" làm cho ý nghĩa hơn, nó càng cứng và dốc; có mười nghìn "kết quả phù hợp" có nghĩa là khớp với có nghĩa là rất ít. Vì vậy, chúng tôi vẫn sẽ cần tính toán lại khi User1 thay đổi một số dữ liệu quan trọng, trong trường hợp nó mang lại một số kết quả "không có" của User1 trở lại vùng "có thể". Nhưng chúng tôi sẽ giữ một nhóm nhỏ các trận đấu hoạt động cho mỗi người dùng.

Bộ nhớ sẽ vẫn phát triển bậc hai, nhưng ít dốc hơn.

Một chiến lược khác sẽ là tính toán lại đối sánh và sau đó chúng tôi cần phát triển một số phương pháp để nhanh chóng chọn người dùng nào có khả năng có kết quả phù hợp (do đó hạn chế số hàng được truy lục bởi JOIN) và một số phương pháp để nhanh chóng tính toán một trận đấu; có thể đòi hỏi phải viết lại một cách nào đó kết hợp giữa User1 và User2 với một hàm rất đơn giản của một tập con của DataUser1, DataUser2 (có thể sử dụng các cột phụ trợ).

Thách thức sẽ là tận dụng khả năng của MySQL và giảm tải một số tính toán của công cụ MySQL.

Để đạt được mục đích này, bạn có thể "ánh xạ" một số dữ liệu, tại thời điểm nhập (do đó trong O (k)), thông tin không gian hoặc chuỗi và sử dụng khoảng cách Levenshtein.

Dung lượng lưu trữ cho một người dùng sẽ phát triển, nhưng nó sẽ phát triển tuyến tính, chứ không phải bậc hai và chỉ mục MySQL SPATIAL rất hiệu quả.

Answer 2

Tôi đồng ý với mọi thứ @Iserni nói.

Nếu bạn có ứng dụng web và người dùng cần "đăng nhập", thì bạn có thể có cơ hội tạo thứ hạng của người dùng đó vào thời điểm đó và thêm chúng vào bảng tạm thời (hoặc các hàng trong bảng hiện có).

Điều này sẽ hoạt động trong một khoảng thời gian hợp lý (vài giây) nếu tất cả dữ liệu cần thiết để tính toán phù hợp với bộ nhớ. Sau đó, công cụ cơ sở dữ liệu sẽ thực hiện quét toàn bộ bảng và tạo tất cả các xếp hạng.

Điều này sẽ hoạt động tốt một cách hợp lý cho một người dùng đăng nhập. Có thể là hai. . . nhưng nó sẽ không mở rộng rất tốt nếu bạn có, nói rằng, một tá người dùng đăng nhập trong vòng một giây.

Về cơ bản, mặc dù, xếp hạng của bạn không mở rộng tốt. Bạn phải so sánh tất cả người dùng với tất cả người dùng để nhận kết quả. Cho dù đây là lô (vào ban đêm) hoặc thời gian thực (khi ai đó có truy vấn) không thay đổi bản chất của vấn đề. Nó sẽ sử dụng rất nhiều tài nguyên máy tính và nhiều người dùng yêu cầu cùng một lúc sẽ là một nút cổ chai.

Answer 3

Nếu tìm kiếm chỉ trả về 100 kết quả phù hợp nhất, thì tại sao không chỉ lưu trữ những kết quả đó? Nghe có vẻ như bạn sẽ không bao giờ muốn tìm kiếm kết thúc dưới cùng của kết quả anyway, do đó, chỉ cần không tính toán chúng.

Bằng cách đó, dung lượng lưu trữ của bạn chỉ là o (n), chứ không phải là o (n^2) và bản cập nhật cũng phải như vậy.Nếu ai đó thực sự muốn xem các trận đấu qua 100 đầu tiên (và bạn muốn cho họ) thì bạn có tùy chọn chạy truy vấn trong thời gian thực tại thời điểm đó.