我目前正在开发一个网站，用户可以在该网站上根据属性(年龄、高度、城镇、教育程度等)搜索其他用户。我现在想在用户配置文件之间实现某种评级。评级是通过其自己的算法根据 2 个给定配置文件之间的相似性计算得出的。例如，用户 A 与用户 B 的评级“匹配评级”为 85，与用户 C 的评级“匹配评级”为 79。 B 和 C 的评级为 94 等等....
用户应该能够搜索某些属性并按评级过滤结果。
由于评级因个人资料而异，而且还取决于进行搜索的用户，我不能简单地向我的用户表添加一个字段并使用 ORDER BY。到目前为止，我提出了 2 个解决方案:
我的第一个解决方案是每晚执行一次批处理作业，计算每个可能的用户组合的评分并将其存储在单独的表中(user1、user2、评分)。然后，我可以将此表与用户表连接起来，并按评分对结果进行排序。在做了一些数学运算后，我发现这个解决方案的扩展性不佳。
根据公式 n * (n - 1)/2，10 个用户有 45 种可能的组合。对于 1.000 个用户，我突然不得不在我的评分表中插入 499.500 个评分组合。
第二个解决方案是保留 MySQL，只在我的应用程序中即时计算评分。这也不能很好地扩展。假设搜索应该只向 UI 返回 100 个结果(评分最高的在最上面)。如果我有 10.000 个用户，并且我想搜索居住在纽约的每个用户(按评级排序)，我必须将居住在纽约的每个用户加载到我的应用程序中(假设是 3.000)，应用算法然后只返回前 100 名的用户。通过这种方式，我从数据库中加载了 2.900 个无用的用户对象，并在算法上浪费了 CPU，而没有对它做任何事情。
有什么想法可以在我的 MySQL 数据库或 Web 应用程序中设计它，以便用户可以对每个其他用户进行单独评级，从而使系统扩展到超过几千个用户？
最佳答案
如果您必须将每个用户与其他每个用户进行匹配，无论您做什么，算法都是 O(N^2)。
如果您可以利用某种一维“指标”，那么您可以尝试将每个用户与一个合成值相关联。但这很尴尬，而且可能是不可能的。
但您可以做的是记录哪些用户需要更改他们的配置文件(每当匹配所基于的任何参数发生更改时)。届时，您可以仅为这些用户批量重新计算表，从而在 O(N) 中工作:如果您有 10000 个用户并且只有 10 个需要重新计算，则您必须检查 100,000 条记录而不是 100,000,000。
其他策略是只对更有可能被比较的记录运行主要算法:在您的示例中，“同城”。或者在更新记录时(但这需要存储(user_1、user_2、ranking、last_calculated))，只重新计算那些排名高、非常旧或从未计算过的记录。排名最低的匹配不太可能发生太大变化以至于它们 float 在短时间内达到顶峰。
更新
问题还在于操作 O(N^2) 存储空间。
如何减少这个空间？我想我可以看到两种方法。一种是根本不将某些信息放入匹配表中。 “匹配”功能使它越僵硬和陡峭越有意义；有一万个“好匹配”意味着匹配意义不大。因此，当 User1 更改某些关键数据时，我们仍然需要进行大量重新计算，以防将 User1 的一些“不-不”匹配项带回“可能”区域。但是我们会为每个用户保留一个较小的事件匹配组。
存储量仍将以二次方增长，但不会那么陡峭。
另一种策略是重新计算匹配，然后我们需要开发一些方法来快速选择哪些用户可能具有良好的匹配(从而限制检索的行数JOIN)，以及一些快速计算匹配的方法；这可能需要以某种方式将 User1 和 User2 之间的匹配重写为 DataUser1、DataUser2 的一个非常简单的子集函数(可能使用辅助列)。
挑战在于利用 MySQL 功能并卸载 MySQL 引擎的一些计算。
为此，您可能会在输入时间(因此在 O(k) 中)将一些数据“映射”到空间信息或字符串并使用 Levenshtein 距离。
单个用户的存储会增长，但会线性增长，而不是二次增长，而且 MySQL SPATIAL 索引非常高效。
关于n * (n - 1)/2 算法的 MySQL 架构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/12679977/