목록이 있는지 확인하는 가장 빠른 방법

목록이 있는지 확인하는 가장 빠른 방법 고유 한 문자열을 포함

---

기본적으로 약 1,000,000 개의 문자열이 있으며 각 요청에 대해 문자열이 목록에 속하는지 여부를 확인해야합니다.

성능이 걱정 되는데요, 최선의 방법은 무엇인가요? ArrayList? 해시시?

---

가장 좋은 방법은 a를 사용 HashSet하고 contains()메서드 를 통해 세트에 문자열이 있는지 확인하는 것입니다. HashSet은 Object 메서드 hashCode()및 equals(). HashSet상태에 대한 Javadoc :

이 클래스는 기본 작업 (추가, 제거, 포함 및 크기 조정)에 대해 일정한 시간 성능을 제공합니다.

HashSet 은 객체를 해시 버킷에 저장합니다. 즉, hashCode메서드에서 반환 된 값 이 객체가 저장되는 버킷을 결정한다는 것을 의미합니다. 이렇게 HashSet하면 equals()메서드 를 통해 수행 해야하는 동등성 검사의 양 이 다른 객체로 줄어 듭니다. 동일한 해시 버킷.

HashSets 및 HashMaps를 효과적으로 사용하려면 javadoc에 설명 된equals 및 hashCode계약을 준수해야합니다 . 이러한 방법 의 경우 이를 수행하기 위해 이미 구현되었습니다.java.lang.String

---

일반적으로 HashSet은 ArrayList처럼 각 요소를 살펴보고 비교할 필요가 없지만 일반적으로 해시 코드가 동일한 요소를 최대 몇 개까지 비교하므로 더 나은 성능을 제공합니다.

그러나 1M 문자열의 경우 hashSet의 성능이 여전히 최적이 아닐 수 있습니다. 캐시 미스가 많으면 세트 검색 속도가 느려집니다. 모든 문자열이 똑같이 가능성이 있다면 이것은 피할 수 없습니다. 그러나 일부 문자열이 다른 문자열보다 더 자주 요청되는 경우 일반 문자열을 작은 hashSet에 배치하고 더 큰 집합을 확인하기 전에 먼저 확인할 수 있습니다. 작은 해시 세트는 캐시에 맞도록 크기를 조정해야합니다 (예 : 최대 수백 K). 그러면 작은 해시 세트에 대한 히트는 매우 빠르며, 더 큰 해시 세트에 대한 히트는 메모리 대역폭에 의해 제한된 속도로 진행됩니다.

---

계속 진행하기 전에 다음 사항을 고려하십시오. 성능에 대해 왜 걱정하십니까? 이 수표는 얼마나 자주 호출됩니까?

가능한 솔루션 :

• 목록이 이미 정렬 된 경우 .NET Framework java.util.Collections.binarySearch와 동일한 성능 특성을 제공하는을 사용할 수 있습니다 java.util.TreeSet.

• 그렇지 않으면 java.util.HashSetO (1)의 성능 특성으로 사용할 수 있습니다 . 아직 계산되지 않은 문자열에 대한 해시 코드를 계산하는 것은 m =을 사용하는 O (m) 연산입니다 string.length(). 또한 해시 테이블은 주어진로드 팩터에 도달 할 때까지만 잘 작동합니다. 즉, 해시 테이블은 일반 목록보다 더 많은 메모리를 사용합니다. HashSet에서 사용하는 기본로드 비율은 .75입니다. 즉, 내부적으로 1e6 개체에 대한 HashSet은 1.3e6 항목이있는 배열을 사용합니다.

• HashSet이 작동하지 않는 경우 (예 : 많은 해시 충돌이 있거나 메모리가 부족하거나 삽입이 많아서) Trie 사용을 고려하십시오 . Trie에서 조회는 m = 인 경우 O (m)의 최악의 복잡성을가집니다 string.length(). Trie는 또한 유용 할 수있는 몇 가지 추가 이점이 있습니다. 예를 들어, 검색 문자열에 가장 근접하게 적합 할 수 있습니다 . 그러나 최고의 코드는 코드가 없다는 것을 명심하십시오. 따라서 혜택이 비용을 능가하는 경우에만 자체 Trie 구현을 수행하십시오.

• 보다 복잡한 쿼리 (예 : 하위 문자열 또는 정규식 일치)를 원하는 경우 데이터베이스 사용을 고려하십시오.

---

나는 Set대부분의 경우 HashSet괜찮습니다.

---

이렇게 엄청난 수의 문자열을 사용하면 즉시 Trie를 생각합니다 . 더 제한된 문자 세트 (예 : 문자) 및 / 또는 많은 문자열의 시작이 겹칠 때 더 잘 작동합니다.

---

여기서 운동을 한 결과는 내 결과입니다.

private static final int TEST_CYCLES = 4000;
private static final long RAND_ELEMENT_COUNT = 1000000l;
private static final int RAND_STR_LEN = 20;
//Mean time
/*
Array list:18.55425
Array list not contains:17.113
Hash set:5.0E-4
Hash set not contains:7.5E-4
*/

나는 숫자가 스스로를 말해 준다고 믿습니다. 해시 세트의 조회 시간이 훨씬 빠릅니다.

---

이렇게 많은 양의 문자열이있는 경우 가장 좋은 기회는 데이터베이스를 사용하는 것입니다. MySQL을 찾으십시오.

---

아마도 이것은 귀하의 경우에 필요하지 않지만 공간 효율적인 확률 알고리즘이 있다는 것을 아는 것이 유용하다고 생각합니다. 예를 들어 Bloom filter .

---

String뿐만 아니라 고유 한 항목이 필요한 경우에 Set 을 사용할 수 있습니다 .

항목 유형이 기본 또는 래퍼이면 상관하지 않을 수 있습니다. 그러나 클래스 인 경우 두 가지 메서드를 재정의해야합니다.

1. 해시 코드()
2. 같음 ()

---

때로는 개체가 목록 / 집합에 있는지 확인하고 동시에 목록 / 집합을 정렬하려는 경우도 있습니다. 열거 형이나 반복자를 사용하지 않고 쉽게 개체를 검색하려는 경우 ArrayList<String>및 HashMap<String, Integer>. 목록은지도에 의해 뒷받침됩니다.

최근에 한 몇 가지 작업의 예 :

public class NodeKey<K> implements Serializable, Cloneable{
private static final long serialVersionUID = -634779076519943311L;

private NodeKey<K> parent;
private List<K> children = new ArrayList<K>();
private Map<K, Integer> childrenToListMap = new HashMap<K, Integer>();

public NodeKey() {}

public NodeKey(Collection<? extends K> c){
    List<K> childHierarchy = new ArrayList<K>(c);
    K childLevel0 = childHierarchy.remove(0);

    if(!childrenToListMap.containsKey(childLevel0)){
        children.add(childLevel0);
        childrenToListMap.put(childLevel0, children.size()-1);
    }

    ...

이 경우 매개 변수 K는 String당신을위한 것입니다. 맵 ( childrenToMapList) Strings은 목록 ( children)에 키로 삽입 된 저장을 저장 하고 맵 값은 목록의 인덱스 위치입니다.

The reason for the list and the map is so that you can retrieve indexed values of the list, without having to do an iteration over a HashSet<String>.

참고URL : https://stackoverflow.com/questions/3307549/fastest-way-to-check-if-a-liststring-contains-a-unique-string