Thuật toán tìm bạn chung giữa hai người như Facebook

Nội dung bài viết

Sử dụng Mongodb giải quyết một thuật toán giống như facebook đó là tìm bạn chung giữa hai Users. Dưới đây là một ví dụ và cách giải quyết bài toán sử dụng Mongodb giải quyết vấn đề này.


Tìm bạn chung giữa hai Users như Facebook với mongodb


Dưới đây là một Collections Friends trong đó chứa _idUserId, và friends đó là tập hợp những Id bạn bè tương ứng với _id đó.


> db.friends.find()
{ "_id" : 1, "friends" : [    2, 3, 4    ] }
{ "_id" : 2, "friends" : [ 1,    3,    5 ] }
{ "_id" : 3, "friends" : [ 1, 2,    4, 5 ] }
{ "_id" : 4, "friends" : [ 1,    3,    5 ] }
{ "_id" : 5, "friends" : [    2, 3, 4    ] }

Dưới đây là một số cách khi làm việc với Mongodb

// 1 and 2 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [1,2]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 3 } ], "ok" : 1 }

// 1 and 3 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [1,3]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 4 }, { "_id" : 2 } ], "ok" : 1 }

// 1 and 4 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [1,4]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 3 } ], "ok" : 1 }

// 1 and 5 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [1, 5]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 4 }, { "_id" : 3 }, { "_id" : 2 } ], "ok" : 1 }

// 2 and 4 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [2, 4]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 5 }, { "_id" : 3 }, { "_id" : 1 } ], "ok" : 1 }

// 1, 2 and 3 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [1,2,3]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 3}}, {$project: {_id: 1}}])
{ "result" : [ ], "ok" : 1 }  // have no friends in common.

// 1, 2 and 4 mutual friends:
> db.friends.aggregate([{$match: {_id: {$in: [1,2,4]}}}, {$unwind: "$friends"}, {$group: {_id: "$friends", count: {$sum: 1}}}, {$match: {count: 3}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 3 } ], "ok" : 1 } // have one friend in common: user 3

Hoặc nếu bạn có thể lưu một dạng khác tuỳ thuộc vào dự án mà chúng ta đang triển khai.

> db.friendships.insert([
	{ "_id" : "1|2", "u" : [1, 2] },
	{ "_id" : "1|3", "u" : [1, 3] },
	{ "_id" : "1|4", "u" : [1, 4] },

//{ "_id" : "1|2", "u" : [2, 1] }, // omit -- id exists above
	{ "_id" : "2|3", "u" : [2, 3] },
	{ "_id" : "2|5", "u" : [2, 5] },

//{ "_id" : "1|3", "u" : [3, 1] }, // omit -- id exists above
//{ "_id" : "2|3", "u" : [3, 2] }, // omit -- id exists above
	{ "_id" : "3|4", "u" : [3, 4] },
	{ "_id" : "3|5", "u" : [3, 5] },

//{ "_id" : "1|4", "u" : [4, 1] }, // omit -- id exists above
//{ "_id" : "3|4", "u" : [4, 3] }, // omit -- id exists above
	{ "_id" : "4|5", "u" : [4, 5] },

//{ "_id" : "2|5", "u" : [5, 2] }, // omit -- id exists above
//{ "_id" : "3|5", "u" : [5, 3] }, // omit -- id exists above
//{ "_id" : "4|4", "u" : [5, 4] }, // omit -- id exists above
])

Sử dụng cách dưới đây, sẽ có những kết quả như trên.

//# 1 and 2 mutual friends:
> db.friendships.aggregate([{$match: {u: {$in: [1,2]}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: [1,2]}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 3 } ], "ok" : 1 }

//# 1 and 3 mutual friends:
> db.friendships.aggregate([{$match: {u: {$in: [1,3]}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: [1,3]}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 4 }, { "_id" : 2 } ], "ok" : 1 }

//# 1 and 4 mutual friends:
> db.friendships.aggregate([{$match: {u: {$in: [1,4]}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: [1,4]}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 3 } ], "ok" : 1 }

//# 1 and 5 mutual friends:
> db.friendships.aggregate([{$match: {u: {$in: [1,5]}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: [1,5]}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 4 }, { "_id" : 3 }, { "_id" : 2 } ], "ok" : 1 }

//# 2 and 4 mutual friends:
> db.friendships.aggregate([{$match: {u: {$in: [2,4]}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: [2,4]}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: 2}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 5 }, { "_id" : 3 }, { "_id" : 1 } ], "ok" : 1 }

//# 1, 2 and 3 mutual friends:
> users = [1,2,3]
> db.friendships.aggregate([{$match: {u: {$in: users}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: users}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: users.length}}, {$project: {_id: 1}}])
{ "result" : [ ], "ok" : 1 }

//# 1, 2 and 4 mutual friends:
> users = [1,2,4]
> db.friendships.aggregate([{$match: {u: {$in: users}}}, {$project: {_id: 0, u: 1}}, {$unwind: "$u"}, {$match: {u: {$nin: users}}}, {$group: {_id: "$u", count: {$sum: 1}}}, {$match: {count: users.length}}, {$project: {_id: 1}}])
{ "result" : [ { "_id" : 3 } ], "ok" : 1 }

Bạn có thể join vào group Mongodb Việt Nam tại đây

Source Code: GITHUB 


Có thể bạn đã bị missing