Java에서 두 세트를 비교하는 가장 빠른 방법은 무엇입니까?
목록 요소를 비교하는 코드를 최적화하려고 합니다.
예.
public void compare(Set<Record> firstSet, Set<Record> secondSet){
for(Record firstRecord : firstSet){
for(Record secondRecord : secondSet){
// comparing logic
}
}
}
세트 내 레코드 수가 많은 점 양해 바랍니다.
감사해요.
셰카루
firstSet.equals(secondSet)
만약 가 다른집합이 다른 에서 발견되면 어떻게 요?에는 「」가 .void이 방법으로 필요한 작업을 할 수 있을 거라고 생각합니다.
필요에 따라 보다 세밀한 제어:
if (!firstSet.containsAll(secondSet)) {
// do something if needs be
}
if (!secondSet.containsAll(firstSet)) {
// do something if needs be
}
한 세트로만 구성되고 다른 세트로 구성되는 요소를 가져와야 하는 경우.
집::set.removeAll(otherSet)집합이 아닌 부울을 반환합니다.을 한 후removeAll()을 사용합니다.
Set one = new HashSet<>(firstSet);
Set two = new HashSet<>(secondSet);
one.removeAll(secondSet);
two.removeAll(firstSet);
의 one ★★★★★★★★★★★★★★★★★」two둘 다 비어있으면 두 집합이 동일하다는 것을 알 수 있습니다.그렇지 않은 경우 집합이 불균등하게 된 요소가 있는 것입니다.
기록 수가 많을 수 있다고 말씀하셨습니다.이 되는 이 「」인 .HashSet각 레코드의 취득은, 다음의 순서로 행해집니다.O(1)시간이면 더 나아질 수 없어요 TreeSetO(log n).
경우, " " " 를 참조하십시오.equals의 메서드입니다.AbstractSet같이 합니다.
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
return containsAll(c);
}
다음과 같은 일반적인 경우를 최적화하는 방법에 주목하십시오.
- 두 물체는 같다
- 다른 오브젝트는 전혀 세트가 아닙니다.
- 두 세트의 사이즈가 달라요.
후 ★★★★★★★★★★★★★★★★★.containsAll(...)false이 세트에도 없는 다른 세트 내의 요소를 발견하면 바로 표시됩니다.그러나 모든 요소가 두 세트에 존재할 경우 모든 요소를 테스트해야 합니다.
따라서 두 집합이 동일하지만 동일한 개체가 아닌 경우 최악의 성능이 발생합니다.은 보통 그은 that that that that 입니다.O(N) ★★★★★★★★★★★★★★★★★」O(NlogN)의 this.containsAll(c).
또한 세트가 크고 요소 중 극히 일부만 다를 경우 최악의 경우에 가까운 성능을 얻을 수 있습니다.
갱신하다
커스텀 세트 구현에 시간을 투자하고 싶다면 "거의 동일한" 사례를 개선할 수 있는 방법이 있습니다.
집합 수 .O(1)그런 다음 두 세트의 해시 코드를 가속도로 비교할 수 있습니다.
어떻게 그런 해시코드를 구현할 수 있죠?set hashcode가 다음과 같다면:
- 빈 세트의 경우 0, 그리고
- 비어 있지 않은 집합에 대한 모든 요소 해시 코드의 XOR,
요소를 추가하거나 제거할 때마다 세트의 캐시된 해시 코드를 저렴하게 업데이트할 수 있습니다.두 경우 모두 현재 설정된 해시 코드를 사용하여 요소의 해시 코드를 XOR하기만 하면 됩니다.
물론 요소 해시코드는 안정적이지만 요소가 집합의 멤버라고 가정합니다.또한 요소 클래스의 해시 코드 함수가 양호한 확산을 제공하는 것으로 가정합니다.에도 2개의 세트해시코드로 입니다.O(N)모든 요소의 비교.
적어도 이론상으론 이 아이디어를 좀 더 발전시킬 수 있을 거야
경고 - 이것은 매우 추측성이 높습니다."생각 실험"을 원하신다면요.
set 요소 클래스에 요소의 암호 체크섬을 반환하는 메서드가 있다고 가정합니다.이제 요소에 대해 반환된 체크섬을 XOR하여 세트의 체크섬을 구현합니다.
이걸로 뭘 얻을 수 있죠?
아무것도 진행되지 않는다고 가정할 경우 2개의 동일하지 않은 집합 요소가 동일한 N비트 체크섬을 가질 확률은 2입니다-N.또한 2개의 부등 집합이 동일한 N비트 체크섬을 가질 확률도-N 2입니다.그래서 제 생각은, 이 시스템을 도입할 수 있다는 것입니다.equals같이요.
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Collection c = (Collection) o;
if (c.size() != size())
return false;
return checksums.equals(c.checksums);
}
위의 가정 하에, 이것은 당신에게 두 번 중-N 한 번만 틀린 답을 줄 것입니다.N을 충분히 크게 하면(예: 512비트), 오답의 확률은 무시할 수 있습니다(예-150: 10비트).
단점은 요소의 암호 체크섬을 계산하는 데 비용이 많이 든다는 점입니다.특히 비트 수가 증가함에 따라 더욱 그렇습니다.체크섬을 메모하기 위한 효과적인 메커니즘이 필요합니다.그리고 그건 문제가 될 수 있어.
또 다른 단점은 0이 아닌 오차 확률은 아무리 작은 확률이라도 받아들일 수 없다는 것입니다.(하지만 만약 그렇다면...)당신은 우주선이 임계치를 날리는 경우를 어떻게 다루나요?또는 다중 시스템의 두 인스턴스에서 동일한 비트를 동시에 플립하는 경우)
.Sets다음과 같은 이점이 있습니다.
public static <E> boolean equals(Set<? extends E> set1, Set<? extends E> set2){
return Sets.symmetricDifference(set1,set2).isEmpty();
}
O(N) 솔루션은 다음과 같은 매우 구체적인 경우에 사용할 수 있습니다.
- 세트는 둘 다 정렬되어 있다
- 둘 다 같은 순서로 정렬된
다음 코드는 두 세트가 비교 가능한 레코드에 기반한다고 가정합니다.유사한 방법은 Comparator를 기반으로 할 수 있습니다.
public class SortedSetComparitor <Foo extends Comparable<Foo>>
implements Comparator<SortedSet<Foo>> {
@Override
public int compare( SortedSet<Foo> arg0, SortedSet<Foo> arg1 ) {
Iterator<Foo> otherRecords = arg1.iterator();
for (Foo thisRecord : arg0) {
// Shorter sets sort first.
if (!otherRecords.hasNext()) return 1;
int comparison = thisRecord.compareTo(otherRecords.next());
if (comparison != 0) return comparison;
}
// Shorter sets sort first
if (otherRecords.hasNext()) return -1;
else return 0;
}
}
https://www.mkyong.com/java/java-how-to-compare-two-sets/에서 다음 솔루션을 입수할 수 있습니다.
public static boolean equals(Set<?> set1, Set<?> set2){
if(set1 == null || set2 ==null){
return false;
}
if(set1.size() != set2.size()){
return false;
}
return set1.containsAll(set2);
}
또는 단일 반환문을 사용하는 경우:
public static boolean equals(Set<?> set1, Set<?> set2){
return set1 != null
&& set2 != null
&& set1.size() == set2.size()
&& set1.containsAll(set2);
}
사용하시는 경우Guava을 사용하다
SetView<Record> added = Sets.difference(secondSet, firstSet);
SetView<Record> removed = Sets.difference(firstSet, secondSet);
그리고 이것들을 바탕으로 결론을 내립니다.
비교하기 전에 두 번째 세트를 해시맵에 넣습니다.이렇게 하면 두 번째 목록의 검색 시간을 n(1)로 줄일 수 있습니다.다음과 같이 합니다.
HashMap<Integer,Record> hm = new HashMap<Integer,Record>(secondSet.size());
int i = 0;
for(Record secondRecord : secondSet){
hm.put(i,secondRecord);
i++;
}
for(Record firstRecord : firstSet){
for(int i=0; i<secondSet.size(); i++){
//use hm for comparison
}
}
public boolean equals(Object o) {
if (o == this)
return true;
if (!(o instanceof Set))
return false;
Set<String> a = this;
Set<String> b = o;
Set<String> thedifference_a_b = new HashSet<String>(a);
thedifference_a_b.removeAll(b);
if(thedifference_a_b.isEmpty() == false) return false;
Set<String> thedifference_b_a = new HashSet<String>(b);
thedifference_b_a.removeAll(a);
if(thedifference_b_a.isEmpty() == false) return false;
return true;
}
동등한 방식의 메서드 레퍼런스를 사용할 수 있다고 생각합니다.의심의 여지가 없는 오브젝트 타입에는 독자적인 비교 방법이 있다고 가정합니다.간단명료한 예가 여기 있습니다.
Set<String> set = new HashSet<>();
set.addAll(Arrays.asList("leo","bale","hanks"));
Set<String> set2 = new HashSet<>();
set2.addAll(Arrays.asList("hanks","leo","bale"));
Predicate<Set> pred = set::equals;
boolean result = pred.test(set2);
System.out.println(result); // true
언급URL : https://stackoverflow.com/questions/3341202/what-is-the-fastest-way-to-compare-two-sets-in-java
'programing' 카테고리의 다른 글
| Vuex 상태를 업데이트할 때 V-snackbar가 표시되지 않음 (0) | 2023.01.20 |
|---|---|
| PHP 키워드 'var'의 역할은 무엇입니까? (0) | 2023.01.20 |
| MySQL은 예외 없이 테이블이 존재하는지 확인합니다. (0) | 2023.01.10 |
| mysql-python 설치 오류: include 파일 'config-win'을 열 수 없습니다.h' (0) | 2023.01.10 |
| mysql에서 datetime 필드를 인덱싱하는 것이 좋은 생각입니까? (0) | 2023.01.10 |