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

Question

我在约会应用程序中有数以万计的用户数据。每个用户有 5 个不重叠的爱好。需要将爱好最相近的情侣联系起来列出来

例子

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

用户 2：{ 姓名：山姆爱好：["E"、"B"、"C"、"Z"、"H"] }

用户 3：{ 姓名：山姆爱好：["A"、"B"、"C"、"E"、"J"] }

结果：用户 1 - 用户 3

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

我想知道一些算法或提示

Answer 1

创造 table hobby 的爱好

所以创建一个列表，包含您在数据中获得的所有不同爱好。
将您的数据中的爱好字符串转换为数字

只需获取每个爱好字符串并在您的新 hobby table 中查找它。当找到 index 时，您找到的就是您要查找的号码。如果未找到，请将新条目添加到 hobby 并使用其 index.

步骤 #1 和步骤 #2 可以一起完成。它们可能会通过散列和按散列进行索引排序来加速。
爱好暴力检查

现在执行 2 个嵌套 for 循环来检查数据中的每个条目，例如：
```
for (i=0;i<entries-1;i++)
 for (j=i+1;j<entries;j++)
  ...
```
里面数一数相同的数（爱好）。所以再次 2 for 循环但计数到 5 而不是 entries.

Answer 2

首先观察如果总的不同爱好适合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

然后，user-1和user-2之间的总匹配爱好可以简单地在这两个整数进行按位与运算得到的整数中找到总共一位。

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 处理器指令来计算 1 位的数量（Link）。

为了找到最匹配的分数，我们可以简单地迭代每对用户并通过简单地在两个数字的按位 AND 中找到总 1 位并最大化该分数来计算匹配的爱好。现在，为了找到最匹配对的列表，我们可以执行相同的操作并与最匹配的分数进行比较并将它们放入我们的列表中。

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

What algorithm should be used when matching hobby?

sorting

algorithm

matching

string-matching