Have/Want列表匹配算法

你可以这样做 O(n*k^2) (n是人数,k是他们拥有/想要的物品的平均数量) 通过保留所有拥有和想要给定项的人的哈希表(或者,在数据库中,索引),然后为所有拥有当前用户想要的项的人和当前用户想要的项打分。显示前10或20个分数。

如何在SQL中实现此功能的示例:

-- Get score for @userid wants
SELECT UserHas.UserID, SUM(Items.Weight) AS Score
FROM UserWants
INNER JOIN UserHas ON UserWants.ItemID = UserHas.ItemID
INNER JOIN Items ON Items.ItemID = UserWants.ItemID
WHERE UserWants.UserID = @userid
GROUP BY UserWants.UserID, UserHas.UserID

这将根据当前用户想要的其他用户和他们的分数列表。对当前用户拥有其他人想要的项目执行相同的操作,然后以某种方式组合它们 抓住前10名。

这个问题看起来很像 stable roomamates problem . 我认为获得最高票数的SQL实现没有任何问题,但正如其他人所说,这就像一个约会/配对问题,类似于 stable marriage problem 但这里所有的参与者都在一个游泳池里。 第二个wikipedia条目还有一个链接,指向 javascript

您可以维护每项列表(作为每用户列表的补充)。项目搜索然后当场。现在你可以允许你的自我暴力搜索最有价值的配对检查最有价值的项目第一。如果您想要更复杂(可以说更快)的搜索,您可以引入一组经常作为元项组合在一起的项,并首先查找它们。

好吧,这个怎么样:

基本上有巨大的“水池”

每个“池”都包含“节”。每个“池”都专用于拥有特定项目的人。每个部分都是为拥有该项目并希望获得另一个项目的人提供的。

我的意思是:

A池(对于请求A的用户)

--B部分(对于有B的请求A的人)

--C部分(对于那些要求A而有C的人,即使他们也有B)

游泳池B

--剖面图A

--剖面图A

--截面图C

每个区都挤满了人。 “交易”将包括一个“请求的”项目,和一个“包”,你愿意提供任何或所有的项目,以获得您请求的项目。

每个“交易”都是按池计算的。。。。如果你想要一个给定的项目,你去你愿意提供的项目池,它会找到属于你请求的项目的部分。

同样地,你的交易也会被放入池中。因此,您可以立即找到所有适用的人员,因为您确切地知道要搜索哪些池和哪些部分,而无需在他们进入系统后进行排序。

然后,年龄会优先,老的交易会被挑选,而不是新的。

假设您可以对项目进行散列,或者至少对其进行排序。假设您的目标是根据请求为给定的用户找到最佳结果,如原始示例所示(优化贸易伙伴以实现整体贸易价值最大化是另一个问题。)

这会很快。O(logn)表示每个插入操作。建议交易伙伴的最坏情况是O(n),但处理时间限制了这一点。

1. 您已经为每个用户维护了一个项目列表。
2. 给每个用户一个等于他们拥有的项目值总和的分数。
3. 维护每个项目的用户拥有和用户想要的列表(@Dialecticus),按用户得分排序(您可以按需排序,也可以在用户每次更改列表时动态排序列表。)
4. 当用户 user1 建议贸易伙伴的请求
   • 迭代他们的项目 item 按价值排序。
   • 迭代用户拥有的 user2 项目 ,按用户得分排序。
   • 计算交易价值 user1 trades-with user2 .
   • 保留到目前为止已处理的用户哈希,以避免多次重新计算用户的值。

按项目值和用户分数排序是使此快速的近似值。不过,我不确定这会有多不理想。当然也有一些简单的例子,如果你不完成交易,就无法找到最好的交易。实际上,这似乎已经足够好了。在限制条件下,您可以让它运行,直到它耗尽步骤4.1和4.2中的列表。倒排列表会带来额外的内存开销,但你没有说你内存有限。一般来说,如果你想要速度的话,在空间上进行权衡是很常见的。

我用字母标记物品,用数字标记使用者。

• m
• x

1 - ABBCDE FFFGH
2 - CFGGH BE
3 - AEEGH BBDF

O(m*x*log(m/x)) + O(log(m)) 而且需要 O(x^2) 额外的记忆。这些值是:第一个用户将获得多少个值以及另一个用户将获得多少个值(如果需要,可以通过将这些值乘以特定项的值来修改这些值)。

1-2 : 1 - 3 (user 1 gets 1) - (user 2 gets 3)
1-3 : 3 - 2
2-3 : 1 - 1 

您还计算并存储每个用户的最佳交易者。生成这些有用的数据后,您可以快速查询。

• O(m*log(m/x)) (您循环浏览用户的have/want列表,对每个其他用户的have/want列表进行二进制搜索并实现数据)
• 寻找最佳连接- O(1) or O(x)

由 m/x 我估计单个用户想要/拥有列表中的项目数。

在这个算法中,我假设所有的数据都没有存储在数据库中(我不知道数据库是否可以进行二进制搜索),并且在列表中插入/删除项是可行的 O(1) .

对不起,我的英语不好,我希望我已经计算了所有正确的,这是工作,因为我也需要它。

假设User1现在想要H项。他只是在“Have”列表中搜索这个项目,在结果中,他发现User4将用项目H交换项目I,而User1恰好拥有这个项目。他们交易,一切都很好。