Java에서 메모리를 효율적으로 구현하십시오

10GB 파일을 읽고 파일에서 가장 자주 나오는 문구를 찾아야합니다. 스캐너를 사용하여 청크로 파일을 읽고이 구문을 트라이 데이터 구조에 저장하고 있습니다. 나중에 해당 구문을 검색하여 효율적인 검색을 위해 trie 데이터 구조를 사용했습니다. 아래 그림과 같이 Trie 을 java에서 Hashmap을 사용하여 구현했습니다.Java에서 메모리를 효율적으로 구현하십시오

class TrieNode { 
     char data; 
     Map<Character, TrieNode> children = new HashMap<>(); 
     boolean isLeafNode; 
     int positionMinHeap = -1; 
     int frequency; 

     TrieNode() { 

     } 

     TrieNode(char data) { 
      this.data = data; 
     } 

    }

그러나이 솔루션은 많은 힙 공간을 차지합니다. 파일에서 모든 구가 다른 경우 Trie는 엄청난 양의 공간을 차지합니다. Trie를 메모리 효율적인 방식으로 구현할 수있는 다른 방법이 있습니까?

출처

2016-10-23 Neha Arora

저는 top-k [스트림 요약] (http://www.cse.ust.hk/~raywong/comp5331/References/EfficientComputationOfFrequentAndTop-kElementsInDataStreams.pdf) 알고리즘을 사용합니다. 예를 들어, CountMinSketch를 사용하여 주파수를 추적하고 메모리에서 k 번째로만 유지하고 높은 주파수로 교체하면 감지됩니다. –

기수 트리 구현은 어떻습니까? https://en.wikipedia.org/wiki/Radix_tree –

C++ 및 JNI 바인딩을 두려워하지 않으면 최적화 된 솔루션을 선택할 수있는 선택의 폭이 넓습니다. 내가 시도하는 것이 좋습니다 것 마리사을-트라이 : 나는 얼마 전에 몇 가지 다른 라이브러리를 시도했다 (불행히도 나는 지금 다른 사람을 기억하지 않는 것) 내 데이터 marisa-을 설정

https://github.com/s-yata/marisa-trie/tree/master

trie는 다른 C++ 라이브러리와 비교할 때 성능과 메모리 사용간에 매우 좋은 균형을 이루었습니다.

또한 데이터가 커지면 (일부 성능을 희생시킴으로써) 메모리 매핑 IO 인터페이스의 이점을 얻을 수 있습니다.

출처

2016-10-25 10:01:06 benjist

Java에서 메모리를 효율적으로 구현하십시오

답변

관련 문제