Java HashMap을 많이 사용할수록 더 많은 성능 저하 - 심지어 안정적인 크기로 -

Question

거대한 코퍼스 텍스트를 스캔하고 단어 빈도를 계산하고 싶습니다. (실제로 N-gram 빈도는 NLP/IR에 익숙한 사람들을위한 것입니다.). 나는 이것을 위해 Java HashMap을 사용한다. 그러면 텍스트가 한 줄씩 처리됩니다. 각 줄마다 단어를 추출하고 각 단어에 대해 해시 맵에서 해당 빈도를 업데이트합니다.

문제는이 프로세스가 느리고 느려집니다. 예를 들어, 약 100k 라인/초를 처리하여 시작하고 성능이 곧 떨어지기 시작합니다. 약 2 천 8 백만 라인 이후, 성능은 16k 라인/초로 떨어졌으며 물론 떨어지고 있습니다.

가장 먼저 떠오르는 것은 해시 맵에서 너무 많은 항목으로 인해 모든 풋과 모든 것이 점점 느려지 게된다는 것이 었습니다. 그래서 내가 시도한 것은 해시 맵에서 가장 자주 (100k) 빈번 항목 만 유지하는 것이 었습니다. 이것은 주파수를 단어에 매핑 한 두 번째 맵을 사용하여 수행되었습니다 (여기에서와 같이 : Automatically sorted by values map in Java)

이것은 일반적으로 훨씬 빠르게 수행됩니다. (56k 라인/초에서 시작했지만, 28mil 라인에 도달 할 때까지 성능은 36.5k 라인/초로 떨어졌습니다). 그러나 이것은 또한 훨씬 더 느린 속도로 계속 떨어졌습니다. 그러나 사실은 계속 떨어지고 있습니다.

해시 맵의 크기가 동일하게 유지되는 이유는 무엇일까요? 이것이 가비지 컬렉터와 관련이 있다고 생각하십니까? 의미, 내가 퍼팅을 계속하고 hashmaps에서 /로 객체를 제거한다는 사실이 메모리 나 다른 것을 파편화하는 것입니까? 또는 해시 함수 문제 일 수 있습니까? 문자열을 사용하고 있기 때문에 해싱 함수는 문자열에 대한 Java의 기본 해시 함수입니다.

http://pastebin.com/P8S6Sj86

참고 : 나는 자바 안돼서 그래서 당신의 대답에있는 정교 내가 사용하는 것이 좋습니다 환영

Answer 1

보다 더 여기에

는 상기 작업을 수행 내 코드의 일부이다 자바 VisualVM은 프로파일 링을 수행합니다. 이것은 Java와 함께 제공됩니다 - 명령 행으로 가서 jvisualvm을 입력하여 실행하십시오. 이렇게하면 메모리 변동이 문제가되는지 또는 특정 유형의 개체가 수십만 번 만들어지는지를 쉽게 알 수 있습니다.

코드를 여러 가지 방법으로 분해하면 어떤 메서드를 실행하는 데 너무 오래 걸릴 지 알 수 있습니다.

불필요하게 내부 루프에 많은 수의 개체가 생성되어 있음을 확인했습니다. 이것은 주요 원인이 아닐지라도 성능에 도움이되지는 않을 것입니다. 예를 들어

: 운영 체제 또는 IDE에 따라

System.out.println(numItems + " items counted"); 

:

float avg = new Float(sumItems)/new Float (freqMap.size()); 

는

단지

float avg = (float)sumItems/freqMap.size(); 

도 골칫거리가 될 수 코드의 또 다른 조각이 있어야한다 콘솔에 100,000 라인을 쓰려면 상당한 시간이 필요합니다. 대신, 1000 개 항목마다 진행 상황 업데이트를 작성하십시오.

Answer 2

제안 : 당신이 당신의 해시 맵에 저장하고있는 객체에 대한 사용자 정의 hashCode 메소드를 구현

보십시오. 여기에 몇 가지 링크가 있습니다 : 제공된 링크에서

Java HashMap performance optimization/alternative

http://www.ibm.com/developerworks/java/library/j-jtp05273/index.html

http://www.javamex.com/tutorials/collections/hash_function_guidelines.shtml

Bad idea to use String key in HashMap?