Java : 대규모 중복 검색을 위해 해시 세트 최적화

Question

많은 트윗을 처리중인 프로젝트에서 작업하고 있습니다. 목표는 내가 처리 할 때 중복을 제거하는 것입니다. 트위터 ID는 형식의 문자열로 제공됩니다. "166471306949304320"

나는이 동안 HashSet<String>을 사용해 왔는데 잠시 동안 잘 작동합니다. 그러나 내가 약 1 천만 가지 항목에 도달 할 때까지 나는 심하게 휘청 거려 결국 GC 오류를 일으켰습니다. 아마도 아마도 다시 해싱에서 발생했을 것입니다. 나는

tweetids = new HashSet<String>(220000,0.80F);

와 더 나은 크기/부하를 정의하는 시도하고는 조금 더 멀리를 얻을 수 있지만 여전히 (약 1000 만은 처리 한 배를 복용에 의한) 극심한 느립니다. 이것을 어떻게 최적화 할 수 있습니까? 마지막으로 얼마나 많은 항목이 있어야하는지에 대한 대략적인 아이디어가 있다고 가정하면 (이 경우 약 20-22 백만), 두 번 또는 세 번 다시 충돌하는 HashSet을 생성해야하며, 그렇지 않은 경우에는 오버 헤드가 발생합니다. 너무 많은 시간 벌칙이 부과됩니까? String을 사용하지 않거나 다른 HashCode 함수 (String의 특정 인스턴스에 대해이 작업을 수행하는 방법을 모르겠다)를 정의하면 더 쉽게 작동할까요? 구현 코드의이 부분은 아래와 같습니다. 당신의 권고

tweetids = new HashSet<String>(220000,0.80F); // in constructor 
duplicates = 0; 
... 
// In loop: For(each tweet) 
String twid = (String) tweet_twitter_data.get("id"); 
// Check that we have not processed this tweet already 
if (!(tweetids.add(twid))){ 
    duplicates++; 
    continue; 
} 

솔루션

덕분에, 나는 그것을 해결했다. 문제는 해시 표현에 필요한 메모리 양이었습니다. 첫째, HashSet<String>은 방대한 숫자로 String.hashCode()이 엄청 났기 때문에 간단하고 엄청나게 열성적이었습니다. 다음으로 Trie를 시도했지만, 100 만 개가 넘는 항목에서 충돌했습니다. 배열을 재 할당하는 것은 문제가있었습니다. 나는 더 나은 효과를 내기 위해 HashSet<Long>을 사용했으나 거의 만들었지 만 속도가 떨어지며 마침내 처리의 마지막 단계 (약 1900 만 건)에 추락했습니다. 해결책은 표준 라이브러리를 벗어나 Trove을 사용하는 것입니다. 그것은 중복을 전혀 점검하지 않는 것보다 2200 만개의 기록을 몇 분 빨리 마쳤습니다. 최종 구현은 간단했다,이 모습 :

import gnu.trove.set.hash.TLongHashSet; 
... 
    TLongHashSet tweetids; // class variable 
... 
    tweetids = new TLongHashSet(23000000,0.80F); // in constructor 
... 
    // inside for(each record) 
    String twid = (String) tweet_twitter_data.get("id"); 
    if (!(tweetids.add(Long.parseLong(twid)))) { 
     duplicates++; 
     continue; 
    } 

Answer 1

Java 콜렉션 프레임 워크를 넘어서는 것을 볼 수 있습니다. 나는 일부 메모리 집약적 인 처리를 완료했습니다 당신은 몇 가지 문제

1. 큰 HashMaps을하고 해시 세트의 버킷의 수는 원인 오버 헤드 (메모리)를 많이하려고에 직면하게 될 것이다. 일종의 사용자 지정 해시 함수와 모듈로 등을 사용하여 영향을 줄 수 있습니다. 50000
2. 문자열은 Java에서 16 비트 문자를 사용하여 표현됩니다. 대부분의 스크립트에서 utf-8로 인코딩 된 바이트 배열을 사용하면 반으로 줄일 수 있습니다.
3. 일반적으로 HashMaps는 매우 낭비적인 데이터 구조이며 HashSet은 기본적으로 그 둘레의 얇은 래퍼입니다.

이 점을 감안할 때 대안을 찾기 위해 trove 또는 guava를 살펴보십시오. 또한 ID는 long처럼 보입니다. 그것들은 문자열 표현보다 꽤 작은 64 비트입니다.

블룸 필터를 사용하는 것이 좋습니다 (구아바는 괜찮은 구현이 있습니다). 블룸 필터는 무언가가 포함되어있는 경우 확실하게 (100 % 미만의) 확실한 확실성을 지니고 있음을 알려줍니다. 일부 디스크 기반 솔루션 (예 : 데이터베이스, mapdb, mecached 등)과 결합하면 정상적으로 작동합니다. 들어오는 새 ID를 버퍼링하고, 일괄 처리로 작성하고, 블룸 필터를 사용하여 데이터베이스를 조사해야하므로 대부분의 경우 비싼 조회를 피할 수 있습니다.

Answer 2

, 간단한 해보지 않은 가능성이 바보 같은 제안 :

Map<String, Set<String>> sets = new HashMap<String, Set<String>>(); 
String tweetId = "166471306949304320"; 
sets.put(tweetId.substr(0, 5), new HashSet<String>()); 
sets.get(tweetId.substr(0, 5)).add(tweetId); 
assert(sets.containsKey(tweetId.substr(0, 5)) && sets.get(tweetId.substr(0, 5)).contains(tweetId)); 

: 트윗의 ID의 첫 번째/마지막 N 문자 색인 설정의지도를 만듭니다

쉽게 해싱 공간의 최대 크기를 적당한 값 이하로 유지할 수 있습니다.

Answer 3

문자열의 존재를 찾고 있다면 Trie (프리픽스 트리라고도 함)을 사용해 보시기 바랍니다. Trie가 사용하는 전체 공간은 HashSet보다 작아야하며 문자열 조회에는 더 빠릅니다.

가장 큰 단점은 해시와 같이 저장된 선형 구조가 아니라 트리를로드 할 때 하드 디스크에서 사용될 때 속도가 느려질 수 있다는 것입니다. RAM 내부에 보관할 수 있는지 확인하십시오.

필자가 제공 한 링크는이 접근법의 장단점 목록입니다.

* Jilles Van Gurp가 제안한 블룸 필터는 훌륭한 고속 프리 필터입니다.