반응형
Java에서 두 세트의 교차점을 효율적으로 계산합니까?
Java에서 두 개의 비 희소 집합의 교차 크기를 찾는 가장 효율적인 방법은 무엇입니까? 이것은 대규모 세트에 대해 매우 많은 횟수로 호출 할 작업이므로 최적화가 중요합니다. 원래 세트를 수정할 수 없습니다.
상당히 느린 것처럼 보이는 Apache Commons CollectionUtils.intersection을 살펴 보았습니다. 내 현재 접근 방식은 두 세트 중 더 작은 세트를 가져와 복제 한 다음 두 세트 중 더 큰 세트에서 .retainAll을 호출하는 것입니다.
public static int getIntersection(Set<Long> set1, Set<Long> set2) {
boolean set1IsLarger = set1.size() > set2.size();
Set<Long> cloneSet = new HashSet<Long>(set1IsLarger ? set2 : set1);
cloneSet.retainAll(set1IsLarger ? set1 : set2);
return cloneSet.size();
}
게시 된 접근 방식과 새 HashSet 생성과 비교하여 몇 가지 테스트를 실행합니다. 즉, A집합 중 더 작은 집합이되고 B더 큰 집합이되게 한 다음의 각 항목에 대해 AB에도 존재하는 경우 C (새 HashSet)에 추가합니다. 건너 뜁니다.
게시 된 접근 방식 O(|A|)과 마찬가지로 반복이 발생 O(|A|)하고 B에 대한 프로브 가이므로 비용이 많이 듭니다 O(1). 복제 및 제거 접근 방식과 비교하는 방법을 모르겠습니다.
행복한 코딩-그리고 몇 가지 결과 게시 ;-)
사실, 더 생각에, 나는이 게시물의 방법보다 약간 더 경계를 가지고 있다고 생각 : O(|A|)대 O(|A| + |B|). 이것이 실제로 차이 (또는 개선)를 가져올 지 전혀 모르고 |A| <<< |B|.
좋아요, 정말 지루 했어요. 적어도 JDK 7 (Windows 7 x64)에서는 게시물에 제시된 방법 이 위의 접근 방식보다 느립니다 (대부분 일정하게 보이지만). 내 눈알 추측에 따르면 카운터를 사용하는 위의 제안보다 약 4 배 느리고 새 HashSet을 만들 때보 다 두 배 느립니다 . 이것은 여러 초기 세트 크기에서 "대략 일관된"것으로 보입니다.
( Voo가 지적했듯이 위의 숫자와이 마이크로 벤치 마크는 HashSet이 사용되고 있다고 가정합니다! 항상 그렇듯이 마이크로 벤치 마크에는 위험이 있습니다. YMMV.)
다음은 추악한 결과입니다 (밀리 초 단위).
1x1 테스트 실행 IntersectTest $ PostMethod @ 6cc2060e는 13.9808544 count = 1000000을 사용했습니다. IntersectTest $ MyMethod1 @ 7d38847d는 2.9893732 count = 1000000을 사용했습니다. IntersectTest $ MyMethod2 @ 9826ac5는 7.775945 count = 1000000을 사용했습니다. 1x10 테스트 실행 IntersectTest $ PostMethod @ 67fc9fee는 12.4647712 count = 734000을 받았습니다. IntersectTest $ MyMethod1 @ 7a67f797은 3.1567252 count = 734000을 받았습니다. IntersectTest $ MyMethod2 @ 3fb01949는 6.483941 count = 734000을 받았습니다. 1x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 16675039가 11.3069326 카운트 = 706000을 받았습니다. IntersectTest $ MyMethod1 @ 58c3d9ac는 2.3482693 카운트 = 706000을 사용했습니다. IntersectTest $ MyMethod2 @ 2207d8bb는 4.8687103 count = 706000을 사용했습니다. 1x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 33d626a4는 10.28656 count = 729000을 사용했습니다. IntersectTest $ MyMethod1 @ 3082f392 소요 2.3478658 count = 729000 IntersectTest $ MyMethod2 @ 65450f1f는 4.109205 카운트 = 729000을 사용했습니다. 10x2 테스트 실행 IntersectTest $ PostMethod @ 55c4d594는 10.4137618 count = 736000을 받았습니다. IntersectTest $ MyMethod1 @ 6da21389는 2.374206 count = 736000을 사용했습니다. IntersectTest $ MyMethod2 @ 2bb0bf9a가 4.9802039 카운트 = 736000 10x10 테스트 실행 IntersectTest $ PostMethod @ 7930ebb는 25.811083 count = 4370000을 받았습니다. IntersectTest $ MyMethod1 @ 47ac1adf는 6.9409306 count = 4370000을 받았습니다. IntersectTest $ MyMethod2 @ 74184b3b는 14.2603248 count = 4370000을 받았습니다. 10x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 7f423820은 25.0577691 count = 4251000을 받았습니다. IntersectTest $ MyMethod1 @ 5472fe25는 6.1376042 count = 4251000을 받았습니다. IntersectTest $ MyMethod2 @ 498b5a73은 13.9880385 count = 4251000을 받았습니다. 10x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 3033b503은 25.0312716 count = 4138000을 받았습니다. IntersectTest $ MyMethod1 @ 12b0f0ae는 6.0932898 카운트 = 4138000을 사용했습니다. IntersectTest $ MyMethod2 @ 1e893918은 13.8332505 count = 4138000을 사용했습니다. 100x1 테스트 실행 IntersectTest $ PostMethod @ 6366de01은 9.4531628 count = 700000을 받았습니다. IntersectTest $ MyMethod1 @ 767946a2는 2.4284762 count = 700000을 사용했습니다. IntersectTest $ MyMethod2 @ 140c7272는 4.7580235 count = 700000을 사용했습니다. 100x10 테스트 실행 IntersectTest $ PostMethod @ 3351e824는 24.9788668 count = 4192000을 받았습니다. IntersectTest $ MyMethod1 @ 465fadce는 6.1462852 count = 4192000을 사용했습니다. IntersectTest $ MyMethod2 @ 338bd37a는 13.1742654 count = 4192000을 받았습니다. 100x100 테스트 실행 IntersectTest $ PostMethod @ 297630d5는 193.0121077 count = 41047000을 받았습니다. IntersectTest $ MyMethod1 @ e800537은 45.2652397 count = 41047000을 사용했습니다. IntersectTest $ MyMethod2 @ 76d66550은 120.8494766 count = 41047000을 받았습니다. 100x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 33576738은 199.6269531 count = 40966000을 받았습니다. IntersectTest $ MyMethod1 @ 2f39a7dd는 45.5255814 카운트 = 40966000을 사용했습니다. IntersectTest $ MyMethod2 @ 723bb663은 122.1704975 count = 40966000을 사용했습니다. 1x1 테스트 실행 IntersectTest $ PostMethod @ 35e3bdb5는 9.5598373 count = 1000000을 사용했습니다. IntersectTest $ MyMethod1 @ 7abbd1b6은 2.6359174 count = 1000000을 사용했습니다. IntersectTest $ MyMethod2 @ 40c542ad는 6.1091794 count = 1000000을 사용했습니다. 1x10 테스트 실행 IntersectTest $ PostMethod @ 3c33a0c5는 9.4648528 카운트 = 733000을 받았습니다. IntersectTest $ MyMethod1 @ 61800463은 2.302116 count = 733000을 받았습니다. IntersectTest $ MyMethod2 @ 1ba03197은 5.4803628 count = 733000을 받았습니다. 1x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 71b8da5는 9.4971057 count = 719000을 받았습니다. IntersectTest $ MyMethod1 @ 21f04f48은 2.2983538 count = 719000을 사용했습니다. IntersectTest $ MyMethod2 @ 27e51160은 5.3926902 count = 719000을 사용했습니다. 1x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 2fe7106a는 9.4702331 count = 692000을 사용했습니다. IntersectTest $ MyMethod1 @ 6ae6b7b7 소요됨 2.3013066 count = 692000 IntersectTest $ MyMethod2 @ 51278635는 5.4488882 count = 692000을 사용했습니다. 10x2 테스트 실행 IntersectTest $ PostMethod @ 223b2d85는 9.5660879 count = 743000을 받았습니다. IntersectTest $ MyMethod1 @ 5b298851은 2.3481445 count = 743000을 받았습니다. IntersectTest $ MyMethod2 @ 3b4ac99는 4.8268489 count = 743000을 받았습니다. 10x10 테스트 실행 IntersectTest $ PostMethod @ 51c700a0은 23.0709476 count = 4326000을 받았습니다. IntersectTest $ MyMethod1 @ 5ffa3251은 5.5460785 count = 4326000을 사용했습니다. IntersectTest $ MyMethod2 @ 22fd9511은 13.4853948 count = 4326000을 받았습니다. 10x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 46b49793은 25.1295491 count = 4256000을 받았습니다. IntersectTest $ MyMethod1 @ 7a4b5828은 5.8520418 count = 4256000을 받았습니다. IntersectTest $ MyMethod2 @ 6888e8d1은 14.0856942 count = 4256000을 받았습니다. 10x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 5339af0d는 25.1752685 count = 4158000을 사용했습니다. IntersectTest $ MyMethod1 @ 7013a92a는 5.7978328 count = 4158000을 사용했습니다. IntersectTest $ MyMethod2 @ 1ac73de2는 13.8914112 count = 4158000을 사용했습니다. 100x1 테스트 실행 IntersectTest $ PostMethod @ 3d1344c8은 9.5123442 count = 717000을 사용했습니다. IntersectTest $ MyMethod1 @ 3c08c5cb는 2.34665 count = 717000을 사용했습니다. IntersectTest $ MyMethod2 @ 63f1b137은 4.907277 count = 717000을 사용했습니다. 100x10 테스트 실행 IntersectTest $ PostMethod @ 71695341은 24.9830339 카운트 = 4180000을 받았습니다. IntersectTest $ MyMethod1 @ 39d90a92는 5.8467864 count = 4180000을 받았습니다. IntersectTest $ MyMethod2 @ 584514e9는 13.2197964 count = 4180000을 받았습니다. 100x100 테스트 실행 IntersectTest $ PostMethod @ 21b8dc91은 195.1796213 count = 41060000을 받았습니다. IntersectTest $ MyMethod1 @ 6f98c4e2는 44.5775162 count = 41060000을 받았습니다. IntersectTest $ MyMethod2 @ 16a60aab는 121.1754402 count = 41060000을 받았습니다. 100x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 20b37d62는 200.973133 count = 40940000을 받았습니다. IntersectTest $ MyMethod1 @ 67ecbdb3은 45.4832226 count = 40940000을 받았습니다. IntersectTest $ MyMethod2 @ 679a6812는 121.791293 count = 40940000을 받았습니다. 1x1 테스트 실행 IntersectTest $ PostMethod @ 237aa07b는 9.2210288 count = 1000000을 사용했습니다. IntersectTest $ MyMethod1 @ 47bdfd6f는 2.3394042 count = 1000000을 받았습니다. IntersectTest $ MyMethod2 @ a49a735는 6.1688936 count = 1000000을 받았습니다. 1x10 테스트 실행 IntersectTest $ PostMethod @ 2b25ffba는 9.4103967 count = 736000을 받았습니다. IntersectTest $ MyMethod1 @ 4bb82277은 2.2976994 count = 736000을 사용했습니다. IntersectTest $ MyMethod2 @ 25ded977은 5.3310813 count = 736000을 받았습니다. 1x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 7154a6d5는 9.3818786 count = 704000을 받았습니다. IntersectTest $ MyMethod1 @ 6c952413 소요됨 2.3014931 count = 704000 IntersectTest $ MyMethod2 @ 33739316은 5.3307998 count = 704000을 받았습니다. 1x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 58334198은 9.3831841 count = 736000을 받았습니다. IntersectTest $ MyMethod1 @ d178f65는 2.3071236 count = 736000을 사용했습니다. IntersectTest $ MyMethod2 @ 5c7369a는 5.4062184 count = 736000을 사용했습니다. 10x2 테스트 실행 IntersectTest $ PostMethod @ 7c4bdf7c는 9.4040537 count = 735000을 사용했습니다. IntersectTest $ MyMethod1 @ 593d85a4는 2.3584088 count = 735000을 받았습니다. IntersectTest $ MyMethod2 @ 5610ffc1은 4.8318229 count = 735000을 받았습니다. 10x10 테스트 실행 IntersectTest $ PostMethod @ 46bd9fb8은 23.004925 count = 4331000을 받았습니다. IntersectTest $ MyMethod1 @ 4b410d50은 5.5678172 count = 4331000을 사용했습니다. IntersectTest $ MyMethod2 @ 1bd125c9는 14.6517184 count = 4331000을 받았습니다. 10x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 75d6ecff는 25.0114913 count = 4223000을 받았습니다. IntersectTest $ MyMethod1 @ 716195c9는 5.798676 count = 4223000을 받았습니다. IntersectTest $ MyMethod2 @ 3db0f946은 13.8064737 count = 4223000을 사용했습니다. 10x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 761d8e2a는 25.1910652 count = 4292000을 받았습니다. IntersectTest $ MyMethod1 @ e60a3fb는 5.8621189 count = 4292000을 사용했습니다. IntersectTest $ MyMethod2 @ 6aadbb1c는 13.8150282 count = 4292000을 받았습니다. 100x1 테스트 실행 IntersectTest $ PostMethod @ 48a50a6e는 9.4141906 count = 736000을 사용했습니다. IntersectTest $ MyMethod1 @ 4b4fe104는 2.3507252 count = 736000을 사용했습니다. IntersectTest $ MyMethod2 @ 693df43c는 4.7506854 count = 736000을 사용했습니다. 100x10 테스트 실행 IntersectTest $ PostMethod @ 4f7d29df는 24.9574096 count = 4219000을 사용했습니다. IntersectTest $ MyMethod1 @ 2248183e는 5.8628954 count = 4219000을 받았습니다. IntersectTest $ MyMethod2 @ 2b2fa007은 12.9836817 카운트 = 4219000을 받았습니다. 100x100 테스트 실행 IntersectTest $ PostMethod @ 545d7b6a는 193.2436192 count = 40987000을 받았습니다. IntersectTest $ MyMethod1 @ 4551976b는 44.634367 count = 40987000을 사용했습니다. IntersectTest $ MyMethod2 @ 6fac155a는 119.2478037 카운트 = 40987000을 받았습니다. 100x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 7b6c238d는 200.4385174 count = 40817000을 받았습니다. IntersectTest $ MyMethod1 @ 78923d48은 45.6225227 count = 40817000을 받았습니다. IntersectTest $ MyMethod2 @ 48f57fcf 소요됨 121.0602757 count = 40817000 1x1 테스트 실행 IntersectTest $ PostMethod @ 102c79f4는 9.0931408 count = 1000000을 사용했습니다. IntersectTest $ MyMethod1 @ 57fa8a77은 2.3309466 count = 1000000을 받았습니다. IntersectTest $ MyMethod2 @ 198b7c1은 5.7627226 count = 1000000을 받았습니다. 1x10 테스트 실행 IntersectTest $ PostMethod @ 8c646d0은 9.3208571 count = 726000을 사용했습니다. IntersectTest $ MyMethod1 @ 11530630은 2.3123797 count = 726000을 사용했습니다. IntersectTest $ MyMethod2 @ 61bb4232는 5.405318 count = 726000을 사용했습니다. 1x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 1a137105는 9.387384 count = 710000을 사용했습니다. IntersectTest $ MyMethod1 @ 72610ca2는 2.2938749 count = 710000을 받았습니다. IntersectTest $ MyMethod2 @ 41849a58은 5.3865938 count = 710000을 사용했습니다. 1x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 100001c8은 9.4289031 count = 696000을 사용했습니다. IntersectTest $ MyMethod1 @ 7074f9ac는 2.2977923 count = 696000을 받았습니다. IntersectTest $ MyMethod2 @ fb3c4e2는 5.3724119 카운트 = 696000을 사용했습니다. 10x2 테스트 실행 IntersectTest $ PostMethod @ 52c638d6은 9.4074124 count = 775000을 받았습니다. IntersectTest $ MyMethod1 @ 53bd940e는 2.3544881 count = 775000을 사용했습니다. IntersectTest $ MyMethod2 @ 43434e15는 4.9228549 count = 775000을 받았습니다. 10x10 테스트 실행 IntersectTest $ PostMethod @ 73b7628d는 23.2110252 count = 4374000을 받았습니다. IntersectTest $ MyMethod1 @ ca75255는 5.5877838 count = 4374000을 사용했습니다. IntersectTest $ MyMethod2 @ 3d0e50f0은 13.5902641 count = 4374000을 받았습니다. 10x100에 대한 테스트 실행 IntersectTest $ PostMethod @ 6d6bbba9는 25.1999918 count = 4227000을 받았습니다. IntersectTest $ MyMethod1 @ 3bed8c5e는 5.7879144 count = 4227000을 사용했습니다. IntersectTest $ MyMethod2 @ 689a8e0e는 13.9617882 count = 4227000을 받았습니다. 10x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 3da3b0a2는 25.1627329 count = 4222000을 받았습니다. IntersectTest $ MyMethod1 @ 45a17b4b는 5.8319523 count = 4222000을 받았습니다. IntersectTest $ MyMethod2 @ 6ca59ca3은 13.8885479 count = 4222000을 받았습니다. 100x1 테스트 실행 IntersectTest $ PostMethod @ 360202a5는 9.5115367 count = 705000을 받았습니다. IntersectTest $ MyMethod1 @ 3dfbba56은 2.3470254 count = 705000을 사용했습니다. IntersectTest $ MyMethod2 @ 598683e4는 4.8955489 count = 705000을 받았습니다. 100x10 테스트 실행 IntersectTest $ PostMethod @ 21426d0d는 25.8234298 count = 4231000을 받았습니다. IntersectTest $ MyMethod1 @ 1005818a는 5.8832067 count = 4231000을 받았습니다. IntersectTest $ MyMethod2 @ 597b933d는 13.3676148 count = 4231000을 받았습니다. 100x100 테스트 실행 IntersectTest $ PostMethod @ 6d59b81a는 193.676662 count = 41015000을 받았습니다. IntersectTest $ MyMethod1 @ 1d45eb0c는 44.6519088 count = 41015000을 사용했습니다. IntersectTest $ MyMethod2 @ 594a6fd7은 119.1646115 count = 41015000을 받았습니다. 100x1000에 대한 테스트 실행 IntersectTest $ PostMethod @ 6d57d9ac는 200.1651432 count = 40803000을 받았습니다. IntersectTest $ MyMethod1 @ 2293e349는 45.5311168 count = 40803000을 받았습니다. IntersectTest $ MyMethod2 @ 1b2edf5b는 120.1697135 카운트 = 40803000을 받았습니다.
그리고 여기에 추악한 (그리고 아마도 결함이있는) 마이크로 벤치 마크가 있습니다.
import java.util.*;
public class IntersectTest {
static Random rng = new Random();
static abstract class RunIt {
public long count;
public long nsTime;
abstract int Run (Set<Long> s1, Set<Long> s2);
}
// As presented in the post
static class PostMethod extends RunIt {
public int Run(Set<Long> set1, Set<Long> set2) {
boolean set1IsLarger = set1.size() > set2.size();
Set<Long> cloneSet = new HashSet<Long>(set1IsLarger ? set2 : set1);
cloneSet.retainAll(set1IsLarger ? set1 : set2);
return cloneSet.size();
}
}
// No intermediate HashSet
static class MyMethod1 extends RunIt {
public int Run (Set<Long> set1, Set<Long> set2) {
Set<Long> a;
Set<Long> b;
if (set1.size() <= set2.size()) {
a = set1;
b = set2;
} else {
a = set2;
b = set1;
}
int count = 0;
for (Long e : a) {
if (b.contains(e)) {
count++;
}
}
return count;
}
}
// With intermediate HashSet
static class MyMethod2 extends RunIt {
public int Run (Set<Long> set1, Set<Long> set2) {
Set<Long> a;
Set<Long> b;
Set<Long> res = new HashSet<Long>();
if (set1.size() <= set2.size()) {
a = set1;
b = set2;
} else {
a = set2;
b = set1;
}
for (Long e : a) {
if (b.contains(e)) {
res.add(e);
}
}
return res.size();
}
}
static Set<Long> makeSet (int count, float load) {
Set<Long> s = new HashSet<Long>();
for (int i = 0; i < count; i++) {
s.add((long)rng.nextInt(Math.max(1, (int)(count * load))));
}
return s;
}
// really crummy ubench stuff
public static void main(String[] args) {
int[][] bounds = {
{1, 1},
{1, 10},
{1, 100},
{1, 1000},
{10, 2},
{10, 10},
{10, 100},
{10, 1000},
{100, 1},
{100, 10},
{100, 100},
{100, 1000},
};
int totalReps = 4;
int cycleReps = 1000;
int subReps = 1000;
float load = 0.8f;
for (int tc = 0; tc < totalReps; tc++) {
for (int[] bound : bounds) {
int set1size = bound[0];
int set2size = bound[1];
System.out.println("Running tests for " + set1size + "x" + set2size);
ArrayList<RunIt> allRuns = new ArrayList<RunIt>(
Arrays.asList(
new PostMethod(),
new MyMethod1(),
new MyMethod2()));
for (int r = 0; r < cycleReps; r++) {
ArrayList<RunIt> runs = new ArrayList<RunIt>(allRuns);
Set<Long> set1 = makeSet(set1size, load);
Set<Long> set2 = makeSet(set2size, load);
while (runs.size() > 0) {
int runIdx = rng.nextInt(runs.size());
RunIt run = runs.remove(runIdx);
long start = System.nanoTime();
int count = 0;
for (int s = 0; s < subReps; s++) {
count += run.Run(set1, set2);
}
long time = System.nanoTime() - start;
run.nsTime += time;
run.count += count;
}
}
for (RunIt run : allRuns) {
double sec = run.nsTime / (10e6);
System.out.println(run + " took " + sec + " count=" + run.count);
}
}
}
}
}
그냥 사용 구글 구아바 의 Sets#intersection(Set, Set)방법을.
집합의 구성원을 비교적 작은 범위의 정수로 쉽게 매핑 할 수 있습니까? 그렇다면 BitSet 사용을 고려하십시오. 그런 다음 교차점은 비트 단위이며 한 번에 32 명의 잠재적 인 구성원입니다.
Set 메서드 preserveAll ()을 사용하면 모든 수동 작업을 피할 수 있습니다.
문서에서 :
s1.retainAll (s2) — s1을 s1과 s2의 교차점으로 변환합니다. (두 세트의 교차점은 두 세트에 공통적 인 요소 만 포함 된 세트입니다.)
두 세트를 모두 정렬 할 수 있다면 두 TreeSet반복기를 실행하는 것이 공유 객체 수를 계산하는 더 빠른 방법이 될 수 있습니다.
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 dirty flag to track validity of the cached result, calculating again if needed.
Using Java 8 stream:
set1.stream().filter(s -> set2.contains(s)).collect(Collectors.toList());
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 size().
My function for counting:
/**
* 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++;
}
}
return result;
}
That is a good approach. You should be getting O(n) performance from your current solution.
FYI, if any collection of sets are all sorted using the same comparision relation, then you can iterate their intersection in time N * M, where N is the size of the smallest set and M is the number of sets.
Implementation left as exercise to reader
. Here's an example.
Intersection counting through streams/reduce (it assumes you figure out which set is larger before calling it):
public int countIntersect(Set<Integer> largerSet, Set<Integer> smallerSet){
return smallerSet.stream().reduce(0, (a,b) -> largerSet.contains(b)?a+1:a);
}
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.
ReferenceURL : https://stackoverflow.com/questions/7574311/efficiently-compute-intersection-of-two-sets-in-java
반응형
'development' 카테고리의 다른 글
| IE는 서버에서 json 결과를 열거 나 저장하라는 메시지를 표시합니다. (0) | 2021.01.07 |
|---|---|
| http 프록시는 어떻게 작동합니까? (0) | 2021.01.07 |
| OpenCV C ++에서 (Mat) 행렬의 값을 인쇄합니다. (0) | 2021.01.07 |
| ScheduledExecutorService에서 작업을 제거하는 방법은 무엇입니까? (0) | 2021.01.07 |
| ConfigureAwait (false)와 Task.Run 사용의 차이점은 무엇입니까? (0) | 2021.01.07 |