Arraylist에 Java에 객체가 포함되어 있는지 확인하는 가장 효율적인 방법
https://stackoverflow.com/questions/558978
-
05-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian문제
Java에는 객체의 배열 목록이 있습니다. 객체에는 4 개의 필드가 있으며 그 중 2 개는 객체를 다른 필드와 동일하게 고려하는 데 사용합니다. 배열에 해당 객체가 포함되어 있는지 확인하기 위해 두 개의 필드를 감안할 때 가장 효율적인 방법을 찾고 있습니다.
렌치는이 클래스가 XSD 객체를 기반으로 생성되므로 클래스 자체를 수정하여 .equals.
각 객체의 두 필드를 통과하고 수동으로 비교 한 다음 발견 될 때 깨는 것보다 더 나은 방법이 있습니까? 그것은 너무 지저분 해 보이고 더 나은 방법을 찾고 있습니다.
편집하다: Arraylist는 객체로마다되지 않은 비누 응답에서 비롯됩니다.
해결책
그것은 당신이 얼마나 효율적으로 필요한지에 달려 있습니다. 특정 조건을 만족하는 요소를 찾는 요소를 찾는 것은 목록을 반복하는 것은 O (n)이지만 arraylist도 마찬가지입니다. 루프 나 내부 루프 에서이 작업을 수행하지 않으면이 접근 방식은 아마도 괜찮을 것입니다.
모든 비용으로 매우 효율적인 조회 속도가 필요한 경우 두 가지 작업을 수행해야합니다.
- 클래스가 생성된다는 사실을 중심으로 작업 : 생성 된 클래스를 감싸고 구현할 수있는 어댑터 클래스를 작성하십시오. equals () 이 두 분야를 기반으로 (공개되었다고 가정). 도 구현하는 것을 잊지 마십시오 해시 코드() (*)
- 해당 어댑터로 각 물체를 감고 해시 세트에 넣으십시오.Hashset.contains () 일정한 액세스 시간, 즉 O (n) 대신 O (1)가 있습니다.
물론,이 해시 세트를 구축하는 데 여전히 O (n) 비용이 있습니다. 해시 세트를 구축하는 데 드는 비용이 모든 포함 () 점검의 총 비용에 비해 무시할 수있는 경우에만 얻을 수 있습니다. 복제없이 목록을 작성하려고하는 것은 그러한 경우입니다.
* () hashcode () 구현은 xor'ing (^ 연산자)에 의해 가장 잘 수행됩니다. 31을 곱합니다 XOR의 가능성을 줄이려면 0)
다른 팁
정렬 및 이진 검색을 위해 Java의 내장 방법과 비교기를 사용할 수 있습니다. A와 B가 정렬에 사용하려는 필드 인 경우 이와 같은 클래스가 있다고 가정 해 봅시다.
class Thing { String a, b, c, d; }
비교기를 정의합니다.
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);
}
});
목록이있는 경우 정렬, 당신은 a를 사용할 수 있습니다 이진 검색. 그렇지 않다면 더 나은 방법은 없습니다.
당신이 이것을 많이하고 있다면, 처음으로 목록을 정렬하는 것은 거의 확실하게 가치가있을 것입니다. 클래스를 수정할 수 없으므로 사용해야합니다. Comparator 정렬 및 검색을 수행합니다.
동등한 방법이라도 ~이었다 이 두 필드를 비교하면 논리적으로 수동으로 수행하는 것과 동일한 코드가됩니다. 좋아, "지저분해질 수도 있지만 여전히 정답입니다.
당신이 내 사용자라면 foreach dsl, 그것은 a 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 아마도 "가장 효율적인"것은 아니지만 (배열을 먼저 정렬하고 이진 검색을 수행해야하기 때문에) 가장 깨끗하고 더 나은 옵션을 제안하십시오.
효율성에 관심이있는 경우 객체의 필드를 해시로 사용하는 사용자 정의 목록 구현을 만들고 해시 맵을 스토리지로 사용할 수 있습니다. 그러나 아마도 이것은 너무 많을 것입니다.
그런 다음 Arraylist에서 CustomList로 데이터를 채우는 장소를 변경해야합니다.
처럼:
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() );
}
}
해시 세트와 마찬가지로 여기서 문제는 해시 세트가 해시 코드 방법의 좋은 구현에 의존한다는 것입니다. 대신 당신은 한 객체를 다른 개체와 동일하게 만드는 해시 "당신이 아는 필드"로 사용합니다.
물론 위의 스 니펫보다 훨씬 까다로운 스크래치에서 목록을 구현하는데 Fabian Steeg 제안이 더 좋고 구현하기 쉬울 것입니다 (이와 같은 것은 더 효율적이지만)
결국 당신이 한 일을 알려주세요.
아마도 목록이 필요한 것이 아닐 수도 있습니다.
어쩌면 A. 트리 셋 더 나은 컨테이너가 될 것입니다. O (log n) 삽입 및 검색을 얻고 반복을 주문했지만 복제를 허용하지 않습니다.
LinkedHashmap 유스 케이스에 더 좋을 수도 있습니다. 확인하십시오.
키로 필드 값을 기준으로 이러한 객체의 해시 맵을 구축하는 것은 성능 관점에서 가치가있을 수 있습니다. 예를 들어 맵을 한 번 채우고 객체를 매우 효율적으로 찾습니다.
같은 목록에서 여러 시간을 검색 해야하는 경우 색인을 구축하기 위해 돈을 지불 할 수 있습니다.
한 번 반복하고 키로 찾고있는 동등한 값을 가진 해시 맵을 구축하고 값으로 적절한 노드를 적절한 노드로 만듭니다. 주어진 주어진 값의 사람 대신 모든 것이 필요한 경우 맵에 값 유형의 목록이 있고 초기 반복에서 전체 목록을 작성하십시오.
인덱스 구축의 오버 헤드가 예상 노드가 발견 될 때까지 가로 지르는 오버 섀도우가있을 수 있으므로이 작업을 수행하기 전에 측정해야합니다.
세 가지 기본 옵션이 있습니다.
1) 검색 성능이 가장 중요하고 실용적이면 한 번 구축 된 해시 테이블의 형태를 사용하십시오 (목록이 변경되는 경우/변경).
2) 목록이 편리하게 정렬되거나 정렬하는 것이 실용적이면 O (log n) 검색이 충분한 경우, 정렬 및 검색이 충분합니다.
3) O (n) 검색이 충분히 빠르거나 데이터 구조를 조작/유지하는 것이 실용적이지 않은 경우 목록을 반복하십시오.
목록을 통해 간단한 반복보다 코드를 더 복잡하게 작성하기 전에 몇 가지 질문을 통해 생각할 가치가 있습니다.
왜 다른 것이 필요한가? (시간) 성능? 우아? 유지 가능성? 재사용? 이 모든 것은 괜찮은 이유이지만, 해당 또는 함께 일하지만 솔루션에 영향을 미칩니다.
문제의 데이터 구조에 대해 얼마나 많은 제어가 있습니까? 그것이 어떻게 건축되는지에 영향을 줄 수 있습니까? 나중에 관리 했습니까?
데이터 구조 (및 기본 객체)의 수명주기는 얼마입니까? 그것은 한 번에 모두 구축되었으며 결코 변하지 않거나 역동적입니까? 코드가 수명주기를 모니터링하거나 변경할 수 있습니까?
메모리 풋 프린트와 같은 다른 중요한 제약이 있습니까? 복제에 대한 정보가 중요합니까? 등.
가장 간단한 해결책은 물체를 감싸고 래핑 클래스의 컬렉션에 대한 호출을 포함하는 것을 위임하는 것입니다. 이것은 비교기와 유사하지만 결과 컬렉션을 정렬하도록 강요하지 않으면 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();
}
}
