标签: set-intersection

是否有接收列表的功能x,并返回一个列表y,以便y[[i]] = intersect(x[[1]][[i]], x[[2]][[i]], ...)？

如果没有,是否有R方式在几行中编码？

我有几百万套C的大集合.我的集合的元素来自大约2000个可能元素的宇宙.我需要知道,对于给定的集合,s,C中的集合与s的交集最大？(或者k在C中设置k个最大的交叉点).我将依次针对不同的s进行许多这些查询.

我知道这样做的显而易见的方法是循环遍历C中的每个集合并计算交集并取最大值.是否有任何智能数据结构/编程技巧可以加快我的搜索速度？如果我能比O(C)更快地做到这一点会很棒.

编辑:大致的答案也没关系

我遇到了一些特殊用途的集合操作实现,但对于一般情况没有任何用处.执行集合运算的一般情况是什么(特别是交集,并集,对称差异).这更容易理解在$ where或map reduce中使用javascript,但我想知道如何在聚合中执行此操作以获得本机性能.

说明这个问题的更好方法是举个例子.假设我有2个阵列/集的记录:

db.colors.insert({
    _id: 1,
    left : ['red', 'green'],
    right : ['green', 'blue']
});

我想找到'左'和'右'数组的并集,交集和差异.更好的是,我想要找到:

联盟 - > ['红色','绿色','蓝色']

交叉口 - > ['绿色']

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

我想知道使用lambda表达式是否可以解决这个问题:

List<Foo> listOne = service.GetListOne();
List<Foo> listTwo = service.GetListTwo();
List<Foo> result = new List<Foo>();

foreach(var one in listOne)
{
    foreach(var two in listTwo)
    {
        if((one.Id == two.Id) && one.someKey != two.someKey)
           result.Add(one);
    }
}

在C++中找到两个范围的交集的最佳方法是什么？例如,如果我有一个范围为[1 ... 20],包括[13 ... 45],则我想得到[13 ... 20],因为这是它们之间的交集.

我想过在C++中使用本机集合交集函数,但我首先要将范围转换为集合,这对于大值需要花费太多的计算时间.

我有一种感觉,我将被告知要去"初学者指南"或者你有什么但我在这里有这个代码

does = ['my','mother','told','me','to','choose','the']
it = ['my','mother','told','me','to','choose','the']
work = []

while 5 > len(work):
    for nope in it:
        if nope in does:
            work.append(nope)

print (work)

我明白了

['my', 'mother', 'told', 'me', 'to', 'choose', 'the']

为什么是这样？我怎么说服它回来呢

['my', 'mother', 'told', 'me']

我有一个集合std::set.我希望以最快的方式找到此集合中所有集合的交集.集合中的集合数量通常非常小(~5-10),每个集合中的元素数量通常小于1000,但偶尔可以达到10000左右.但我需要做几十个交叉点成千上万的时间,尽可能快.我试着对几个方法进行基准测试,如下所示:

1. std::set最初复制第一组的对象中的就地交叉.然后对于后续集合,它遍历其自身的所有元素和集合的第i组,并根据需要从其自身中移除项目.
2. 使用std::set_intersection临时std::set,将内容交换到当前集,然后再次找到当前集与下一集的交集并插入临时集,依此类推.
3. 手动迭代所有集合中的所有元素,如1),但使用a vector作为目标容器而不是std::set.
4. 与4相同,但使用a std::list而不是a vector,怀疑a list将提供从中间更快的删除.
5. 使用散列集(std::unordered_set)并检查所有集合中的所有项目.

事实证明,vector当每组中的元素数量较少时,使用a 略微更快,而list对于较大的集合,使用a 略微更快.就地使用set比两者都慢得多,其次是set_intersection哈希集.是否有更快的算法/数据结构/技巧来实现这一目标？如果需要,我可以发布代码片段.谢谢!

我一直在使用高度简洁和直观的C++语法来查找两个已排序的vectors并将结果放在第三个中vector:

vector<bar> a,b,c;
//...
std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                      std::back_inserter(c));

这应该设置c为交集(a,b),假设a和b排序.

但是,如果我只是使用c.begin()(我以为我在某个地方看到了一个例子,这就是我做的原因):

 std::set_intersection(a.begin(),a.end(),b.begin(),b.end(),
                       c.begin());

set_intersection期望OutputIteratorat参数.我认为标准只需要c.begin()返回a forward iterator,我想这可能是也可能不是OutputIterator.

无论如何,代码与c.begin()编译下铿锵.

保证在标准下发生什么？如果这编译,可能发生的事情 - 也就是说,当返回的迭代器c.begin()最终递增超过向量的末尾,并且尝试访问指向的元素时,必须/可能发生什么？在这种情况下,符合标准的实现是否可以无声地扩展向量,因此begin()实际上是一个OutputIterator类似的附加back_inserter？

我问这个主要是为了理解标准如何与迭代器一起工作:真正发生了什么,所以我可以使用STL超越复制和粘贴.

我有两个numpy整数数组,长度都是几亿.在每个数组中,值是唯一的,并且每个值最初都是未排序的.

我希望每个索引产生它们的排序交集.例如:

x = np.array([4, 1, 10, 5, 8, 13, 11])
y = np.array([20, 5, 4, 9, 11, 7, 25])

然后这些排序的交集是[4, 5, 11],所以我们想要将x和y中的每一个转换成该数组的索引,所以我们希望它返回:

mx = np.array([0, 3, 6])
my = np.array([2, 1, 4])

自那时候起 x[mx] == y[my] == np.intersect1d(x, y)

到目前为止,我们唯一的解决方案涉及三种不同的方法,因此似乎不太可能是最优的.

每个值代表一个星系,以防这个问题变得更有趣.

虽然在for循环中很容易实现,但在Java-8中是否有办法查找列表L中的所有元素是否都存在于Set中s？