blocks|key|769443|text|可以轻松地将集合的成员映射到相对较小的整数范围内吗？如果是这样，请考虑使用BitSets。交集就是按位的，一次-+32个潜在成员。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|769444|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Can the members of the sets be easily mapped into a relatively small range of integers? If so, consider using BitSets. Intersection then is just bitwise and's - 32 potential members at a time.

blocks|key|552869|text|只需使用Google+Guava的Sets#intersection(Set,+Set)方法即可。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|552870|entityMap|0|LINK|mutability|MUTABLE|url|https://github.com/google/guava|1|https://github.com/google/guava/blob/bdaa4683401dbe9c05e16e6cd2b1ba3caba7c961/guava/src/com/google/common/collect/Sets.java#L824^0|H|R|4|C|0|H|R|1|0^^$0|@$1|2|3|4|5|6|7|P|8|@$9|Q|A|R|B|C]]|D|@$9|S|A|T|1|U]|$9|V|A|W|1|X]]|E|$]]|$1|F|3|-4|5|6|7|Y|8|@]|D|@]|E|$]]]|G|$H|$5|I|J|K|E|$L|M]]|N|$5|I|J|K|E|$L|O]]]]

Just use <a href="https://github.com/google/guava" rel="nofollow noreferrer">Google Guava</a>'s <a href="https://github.com/google/guava/blob/bdaa4683401dbe9c05e16e6cd2b1ba3caba7c961/guava/src/com/google/common/collect/Sets.java#L824" rel="nofollow noreferrer"><code>Sets#intersection(Set, Set)</code></a> method.

blocks|key|552909|text|这是一个很好的方法。您应该可以从当前解决方案中获得O(n)性能。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|552910|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

That is a good approach. You should be getting O(n) performance from your current solution.

blocks|key|769596|text|如果两个集合都可以排序，就像TreeSet一样，运行两个迭代器可以更快地计算共享对象的数量。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|769597|如果您经常执行此操作，如果您可以包装这些集合，以便可以缓存交集操作的结果，则可能会带来很多问题，保留dirty标志以跟踪缓存结果的有效性，并在需要时重新计算。|769598|entityMap^0|E|7|0|1E|5|0^^$0|@$1|2|3|4|5|6|7|J|8|@$9|K|A|L|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|M|8|@$9|N|A|O|B|C]]|D|@]|E|$]]|$1|H|3|-4|5|6|7|P|8|@]|D|@]|E|$]]]|I|$]]

If both sets can be sorted, like <code>TreeSet</code> running both iterators could be a faster way to count the number of shared objects.

If you do this operation often, it might bring a lot if you can wrap the sets so that you can cache the result of the intersection operation keeping a <code>dirty</code> flag to track validity of the cached result, calculating again if needed.

blocks|key|769632|text|使用Java+8流：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|769633|set1.stream().filter(s+->+set2.contains(s)).collect(Collectors.toList());|code-block|syntax|javascript|769634|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Using Java 8 stream:

<pre><code>set1.stream().filter(s -&gt; set2.contains(s)).collect(Collectors.toList());
</code></pre>

blocks|key|553086|text|如果你只是为了计算集合中有多少元素而计算交集，我建议你只需要直接计算交集，而不是构建集合然后调用size()。|type|unstyled|depth|inlineStyleRanges|offset|length|style|CODE|entityRanges|data|553087|我的计数函数：|553088|/**
+*+Computes+the+size+of+intersection+of+two+sets
+*+@param+small+first+set.+preferably+smaller+than+the+second+argument
+*+@param+large+second+set;
+*+@param+<T>+the+type
+*+@return+size+of+intersection+of+sets
+*/
public+<T>+int+countIntersection(Set<T>+small,+Set<T>+large){
++++//assuming+first+argument+to+be+smaller+than+the+later;
++++//however+double+checking+to+be+sure
++++if+(small.size()+>+large.size())+{
++++++++//swap+the+references;
++++++++Set<T>+tmp+=+small;
++++++++small+=+large;
++++++++large+=+tmp;
++++}
++++int+result+=+0;
++++for+(T+item+:+small)+{
++++++++if+(large.contains(item)){
++++++++++++//item+found+in+both+the+sets
++++++++++++result%2B%2B;
++++++++}
++++}
++++return+result;
}|code-block|syntax|javascript|553089|entityMap^0|1C|6|0|0|0^^$0|@$1|2|3|4|5|6|7|O|8|@$9|P|A|Q|B|C]]|D|@]|E|$]]|$1|F|3|G|5|6|7|R|8|@]|D|@]|E|$]]|$1|H|3|I|5|J|7|S|8|@]|D|@]|E|$K|L]]|$1|M|3|-4|5|6|7|T|8|@]|D|@]|E|$]]]|N|$]]

If you are computing the intersection just for the sake of counting how many elements are there in the set, I suggest you just need to count the intersection directly instead of building the set and then calling <code>size()</code>. 

My function for counting:

<pre><code>/**
 * Computes the size of intersection of two sets
 * @param small first set. preferably smaller than the second argument
 * @param large second set;
 * @param &lt;T&gt; the type
 * @return size of intersection of sets
 */
public &lt;T&gt; int countIntersection(Set&lt;T&gt; small, Set&lt;T&gt; large){
 //assuming first argument to be smaller than the later;
 //however double checking to be sure
 if (small.size() &gt; large.size()) {
 //swap the references;
 Set&lt;T&gt; tmp = small;
 small = large;
 large = tmp;
 }
 int result = 0;
 for (T item : small) {
 if (large.contains(item)){
 //item found in both the sets
 result++;
 }
 }
 return result;
}
</code></pre>

blocks|key|553162|text|通过streams/reduce进行交集计数(它假设您在调用它之前确定了哪个集合更大)：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|553163|public+int+countIntersect(Set<Integer>+largerSet,+Set<Integer>+smallerSet){
++++return+smallerSet.stream().reduce(0,+(a,b)+->++largerSet.contains(b)?a%2B1:a);
}|code-block|syntax|javascript|553164|然而，我在其他地方读到，没有java代码可以比Set操作的set方法更快，因为它们是作为本机代码而不是java代码实现的。因此，我建议尝试使用BitSet以更快地获得结果。|553165|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Intersection counting through streams/reduce (it assumes you figure out which set is larger before calling it):

<pre><code>public int countIntersect(Set&lt;Integer&gt; largerSet, Set&lt;Integer&gt; smallerSet){
 return smallerSet.stream().reduce(0, (a,b) -&gt; largerSet.contains(b)?a+1:a);
}
</code></pre>

However somewhere else I have read that no java code can be faster than the Set methods for set operations because they are implemented as native code instead of java code. Therefore I back up the suggestion to try BitSet to achieve faster results.

What is the most efficient way to find the size of the intersection of two non-sparse Sets in Java? This is an operation I will be calling on large sets a very large number of times, so optimisation is important. I cannot modify the original sets.

I have looked at Apache Commons CollectionUtils.intersection which appears to be quite slow. My current approach is to take the smaller of the two sets, clone it, and then call .retainAll on the larger of the two sets.

<pre><code>public static int getIntersection(Set&lt;Long&gt; set1, Set&lt;Long&gt; set2) {
 boolean set1IsLarger = set1.size() &gt; set2.size();
 Set&lt;Long&gt; cloneSet = new HashSet&lt;Long&gt;(set1IsLarger ? set2 : set1);
 cloneSet.retainAll(set1IsLarger ? set1 : set2);
 return cloneSet.size();
}
</code></pre>

Efficiently compute Intersection of two Sets in Java?

Java

在Java中，找到两个非稀疏集合的交集大小的最有效方法是什么？这是一个我将在大型集合上调用非常多次的操作，因此优化是重要的。我不能修改原始集。我看过Apache Commons的CollectionUtils.intersection，它看起来相当慢。我目前的方法是取两个集合中较小的一个，克隆它，然后在两个集合中较大的...

问在Java中高效地计算两个集合的交集？
EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Java中高效地计算两个集合的交集？EN

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问在Java中高效地计算两个集合的交集？
EN