问题标签 [set-intersection]

在我正在开发的一个应用程序中，一个要求是进行大规模集合交集，大约 10-1,000,000 个项目。我们相交的项目只是 ObjectId 的。

因此，例如有一个 box 文档，并且在 boxes 文档内有一个 item_ids 数组。每个盒子的 item_ids 数组包含 10-1,000,000 个 ObjectId。

这里的最终目标是说，给定 ObjectId 为 4d3dc3898951498107000005 的框 A 和 ObjectId 为 4d3dc3898951498107000002 的框 B，它们有哪些共同的 item_id？

这是我的做法：

首先只是好奇这是否看起来是一种理智的方法。到目前为止，在我的研究中，似乎 map reduce 是大型交叉路口的常见建议，但不建议用于实时查询。

其次，好奇这在分片环境中会如何表现？mongos 会在它需要的 mongod 上运行大量查询并神奇地聚合我的结果吗？

最后，如果上述内容是理智的，那么这样做是否也是理智的：

这基本上是找到盒子 A 和盒子 B 有哪些共同点，然后在一个服务器端查询中将它们具体化为对象。这似乎也适用于 .limit 和 .skip 以有效地实现数据集的分页。

无论如何，任何反馈都是有价值的，谢谢！

我认为没有好的方法可以做到这一点，但是如果必须这样做，您将如何在 Appengine 的数据存储上实现集合操作？

例如，给定两个整数集合，您将如何将它们存储在数据存储中以获得相交和除外（A 中所有不在 B 中的所有项目）操作的良好性能？

我有一个有两个属性的类：

现在，我有一种方法可以找到这两组之间的交集。这是我在方法中写的：

它在 stl_algo.h 内编译时给我一个错误，但我不知道从哪里开始纠正错误

感谢您的时间

艾蒂安

很抱歉在 hadoop 用户邮件列表和此处交叉发布此内容，但这对我来说是个紧急问题。

我的问题如下：我有两个输入文件，我想确定

• a) 仅出现在文件 1 中的行数
• b) 仅在文件 2 中出现的行数
• c) 两者共有的行数（例如关于字符串相等性）

例子：

每种情况的所需输出：

基本上我的方法如下：我编写了自己的 LineRecordReader，以便映射器接收由行（文本）和指示源文件（0 或 1）的字节组成的对。映射器仅再次返回该对，因此实际上它什么也不做。然而，副作用是，组合器收到一个

（其中 SourceId 为 0 或 1）。

现在，对于每一行，我可以获得它出现的源集。因此，我可以编写一个组合器，计算每种情况（a、b、c）的行数（清单 1）

然后，组合器仅在清理时输出“摘要”（安全吗？）。所以这个总结看起来像：

然后，在减速器中，我只总结这些摘要的值。（因此reducer 的输出看起来就像combiner 的输出）。

但是，主要问题是，我需要将两个源文件视为一个单独的虚拟文件，该文件会产生格式为 (line, sourceId) // sourceId 0 或 1 的记录

我不确定如何实现这一目标。所以问题是我是否可以避免预先处理和合并文件，并使用虚拟合并文件阅读器和自定义记录阅读器之类的东西即时进行。非常感谢任何代码示例。

最好的问候，克劳斯

清单 1：

是否有一个函数接收一个列表x并返回一个y这样的列表y[[i]] = intersect(x[[1]][[i]], x[[2]][[i]], ...)？

如果没有，是否有一种 R 方法可以用几行代码对其进行编码？

有什么方法可以对两种不同类型的集合执行 std::set_intersection 吗？

我有两套：

我可以为它们定义一些比较器来检查 X1 和 X2 是否相等。

现在，我尝试在这两个集合上做一个集合交集：

不幸的是，我不能强迫这段代码工作。我什至不确定这是否可能，但从 set_intersection 的描述中我知道我可以使用两个不同的迭代器。

我试图搜索一些我想要的代码示例，但没有找到？有人可以为我的问题提供一个工作代码示例吗？

更新：错误是：

错误：stl_function.h:227: '__x < __y' 中的 'operator<' 不匹配

提前致谢！

我有一个包含 10K 记录的 XML 数据集，每个记录都包含一组字段。

我想知道与数据集匹配的数据库模式中哪些字段需要为空，哪些字段可以为非空。

linq 是否提供产生大交叉点的方法？

例子：

原型：

期望的结果：

考虑有一些整数列表：

问题是合并具有至少一个共同元素的列表。因此，仅给定部分的结果将如下所示：

对大数据（元素只是数字）执行此操作的最有效方法是什么？tree结构需要考虑吗 ？我现在通过将列表转换sets为交叉点并迭代交叉点来完成这项工作，但这很慢！此外，我有一种如此初级的感觉！此外，该实现缺少一些东西（未知），因为某些列表有时仍未合并！话虽如此，如果您提出自我实现，请慷慨并提供一个简单的示例代码 [显然Python是我最喜欢的 :)] 或伪代码。
更新 1： 这是我使用的代码：

功能是（越野车！！）：

结果是：

更新 2： 根据我的经验，下面Niklas Baumstark给出的代码对于简单的情况来说要快一些。尚未测试“Hooked”给出的方法，因为它是完全不同的方法（顺便说一句，看起来很有趣）。所有这些的测试程序可能真的很难或不可能确保结果。我将使用的真实数据集如此庞大和复杂，因此仅通过重复是不可能追踪任何错误的。也就是说，我需要对方法的可靠性 100% 满意，然后才能将其作为模块推送到大型代码中的位置。就目前而言 Niklas的方法更快，简单集合的答案当然是正确的。
但是，我如何确定它适用于真正的大型数据集？因为我将无法直观地跟踪错误！

更新 3： 请注意，对于这个问题，方法的可靠性比速度更重要。我希望最终能够将 Python 代码转换为 Fortran 以获得最大性能。

更新 4：
这篇文章有很多有趣的观点，并且慷慨地给出了答案，建设性的意见。我建议通读一遍。请接受我对问题的发展、惊人的答案以及建设性的评论和讨论的赞赏。

我有一个这样的代码片段，要在 VC++ 2010 下编译。

据我所知，这应该可行。但是，我得到构建错误：

为此，我做了明确的模板参数声明：

但我有同样的错误。我的问题是，在第二种情况下，如果我要传递一个 const_iterator，它应该会因为参数类型不匹配而在 const_iterator 和迭代器之间出现转换错误而失败。我在这里想念什么？（我知道 set_intersection 的“插入器”形式，但我想知道我在这里做错了什么）

以下代码的复杂度是多少？

其中S1和S2是一些非空集，并且ans是空集。

我知道将排序范围插入集合是线性的；但是也使用线性插入器插入吗？