问题标签 [set-intersection]

给定一个 Map[String, Set[String]] 在 Scala 中，确定所有不同键对的集合，其中相应集合具有非空交集，什么是优雅而有效的方法？

例如将地图固定为

那么所需的输出是

在这种情况下，高效意味着比 O(n^2) 更好，其中 n 是作为输入给出的集合族中元素数量的总和。

我正在尝试使用 Mongo 聚合框架来查找在同一文档中具有不同唯一集的记录。一个例子将最好地解释这一点：

这是一个不是我真实数据的文档，但在概念上是相同的：

请注意，有两个具有相似项目的层次结构。也可以使用不属于自己的物品。我想找到像这样的文件：那里有一所房子使用了它不拥有的东西。

到目前为止，我已经使用如下聚合框架构建了结构。这让我得到了两组不同的项目。但是，我找不到任何可以给我设置交集结果的东西。请注意，由于以下情况，简单的设置大小计数将不起作用：['couch', 'cabinet'] 与 ['sofa', 'cabinet'] 相比。

产生：

那么我如何在流水线的下一阶段找到集合的使用和拥有的交集？

我遇到了一些特殊目的的集合操作实现，但一般情况下没有。执行集合操作的一般情况是什么（特别是交集、联合、对称差）。这更容易在 $where 或 map reduce 中使用 javascript，但我想知道如何在聚合中执行此操作以获得本机性能。

说明这个问题的更好方法是举个例子。假设我有 2 个数组/集的记录：

我想找到“左”和“右”数组的并集、交集和差异。更好的是，我想从图形上找到：

联合--> ['red', 'green', 'blue']

交叉口--> ['green']

对称差--> ['red', 'blue']

我找到了两种方法来获取共享一个列值的每条记录，其中一些不同的记录集由一组 WHERE 条件标识。（示例查询非常清晰......）

你知道第三种更合成的方式吗？也许使用分析功能？

考虑以下示例：

为什么 idx 的大小与 time 的大小不同？我会认为这些在长度上应该是相同的，因为时间只是 Jday 的一部分。有任何想法吗？

嗨，所以很难在标题中正确解释这一点，但首先让我从解释我的数据开始。我在一个列表中存储了 40 个列表，其形式如下：

现在我期待这样的输出：

我知道这读起来有点复杂，但我想确保有一个很好的数据演示。因此，基本上所有列表都需要具有所有列表中存在的值的所有可能组合，如果该组合不作为标准存在于该列表中，则其频率（第二个字段）为 0。

感谢您的帮助，请记住这是 40 个不同列表的交集，因此需要快速高效。我不确定如何最好地做到这一点......

编辑：我也不知道所有的“值”，为了简单起见，我刚刚在这里写了 3 个不同的值（value1、value2、value3）。在我的项目中，我不知道值是什么或有多少不同的值（我知道至少有几千个）

编辑2：这是一些真实的输入数据，我没有真实的输出数据，但我会尝试解决：

当可能存在重复时，我想在两个 [列表、向量、序列] 中找到共同的元素。

这是我目前拥有的：

我使用4clojure的经验告诉我，我很少编写最惯用或最简洁的代码，所以我很想知道是否有更好的方法来做到这一点。

我有 n 个不同长度的单元向量，称之为c{i}, i=1,2,...,n。

我想知道是否有c{j}的子集c{i}，例如：

那么我希望我能找到那c{4}是 的子集c{1}，c{5}是 的子集c{2}。

我用了两个for循环和intersect函数可以处理，但我希望我最多可以用一个循环来处理它，有什么办法可以实现吗？

假设支持 O(n) 迭代和 O(log n) 访问单个项目的有序集合，集合并集、集合交集和集合差的理论上最优复杂度是多少？假设可以对集合使用专用结构，只要结果与输入的类型相同。

编辑：

令 n 为较大集合的大小，m 为较小集合的大小，d 为对称差的大小。

本文描述了一种算法。它以 O(m*log(n/m)) 运行，据称是最佳的。然后在本文中对该算法进行了修改，使其也变为 O(d*log(n/d))。

可以改进最优算法是否矛盾？我猜不是因为 d 是一个新参数，所以 O(m*log(n/m)) 相对于 n 和 m 仍然是最优的。但这是结束还是可能有多快？

我正在寻找一种有效的方法来做到这一点。假设我有两个带有对象点的数组。

我想要的是在不使用 java.util.* 的情况下在两个数组中获取相互的东西

例如

我想得到一个新的数组 a3 是

让我困惑的是，我不知道 a3 会持续多久。所以我是否必须遍历 a1、a2 来计算那里有多少相互项目，以及

然后再次循环a1，a2并将项目放入？？这看起来效率很低。有没有更优雅的方法来做到这一点，因为这可能会一直出现。