7

我目前正在开发一个网站，用户可以在其中根据属性（年龄、身高、城镇、教育等）搜索其他用户。我现在想在用户配置文件之间实现某种评级。评级是通过其自己的算法根据 2 个给定配置文件之间的相似性计算的。例如，用户 A 对用户 B 的评级“匹配评级”为 85，对用户 C 的评级“匹配评级”为 79。B 和 C 的评分为 94，依此类推....

用户应该能够搜索某些属性并按评级过滤结果。

由于评级因个人资料而异，而且还取决于进行搜索的用户，所以我不能简单地在我的用户表中添加一个字段并使用 ORDER BY。到目前为止，我想出了2个解决方案：

  • 我的第一个解决方案是每晚进行一次批处理作业，计算每个可能的用户组合的评分并将其存储在单独的表中（user1、user2、rating）。然后我可以将此表与用户表连接起来，并按评级对结果进行排序。在做了一些数学运算后，我发现这个解决方案不能很好地扩展。

    根据公式 n * (n - 1) / 2，10 个用户有 45 种可能的组合。对于 1.000 个用户，我突然不得不在我的评分表中插入 499.500 个评分组合。

  • 第二种解决方案是让 MySQL 保持不变，并在我的应用程序中即时计算评级。这也不能很好地扩展。假设搜索应该只向 UI 返回 100 个结果（最高评分在顶部）。如果我有 10.000 个用户，并且我想搜索居住在纽约的每个用户（按评分排序），我必须将居住在纽约的每个用户加载到我的应用程序中（比如说 3.000），应用算法然后只返回前 100 名给用户。通过这种方式，我从数据库中加载了 2.900 个无用的用户对象，并在算法上浪费了 CPU，而没有对其进行任何操作。

有什么想法可以在我的 MySQL 数据库或 Web 应用程序中进行设计，以便用户可以与其他每个用户进行单独评分，从而使系统扩展到几千个用户之外？

4

3 回答 3

3

如果您必须将每个用户与其他每个用户进行匹配，那么无论您做什么，算法都是 O(N^2)。

如果您可以利用某种一维“指标”，那么您可以尝试将每个用户与单个合成值相关联。但这很尴尬，而且可能是不可能的。

但是您可以做的是注意哪些用户需要更改他们的配置文件（只要匹配所基于的任何参数发生更改）。此时，您可以只为这些用户批量重新计算表，从而在 O(N) 中工作：如果您有 10000 个用户并且只有 10 个需要重新计算，则您必须检查 100,000 条记录而不是 100,000,000 条记录。

其他策略是只对比较有可能被比较的记录运行主要算法：在你的例子中，“同一个城市”。或者在更新记录时（但这需要存储（user_1，user_2，ranking，last_calculated），只重新计算那些排名高、非常旧或从未计算过的记录。排名最低的匹配不太可能改变太多以至于它们浮动短时间内登上顶峰。

更新

问题还在于 O(N^2)存储空间。

如何减少这个空间？我想我可以看到两种方法。一是根本不把一些信息放在匹配表中。“匹配”功能越是刚性和陡峭越有意义；一万个“好的匹配”意味着匹配的意义很小。因此，当 User1 更改一些关键数据时，我们仍然需要重新计算大量数据，以防它将 User1 的一些“no-no”匹配带回“maybe”区域。但是我们会为每个用户保留一个较小的活跃匹配集团。

存储量仍将呈二次方增长，但不那么陡峭。

另一种策略是重新计算匹配，然后我们需要开发一些方法来快速选择哪些用户可能有很好的匹配（从而限制 JOIN 检索的行数），以及一些快速计算的方法匹配; 这可能需要以某种方式将 User1 和 User2 之间的匹配重写为 DataUser1 的子集 DataUser2 的一个非常简单的函数（可能使用辅助列）。

挑战将是利用 MySQL 功能并将一些计算卸载到 MySQL 引擎。

为此，您可能会在输入时间（因此在 O(k) 中）将一些数据“映射”到空间信息或字符串并使用 Levenshtein 距离。

单个用户的存储会增长，但会线性增长，而不是二次增长，而且 MySQLSPATIAL索引非常有效。

于 2012-10-01T20:08:16.900 回答
2

如果搜索应该只返回前 100 个最佳匹配项，那么为什么不直接存储它们呢？听起来您无论如何都不想搜索结果的底端，所以不要计算它们。

这样，你的存储空间只有 o(n)，而不是 o(n^2)，更新也应该是。如果有人真的想查看前 100 个之后的匹配项（并且您想让它们），那么您可以选择在该点实时运行查询。

于 2012-10-01T20:31:37.857 回答
0

我同意@Iserni 所说的一切。

如果您有一个网络应用程序并且用户需要“登录”，那么您可能有机会创建该用户当时的排名并将它们存储到临时表（或现有表中的行）中。

如果计算所需的所有数据都放入内存，这将在合理的时间内（几秒钟）起作用。然后数据库引擎应该进行全表扫描并创建所有评级。

对于一个登录的用户来说，这应该可以很好地工作。对于两个 . . . 但是如果你有一打用户在一秒钟内登录，它就不会很好地扩展。

但是，从根本上说，您的评级并不能很好地衡量。您必须将所有用户与所有用户进行比较才能获得结果。无论是批处理（夜间）还是实时（当有人查询时）都不会改变问题的性质。它会占用大量的计算资源，多个用户同时发出请求会成为瓶颈。

于 2012-10-01T20:29:25.273 回答