HashMap을 이용한 중복 찾기

Question

해쉬 맵 를 이용해서 중복을 찾아 중복된 값만 ArrayList에 넣는 문제를 풀고 있습니다.비교대상으로는 Brute force pair comparison 이라고, 하나의 값을 그 이 후 값과 하나씩 대조해서 중복된 값을 뽑아내는 방법으로 제가 만든 코드와 속도 비교를 하고 있습니다. for( int i = 0; i < strings.size() - 1; i++ ) { // For each string in strings String curr_string = strings.get(i); // Grab the current string for( int j = i + 1; j < strings.size(); j++ ) { // For each string *after* curr_string String check_string = strings.get(j); // Grab the string to check against if( curr_string.compareTo(check_string) == 0 ) { // Is a duplicate boolean is_already_dup = false; // Separate flag for duplicate in duplicates for( int k = 0; k < duplicates.size(); k++ ) { // Checking if duplicates already has this string if( curr_string.compareTo(duplicates.get(k) ) == 0 ) { // If a dup in dups is_already_dup = true; // Flag that it's a dup of a dup } } if( is_already_dup == false ) { // If it's a a dup, but not already in dups duplicates.add(curr_string); // Add to duplicates array } } } } return duplicates;일단 해쉬 맵을 써야하는게 기본 조건이고 인풋 될 데이터는 {one, two, three, one, one} 이런식으로 키 값만 있습니다. strings = {one, two, three, one, one}; ArrayList duplicates = new ArrayList<>(); HashMap map = new HashMap<>(); for (int i = 0; i < strings.size(); i++) { String key = strings.get(i); if (map.containsKey(key)) { if (map.get(key) == null) { duplicates.add(key); } map.put(key, "d"); } else { map.put(key, null); } } return duplicates; 로 구현해봤습니다. 확실히 100개 이상의 데이터일때는 속도가 향상이 있지만, 10개 미만이거나 중복이 없는 경우에는 더 느린 결과를 봤습니다. 시간 복잡도는 Brute force 가 O(N^2) 이고, 해쉬 맵을 이용한 것은 O(1) (단순히 insert만 고려한것) 인것 같은데 왜 10개 미만, 중복이 없는 상태에서 더 느린지 잘 모르겠습니다.또 혹시 다른 좋은 아이디어가 있으시면 조언 부탁드립니다. * 아래에 결과를 첨부합니다. ----- Beginning String Dup Tests ----- -- Running Tests on Detector algorithm: Brute Force Check Alles! No Dups | Brute Force Check Alles! | PASS | Time (ns): 32316 Super Short | Brute Force Check Alles! | PASS | Time (ns): 9250 Small | Brute Force Check Alles! | PASS | Time (ns): 21673 One Hundred | Brute Force Check Alles! | PASS | Time (ns): 899914 One Thousand | Brute Force Check Alles! | PASS | Time (ns): 19092508 -- DONE with Detector Brute Force Check Alles! -- Running Tests on Detector algorithm: HashMap O(1) Hotrod! No Dups | HashMap O(1) Hotrod! | PASS | Time (ns): 89595 Super Short | HashMap O(1) Hotrod! | PASS | Time (ns): 21501 Small | HashMap O(1) Hotrod! | PASS | Time (ns): 24295 One Hundred | HashMap O(1) Hotrod! | PASS | Time (ns): 245005 One Thousand | HashMap O(1) Hotrod! | PASS | Time (ns): 2126520 -- DONE with Detector HashMap O(1) Hotrod!

LichKing · Answer

10~100개 정도 속도 비교는 거의 의미없을거같은데요..코드는 둘다 올려주시는게 좋을거같네요

AndrewJK · Answer

&#64;LichKing 답변감사합니다 일단 Brute force 코드도 올려봤습니다.

satis · Answer

for (int i &#61;0 ; i < strings.size(); i&#43;&#43;){ String key &#61; strings.get(i); if(map.containKey(key)){ duplicates.add(key); map.put(key, &#34;d&#34;); }} 좀더 짧게 바꿔보았습니다. 10개 미만의 경우 직접 하나하나 비교하는 알고리즘이 연산이 더 적겠네요.해시맵은 해시 알고리즘으로 key의 해시코드를 만들며, 그 해시코드를 가지고 keymap arrayindex 연산(contains, get, put 메서드)을 해야합니다.적은 수면 당연 문자열 직접 비교가 빠릅니다.

AndrewJK · Answer

&#64;satis 제시해주신 코드 감사합니다. 제가 깜빡하고 말씀 안 드린게 duplicates안에서는 중복으로 들어가면 안되는 조건이 있습니다. 위의 예시로 보면 duplicates &#61; {one} 만 리턴이 되어야 합니다.ArrayList 대신 HashSet으로 중복값을 저장하고 해쉬셋을 다시 어레이리스트로 변환하여 봤지만 모든 경우에서 더 느렸습니다.

Whislter · Answer

해쉬가 한번 접근할때 O(1)이지만 N개를 돌면 결국 O(N)이죠.그리고 O(N)이라고 무조건 O(N2) 보다 빠를순 없죠for(int i &#61; 0 ; i < 10; i&#43;&#43;){ print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); print(i); } for(int i &#61; 0 ; i < 10; i&#43;&#43;){ for(int j &#61; 0 ; j < 10; j&#43;&#43;){ print(i,j); } }}해쉬 내부가 어떻게 구현되었는지 잘은 모르겠지만 1번 호출이 아래코드 10번 도는것보다 비효율적이고 100번도는것보단 효율적이여서 그렇게 나오나보네요. for( int j &#61; i &#43; 1; j < strings.size(); j&#43;&#43; ) { // For each string *after* curr_string String check_string &#61; strings.get(j); // Grab the string to check against if( curr_string.compareTo(check_string) &#61;&#61; 0 ) { // Is a duplicate boolean is_already_dup &#61; false; // Separate flag for duplicate in duplicates for( int k &#61; 0; k < duplicates.size(); k&#43;&#43; ) { // Checking if duplicates already has this string if( curr_string.compareTo(duplicates.get(k) ) &#61;&#61; 0 ) { // If a dup in dups is_already_dup &#61; true; // Flag that it's a dup of a dup } } if( is_already_dup &#61;&#61; false ) { // If it's a a dup, but not already in dups duplicates.add(curr_string); // Add to duplicates array } } }

HashMap을 이용한 중복 찾기

5개의 답변

#duplicate 목록