匹配爱好时应该用什么算法？

Question

我在交友APP里有几万个用户数据，每个用户都有5个不重叠的爱好.需要通过连接爱好最匹配的情侣来列出他们的数据。每个用户有5个不重叠的爱好.需要通过连接爱好最匹配的情侣来列出他们。

例如

用户1：{姓名：sam爱好：["A"、"B"、"C"、"E"、"H"]}。["A"、"B"、"C"、"E"、"H"]}。

user2: { name: sam hobbies: ["E", "B", "C", "Z", "H"]}。

user3: { name: sam hobbies: ["A"、"B"、"C"、"E"、"J"]}。

结果:user1 - user3

如果用户1,用户2,用户3爱好相同，结果是用户1-用户2,用户1-用户3,用户2-用户3。

我想知道一些算法或提示。

Answer 1

首先观察到的是，如果所有不同的爱好都符合64位整数范围，那么我们可以将每个用户数据存储为一个整数，其二进制表示代表一个爱好。比如说

0th bit -> hobby A
1st bit -> hobby B
2nd bit -> hobby C
and so on ...

如果用户1的爱好是["A", "B", "C", "E", "H"], 那么它的二进制表示就是:

           H  E CBA
           10010111
Integer =  151

如果用户2有爱好["A""B""C""E""J"]那么它的二进制表示就是：

           J    E CBA
           1000010111
Integer =  535

那么，用户-1和用户-2之间的总匹配爱好就可以得到，只需找到这两个整数的位与位运算得到的整数中的1位。

Bitwise AND of (151 & 535) = 23 (10111) which has 4 ones in binary representation.

      151 = 0010010111
      535 = 1000010111
----------------------
and_a_b   = 0000010111

Basically, Bitwise AND will keep 1 bit only if both bit position are 1s.
Here, total hobbies match is = 4 which is total 1 bits in and_a_b.

在c++中，我们可以简单地应用以下方法获得这个值 __builtin_popcount(and_a_b).在现代硬件上，我们可以在现代的时间内不断地得到这些信息，因为它提供了POPCNT处理器指令来计算1s位数(链接).

为了找到最匹配的分数，我们可以简单地对每一对用户进行迭代，并计算出匹配的爱好，只需在两个数字的位与位之间找到总的1s位，并使该分数最大化。现在，为了找到最匹配的用户对列表，我们可以执行同样的操作，并与最匹配的分数进行比较，然后将它们放入我们的列表中。

Answer 2

1. 创建表格 hobby 嗜好

   因此，创建一个所有 鲜明 您的数据中的爱好。

2. 将您数据中的兴趣爱好字符串转换为数字。

   只需将每个爱好的字符串，在你的新。hobby 表。当发现 index 你找到的是你要找的号码。如果没有找到，请添加新条目到 hobby 并利用其 index.

   步骤#1和#2可以一起完成。它们可能会通过散列和通过散列的索引排序来加快速度。

3. 粗暴地检查兴趣爱好

   现在做2个嵌套for循环来检查每个条目和数据中的其他条目，比如。

   for (i=0;i<entries-1;i++)
    for (j=i+1;j<entries;j++)
     ...
   

   然后在里面计算相同数字的数量（兴趣爱好）。所以同样是2个for循环，但计数到 5 而不是高达 entries.