ArrayList에 Java의 객체가 포함되어 있는지 확인하는 가장 효율적인 방법
Java에 ArrayList 개체가 있습니다. 개체에는 4 개의 필드가 있으며 그 중 2 개는 개체를 다른 것과 동일하게 간주하는 데 사용합니다. 이 두 필드가 주어지면 배열에 해당 개체가 포함되어 있는지 확인하는 가장 효율적인 방법을 찾고 있습니다.
렌치는 이러한 클래스가 XSD 개체를 기반으로 생성되므로 클래스 자체를 수정하여 .equals.
각 개체에 대해 두 필드를 반복하고 수동으로 비교 한 다음 발견되면 중단하는 것보다 더 좋은 방법이 있습니까? 더 나은 방법을 찾는 것은 너무 지저분 해 보입니다.
편집 : ArrayList는 개체로 정렬되지 않은 SOAP 응답에서 제공됩니다.
얼마나 효율적인지에 달려 있습니다. 특정 조건을 만족하는 요소를 찾는 목록을 단순히 반복하는 것은 O (n)이지만 Equals 메서드를 구현할 수 있다면 ArrayList.Contains도 마찬가지입니다. 루프 또는 내부 루프에서이 작업을 수행하지 않는 경우이 방법은 아마도 괜찮을 것입니다.
어떤 비용으로도 매우 효율적인 조회 속도가 필요한 경우 다음 두 가지를 수행해야합니다.
- 클래스가 생성된다는 사실을 해결하십시오. 생성 된 클래스를 래핑 할 수 있고이 두 필드를 기반으로 equals () 를 구현하는 어댑터 클래스를 작성하십시오 (공용이라고 가정). hashCode () (*) 도 구현하는 것을 잊지 마십시오.
- 해당 어댑터로 각 개체를 래핑하고 HashSet에 넣습니다. HashSet.contains () 는 일정한 액세스 시간, 즉 O (n) 대신 O (1 )을 갖습니다.
물론이 HashSet을 구축하는 데에는 여전히 O (n) 비용이 있습니다. HashSet 구축 비용이 필요한 모든 contains () 검사의 총 비용과 비교하여 무시할 수있는 경우에만 얻을 수 있습니다. 중복없이 목록을 작성하려고하는 것은 그러한 경우입니다.
* ( ) hashCode ( ) 구현은 equals 구현에 사용중인 동일한 필드의 hashCode를 XOR (^ 연산자)하여 수행하는 것이 가장 좋습니다 (그러나 XOR이 0을 산출 할 가능성을 줄이려면 31 을 곱 하십시오)
정렬 및 이진 검색을 위해 Java의 내장 메소드와 함께 Comparator를 사용할 수 있습니다. 다음과 같은 클래스가 있다고 가정합니다. 여기서 a와 b는 정렬에 사용하려는 필드입니다.
class Thing { String a, b, c, d; }
Comparator를 정의합니다.
Comparator<Thing> comparator = new Comparator<Thing>() {
public int compare(Thing o1, Thing o2) {
if (o1.a.equals(o2.a)) {
return o1.b.compareTo(o2.b);
}
return o1.a.compareTo(o2.a);
}
};
그런 다음 목록을 정렬하십시오.
Collections.sort(list, comparator);
마지막으로 이진 검색을 수행하십시오.
int i = Collections.binarySearch(list, thingToFind, comparator);
제약 조건이 주어지면 무차별 대입 검색 (또는 검색이 반복되는 경우 인덱스 생성)에 갇혀 있습니다. 어떻게 ArrayList생성 되는지 자세히 설명해 주 시겠습니까? 아마도 거기에 약간의 흔들림이있을 것입니다.
찾고있는 것이 더 예쁜 코드라면 Apache Commons Collections 클래스, 특히 CollectionUtils.find () 를 사용하여 기성 구문 설탕을 사용하는 것이 좋습니다 .
ArrayList haystack = // ...
final Object needleField1 = // ...
final Object needleField2 = // ...
Object found = CollectionUtils.find(haystack, new Predicate() {
public boolean evaluate(Object input) {
return needleField1.equals(input.field1) &&
needleField2.equals(input.field2);
}
});
목록이 정렬 된 경우 이진 검색을 사용할 수 있습니다 . 그렇지 않다면 더 좋은 방법은 없습니다.
이 작업을 많이한다면 처음에 목록을 정렬하는 것이 거의 확실합니다. 클래스를 수정할 수 없으므로 Comparator정렬 및 검색을 수행 하려면 a 를 사용해야합니다 .
equals 메소드는해도 한 두 필드를 비교 수동으로 수행으로, 논리적으로, 그냥 같은 코드가 될 것이다. 좋습니다. "지저분 할 수 있습니다."하지만 여전히 정답입니다.
내 ForEach DSL 사용자 인 경우 Detect쿼리를 통해 수행 할 수 있습니다 .
Foo foo = ...
Detect<Foo> query = Detect.from(list);
for (Detect<Foo> each: query)
each.yield = each.element.a == foo.a && each.element.b == foo.b;
return query.result();
각 개체에 대해 두 필드를 반복하고 수동으로 비교 한 다음 발견되면 중단하는 것보다 더 좋은 방법이 있습니까? 더 나은 방법을 찾는 것은 너무 지저분 해 보입니다.
당신의 관심사가 유지 보수성이라면 Fabian Steeg가 제안한 것을 할 수 있습니다. (그것이 제가 할 것입니다) 아마도 "가장 효율적"은 아니지만 (배열을 먼저 정렬 한 다음 이진 검색을 수행해야하기 때문에) 확실히 가장 깨끗합니다. 더 나은 옵션입니다.
효율성에 정말로 관심이 있다면 객체의 필드를 해시로 사용하고 HashMap을 저장소로 사용하는 사용자 지정 목록 구현을 만들 수 있습니다. 그러나 아마도 이것은 너무 많을 것입니다.
그런 다음 데이터를 채우는 위치를 ArrayList에서 YourCustomList로 변경해야합니다.
처럼:
List list = new ArrayList();
fillFromSoap( list );
에:
List list = new MyCustomSpecialList();
fillFromSoap( list );
구현은 다음과 같습니다.
class MyCustomSpecialList extends AbstractList {
private Map<Integer, YourObject> internalMap;
public boolean add( YourObject o ) {
internalMap.put( o.getThatFieldYouKnow(), o );
}
public boolean contains( YourObject o ) {
return internalMap.containsKey( o.getThatFieldYouKnow() );
}
}
HashSet과 매우 유사하지만 여기서 문제는 HashSet이 아마도 여러분이 가지고 있지 않은 hashCode 메서드의 좋은 구현에 의존한다는 것입니다. 대신 한 개체를 다른 개체와 동일하게 만드는 해시 "당신이 알고있는 그 필드"로 사용합니다.
물론 처음부터 List를 구현하는 것이 위의 스 니펫보다 훨씬 까다롭기 때문에 Fabian Steeg 제안이 구현하기가 더 좋고 더 쉬울 것이라고 말하는 이유입니다 (이와 같은 것이 더 효율적일 수 있음).
마지막에 무엇을했는지 알려주세요.
목록이 필요한 것이 아닐 수도 있습니다.
아마도 TreeSet 이 더 나은 컨테이너가 될 것입니다. O (log N) 삽입 및 검색 및 순서가 지정된 반복 (하지만 중복을 허용하지 않음)을 얻습니다.
LinkedHashMap 은 유스 케이스에 더 좋을 수 있습니다.
필드 값을 키로하여 이러한 객체의 HashMap을 구축하는 것은 성능 관점에서 가치가있을 수 있습니다. 예를 들어 맵을 한 번 채우고 객체를 매우 효율적으로 찾습니다.
동일한 목록에서 여러 번 검색해야하는 경우 인덱스를 작성하는 것이 좋습니다.
한 번 반복하고 찾고있는 같음 값을 키로 사용하고 적절한 노드를 값으로 사용하여 HashMap을 빌드합니다. 주어진 같음 값 대신 모두가 필요한 경우 맵에 값 유형 목록을 지정하고 초기 반복에서 전체 목록을 작성하십시오.
인덱스를 구축하는 오버 헤드가 예상 노드를 찾을 때까지 순회 만 가려 질 수 있으므로이를 수행하기 전에 측정해야합니다.
세 가지 기본 옵션이 있습니다.
1) 검색 성능이 가장 중요하고 그렇게하는 것이 실용적인 경우 한 번 빌드 된 해시 테이블 형식을 사용합니다 (목록이 변경되면 변경됨).
2) List가 편리하게 정렬되어 있거나 정렬하는 것이 실용적이고 O (log n) 검색만으로 충분하다면 정렬하고 검색합니다.
3) O (n) 검색이 충분히 빠르거나 데이터 구조 또는 대안을 조작 / 유지하는 것이 비현실적인 경우 목록을 반복합니다.
List에 대한 단순한 반복보다 복잡한 코드를 작성하기 전에 몇 가지 질문을 생각해 볼 가치가 있습니다.
왜 다른 것이 필요합니까? (시간) 성능? 우아? 유지 보수성? 재사용 하시겠습니까? 이것들은 모두 떨어져 있든 함께 든 괜찮은 이유이지만 솔루션에 영향을 미칩니다.
문제의 데이터 구조를 얼마나 제어 할 수 있습니까? 건축 방식에 영향을 미칠 수 있습니까? 나중에 관리 하시겠습니까?
데이터 구조 (및 기본 개체)의 수명주기는 무엇입니까? 한 번에 구축되고 변경되지 않았습니까, 아니면 매우 역동적입니까? 코드가 수명주기를 모니터링 (또는 변경) 할 수 있습니까?
메모리 풋 프린트와 같은 다른 중요한 제약이 있습니까? 중복에 대한 정보가 중요합니까? 기타.
가장 간단한 해결책은 개체를 래핑하고 contains 호출을 래핑 된 클래스의 컬렉션에 위임하는 것입니다. 이것은 비교기와 유사하지만 결과 컬렉션을 정렬하도록 강요하지는 않으며 단순히 ArrayList.contains ()를 사용할 수 있습니다.
public class Widget {
private String name;
private String desc;
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public String getDesc() {
return desc;
}
public void setDesc(String desc) {
this.desc = desc;
}
}
public abstract class EqualsHashcodeEnforcer<T> {
protected T wrapped;
public T getWrappedObject() {
return wrapped;
}
@Override
public boolean equals(Object obj) {
return equalsDelegate(obj);
}
@Override
public int hashCode() {
return hashCodeDelegate();
}
protected abstract boolean equalsDelegate(Object obj);
protected abstract int hashCodeDelegate();
}
public class WrappedWidget extends EqualsHashcodeEnforcer<Widget> {
@Override
protected boolean equalsDelegate(Object obj) {
if (obj == null) {
return false;
}
if (obj == getWrappedObject()) {
return true;
}
if (obj.getClass() != getWrappedObject().getClass()) {
return false;
}
Widget rhs = (Widget) obj;
return new EqualsBuilder().append(getWrappedObject().getName(),
rhs.getName()).append(getWrappedObject().getDesc(),
rhs.getDesc()).isEquals();
}
@Override
protected int hashCodeDelegate() {
return new HashCodeBuilder(121, 991).append(
getWrappedObject().getName()).append(
getWrappedObject().getDesc()).toHashCode();
}
}
'Development Tip' 카테고리의 다른 글
| DOM 객체에 속성을 설정할 때 매개 변수 재 할당을 방지하는 방법 (0) | 2020.10.28 |
|---|---|
| ESLint 달러 ($)가 정의되지 않았습니다. (0) | 2020.10.28 |
| Java-문자열을 유효한 URI 객체로 변환 (0) | 2020.10.28 |
| 앵커 링크 내부의 버튼은 Firefox에서 작동하지만 Internet Explorer에서는 작동하지 않습니까? (0) | 2020.10.28 |
| 이름으로 저장 프로 시저 찾기 (0) | 2020.10.28 |