Thuật toán xử lý tìm bạn quanh đây tối ưu

Thuật toán xử lý tìm bạn quanh đây tối ưu

Tính năng tìm bạn quanh đây là một trong những tính năng rất phổ biến trong các ứng dụng chat, làm quen, hẹn hò. Thuật toán xử lý dường như không quá khó chỉ cần tính khoảng cách theo vị trí để tìm ra những người gần nhất. Tuy nhiên với một số lượng người dùng rất lớn thì quá trình này sẽ gặp rất nhiều vấn đề.

Đương nhiên để tìm những người ở gần bạn nhất thì trong cơ sở dữ liệu đã có sẵn thông tin về vị trí của tất cả mọi người, thường được đại diện bằng 2 tham số là longitude và latitude. Giờ chúng ta sẽ đi tìm giải thuật, thử xem nó khó cỡ nào nào.

I. Thuật toán vét cạn

Tư tưởng rất đơn giản, để tìm được những người gần tôi nhất, tôi cần

  • Lấy danh sách tất cả người trên map
  • Tính khoảng cách từ tôi đến tất cả người này
  • Sắp xếp theo khoảng cách tăng dần
  • Chọn k người ở gần
    Để tính khoảng cách thì thông thường chúng ta dùng công thức tính đường chéo của tam giác vuông. Cái này hồi đi học làm nhiều lắm rồi nè.

Tìm quanh đây 1

d = √((x1-x2)² + (y1-y2)²)

Tuy nhiên, để ý là chúng ta không cần thiết phải tính hẳn khoảng cách mà chỉ muốn so sánh 2 khoảng cách từ điểm 1 đến 2 và từ 2 đến 3. Do đó chúng ta có thể bỏ phép khai căn đi, chỉ cần tính tổng 2 bình phương là được. Việc bỏ qua phép khai căn sẽ giúp thuật toán chạy nhanh hơn.

d12 > d23 ((x1-x2)² + (y1-y2)²) > ((x3-x2)² + (y3-y2)²)

tìm quanh đây 2

Thuật toán này chỉ có thể áp dụng cho quy mô nhỏ, khi số lượng user vượt 1000 thì bạn nên dùng cách khác do tốc độ chạy thuật toán sẽ chậm đi thấy rõ.

II. Tìm gần đúng

Nếu bạn đã tìm hiểu nhiều về các thuật toán khi áp dụng vào thực tế, bạn sẽ biết một quy tắc đó là “Thà chọn cách giải gần đúng mà thời gian thực hiện nhanh còn hơn cách giải chính xác mà thời gian lâu”. Bạn có thể dễ thấy điều này khi sử dụng Google Map, nếu bạn chọn tìm đường giữa 2 điểm gần nhau, nó sẽ chỉ cho bạn cả những con đường ngách rất nhỏ, giúp bạn đi nhanh. Nhưng nếu 2 địa điểm xa nhau, nó sẽ chỉ cho bạn đi đường lớn do nó loại bớt những đường nhánh nhỏ để tăng tốc độ tìm đường. Kết quả, con đường tìm thấy không phải là con đường ngắn nhất 100%, nhưng là kết quả “chấp nhận được”.

Vậy trong bài toán tìm người ở gần của chúng ta thì sẽ áp dụng quy tắc “tìm gần đúng” như thế nào. Rõ ràng thuật toán “Vét cạn” là thuật toán tìm chính xác — aka Chậm. Để cải tiến nó, chúng ta chỉ cần biến đổi đi một tí, thay vì tìm những người ở gần nhất, chúng ta sẽ chỉ tìm những người trong phạm vi bán kính x km.

Tìm quanh đây 3

Tuy nhiên, nếu tính bán kính hình tròn như bình thường, chúng ta sẽ không có cách lưu trữ dữ liệu phù hợp. Do đó, chúng ta lại biến đổi một tí, thay vì lấy theo bán kính hình tròn, chúng ta sẽ lấy theo hình vuông như sau.

Tìm quanh đây 4

Nếu lấy theo hình vuông như vậy thì sẽ lọt thêm một vài đối tượng đáng nhẽ không đủ tiêu chuẩn nhưng vẫn được lấy thêm vào. Nhưng thế thì có sao đâu, càng thích ấy chứ 😛
Đến đây thì dễ rồi, giả sử vị trí hiện tại của bạn là (x1, y1), bạn chỉ cần query database lấy những người có nằm trong hình vuông là ra.

(x1-r

Cách query này hoàn toàn có thể đánh chỉ mục được và chạy nhanh như một cơn gió dù dữ liệu có lớn đi nữa.

III. Tìm theo địa phương

Cách tìm gần đúng ở trên vẫn còn một nhược điểm. Giả sử như bạn đang ở một vùng hoang vắng, xung quanh ít bạn nữ. Bạn mở ứng dụng lên và quét 5km – không thấy ai, 10km – ko thấy ai. Nếu mỗi lần không tìm thấy user nào, bạn lại tăng bán kính lên thì bạn phải query rất nhiều lần để tìm được những người ở gần. Vậy giờ phải làm sao ?

Thử để ý Grab, trước khi chúng ta đặt xe, chúng ta thường thấy nhiều xe xung quanh chỗ chúng ta đứng. Tuy nhiên, cuối cùng khi tìm được xe thì lại thấy xe này ở cách chúng ta xa hơn những xe khác. Tức là thuật toán của họ không phải luôn luôn chọn xe ở gần nhất, mà còn phụ thuộc nhiều yếu tố, VD ưu tiên xe chưa chạy được cuốc nào, ưu tiên xe có nhiều đánh giá tốt hơn..

Chúng ta thử tìm cách giải cho bài toán này. Thông thường những người ở gần sẽ cùng 1 đơn vị hành chính, VD phường, xã, thành phố, tỉnh, quốc gia. Vậy đơn giản rồi, bên cạnh việc lưu thông tin về tọa độ của user, bạn sẽ lưu thêm thông tin địa chỉ ứng với địa điểm đó. Mình dùng thư viện này https://www.npmjs.com/package/react-native-geocoding , nó có sẵn hàm chuyển từ tọa độ sang đơn vị hành chính ( địa chỉ ). Chúng ta sẽ tổ chức dữ liệu như sau :

`coordinate

  • longitude
  • latitude
  • address
    • country: “vn”
    • city: “hanoi”
    • district: “hoankiem”`

Giờ query chúng ta sẽ tìm những người trong cùng 1 quận trước, nếu ko có thì tìm những người cùng thành phố, ko có nữa thì cùng nước, mà ko có nữa thì chắc tìm trong hệ mặt trời quá. Sau khi có danh sách những người ở gần, chúng ta sẽ có 1 danh sách không quá lớn những ứng viên tiềm năng. Từ đây, chúng ta chạy tiếp các hàm đánh giá để lựa chọn ứng viên phù hợp nhất.

Cách làm này đương nhiên không đúng với bài toán gốc là tìm những người ở gần mình nhất. Nhưng nếu bạn đang xây dựng một app hẹn hò thì đây là cách “chấp nhận được” vì nó giảm chi phí query dữ liệu, đồng thời chính nhờ tính “gần đúng” mà bạn sẽ chọn được những đối tượng đa dạng hơn, mang tính ngẫu nhiên cao hơn.

Tóm lại, trong bất kỳ vấn đề nào trong cuộc sống, đừng quá cứng nhắc phải giải quyết đúng 100% yêu cầu bài toán đặt ra. Mà hãy có sự linh động, và sự thương lượng, cân bằng giữa nhiều yếu tố. Chọn bạn gái cũng vậy nhé — Đôi khi cách giải gần đúng lại còn hay hơn cách giải đúng 😉

Tác giả: Nghiêm Tiến Viễn

admin

Leave a Reply

Your email address will not be published. Required fields are marked *