어떤 데이터 구조를 사용 하시겠습니까 : TreeMap 또는 HashMap? (자바)
이 질문에 이미 답변이 있습니다.
설명 | 텍스트 파일을 읽고 텍스트에서 단어가 나오는 횟수와 함께 각 고유 단어를 알파벳 순서로 인쇄하는 Java 프로그램입니다.
프로그램은 Map<String, Integer>단어와 해당 발생 빈도를 저장할 유형의 변수를 선언해야합니다 . 하지만 어떤 구체적인 유형입니까? TreeMap<String, Number>또는 HashMap<String, Number>?
입력은 소문자로 변환되어야합니다.
단어에 다음 문자가 포함되어 있지 않습니다. \t\t\n]f.,!?:;\"()'
예제 출력 |
Word Frequency
a 1
and 5
appearances 1
as 1
.
.
.
비고 | 나는 대략 두 줄의 코드로 Perl에서 이것에 대한 우아한 해결책을 보았다. 그러나 Java로보고 싶습니다.
편집 : 예, 이러한 구조 중 하나를 사용하는 구현을 보여주는 것이 유용합니다 (Java에서).
TreeMap 은 "알파벳 순서로"요구 사항이 있기 때문에 당연한 것 같습니다. HashMap은 반복 할 때 순서가 없습니다. TreeMap은 자연 키 순서로 반복됩니다.
편집 : Konrad의 의견이 "HashMap을 사용한 다음 정렬"을 제안했을 수 있습니다. 처음에는 N 개의 반복이 있지만 중복으로 인해 마지막에 K <= N 개의 키가 있기 때문에 좋습니다. 키가 적을 때까지 값 비싼 비트 (정렬)를 저장하는 것이 좋습니다. 작지만 일정하지 않은 정렬을 유지하는 것보다 더 적을 수 있습니다.
그렇게 말하면서 저는 잠시 제 대답을 고수하고 있습니다. 목표를 달성하는 가장 간단한 방법 이기 때문 입니다. 우리는 OP가 특히 성능에 대해 걱정하고 있다는 것을 실제로 알지 못하지만, 질문은 그가 우아함과 간결함에 대해 우려하고 있음을 의미합니다. TreeMap을 사용하면 이것을 매우 간단하게 만들 수 있습니다. 성능이 실제로 문제라면 TreeMap 또는 HashMap보다 더 나은 공격 방법이있을 수 있습니다. :)
TreeMap이 이미 정렬되어 있기 때문에 TreeMap이 HashMap을 능가합니다.
그러나 더 적절한 데이터 구조 인 백 사용을 고려할 수 있습니다. Commons Collections- 및 TreeBag 클래스를 참조하십시오 .
여기에는 최적화 된 내부 구조와 API가 있습니다.
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
편집 : HashMap 대 TreeMap 성능에 대한 질문은 Jon-HashMap 및 정렬이 더 빠를 수 있지만 TreeBag가 더 쉽습니다. 가방도 마찬가지입니다. HashBag와 TreeBag가 있습니다. 구현 (가변 정수 사용)에 따라 bag은 Integer의 동등한 일반 맵보다 성능이 우수해야합니다. 확실히 알 수있는 유일한 방법은 성능 질문과 마찬가지로 테스트하는 것입니다.
꽤 많은 사람들이 "TreeMap 조회가 필요합니다 O(n log n)" 라고 말하는 것을 봅니다 !! 어째서?
나는 그것이 어떻게 구현되었는지 모르지만 내 머릿속에는 O(log n).
이는 트리에서 조회가에서 수행 될 수 있기 때문입니다 O(log n). 항목을 삽입 할 때마다 전체 트리를 정렬하지 않습니다. 그것이 나무를 사용하는 전체 아이디어입니다!
따라서 원래 질문으로 돌아가서 비교 수치는 다음과 같습니다.
HashMap 접근 방식 : O(n + k log k) 평균 사례, 최악의 경우 훨씬 더 클 수 있음
TreeMap 접근 방식 : O(k + n log k) 최악의 경우
여기서 n = 텍스트의 단어 수, k = 텍스트의 고유 단어 수.
해시 맵은 훨씬 빨라야합니다. 최종적으로 항목을 정렬하는 방법에 따라 컨테이너를 선택해서는 안됩니다. 끝에있는 (단어, 빈도) 쌍 목록을 정렬하십시오. 일반적으로 파일에있는 단어보다 정렬 할 이러한 쌍이 적으므로 해시 맵을 사용하는 점근 적 (실제) 성능이 더 좋습니다.
TreeMap<String,Number>유형이있는 변수 에을 할당 할 수 없습니다 Map<String,Integer>. Double, Long등을 TreeMap<String,Number>. 나는에서 값을 "얻을"때 Map<String,Integer>, 그것은을해야합니다 Integer.
i18n 문제, 메모리 제약 및 오류 처리를 완전히 무시하면 다음과 같습니다.
class Counter {
public static void main(String... argv)
throws Exception
{
FileChannel fc = new FileInputStream(argv[0]).getChannel();
ByteBuffer bb = fc.map(FileChannel.MapMode.READ_ONLY, 0, fc.size());
CharBuffer cb = Charset.defaultCharset().decode(bb);
Pattern p = Pattern.compile("[^ \t\r\n\f.,!?:;\"()']+");
Map<String, Integer> counts = new TreeMap<String, Integer>();
Matcher m = p.matcher(cb);
while (m.find()) {
String word = m.group();
Integer count = counts.get(word);
count = (count == null) ? 1 : count + 1;
counts.put(word, count);
}
fc.close();
for (Map.Entry<String, Integer> e : counts.entrySet()) {
System.out.printf("%s: %d%n", e.getKey(), e.getValue());
}
}
}
"키가 이미 존재하면 HashMap과 동일한 성능을 갖습니다." -그건 명백한 잘못입니다. HashMap에는 O (1) 삽입과 TreeMap O (n log n)가 있습니다. 테이블에 있는지 확인하려면 적어도 n log n 검사가 필요합니다!
import java.io.BufferedReader;
import java.io.DataInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.ObjectInputStream.GetField;
import java.util.Iterator;
import java.util.Map;
import java.util.StringTokenizer;
import java.util.TreeMap;
public class TreeMapExample {
public static void main (String args[]){
Map<String,Integer> tm = new TreeMap<String,Integer>();
try {
FileInputStream fis = new FileInputStream("Test.txt");
DataInputStream in = new DataInputStream(fis);
BufferedReader br = new BufferedReader(new InputStreamReader(in));
String line;
int countValue = 1;
while((line = br.readLine())!= null ){
line = line.replaceAll("[-+.^:;,()\"\\[\\]]","");
StringTokenizer st = new StringTokenizer(line, " ");
while(st.hasMoreTokens()){
String nextElement = (String) st.nextElement();
if(tm.size()>0 && tm.containsKey(nextElement)){
int val = 0;
if(tm.get(nextElement)!= null){
val = (Integer) tm.get(nextElement);
val = val+1;
}
tm.put(nextElement, val);
}else{
tm.put(nextElement, 1);
}
}
}
for(Map.Entry<String,Integer> entry : tm.entrySet()) {
System.out.println(entry.getKey() + " : " + entry.getValue());
}
} catch (FileNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
} catch (IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
}
내 의견으로는 이러한 방법으로, 더 나은 사용을 위해 HashBag 에서 아파치 코 몬즈 컬렉션 또는 HashMultiset 에서 구아바 또는 HashBag 에서 이클립스 컬렉션 (formaly GS 모음 ) 또는 다음 클래스 :
Order | Guava | Apache | Eclipse(GS) | JDK analog
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Not define | HashMultiset | HashBag | HashBag | HashMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Sorted | TreeMultiset | TreeBag | TreeBag | TreeMap<String, Integer>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Linked |LinkedHashMultiset| - | - | LinkedHashMap<String, Integere>
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent & | ConcurrentHash- |Synchroniz-|Synchroniz- | Collections.synchronizedMap(
not define | Multiset | edBag | edBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Concurrent | - |Synchroniz-|Synchroniz- | Collections.synchronizedSorted-
and sorted | |edSortedBag| edSortedBag | Map(TreeMap<>))
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableMultiset|Unmodifiab-|Unmodifiab- | Collections.unmodifiableMap(
not define | | leBag | leBag | HashMap<String, Integer>)
─────────────┼──────────────────┼───────────┼─────────────┼─────────────
Immutable and| ImmutableSorted- |Unmodifiab-|Unmodifiab- | Collections.unmodifiableSorted-
sorted | Multiset |leSortedBag| leSortedBag | Map(TreeMap<String, Integer>))
────────────────────────────────────────────────────────────────────────
예 :
1. Apache에서 SynchronizedSortedBag 사용 :
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Bag bag = SynchronizedSortedBag.synchronizedBag(new TreeBag(Arrays.asList(INPUT_TEXT.split(" "))));
// Print count words
System.out.println(bag); // print [1:All!,2:Hello,1:Hi,2:World!]- in natural (alphabet) order
// Print all unique words
System.out.println(bag.uniqueSet()); // print [All!, Hello, Hi, World!]- in natural (alphabet) order
// Print count occurrences of words
System.out.println("Hello = " + bag.getCount("Hello")); // print 2
System.out.println("World = " + bag.getCount("World!")); // print 2
System.out.println("All = " + bag.getCount("All!")); // print 1
System.out.println("Hi = " + bag.getCount("Hi")); // print 1
System.out.println("Empty = " + bag.getCount("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.uniqueSet().size()); //print 4
2. Eclipse (GC)에서 TreeBag 사용 :
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
MutableSortedBag<String> bag = TreeBag.newBag(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(bag); // print [All!, Hello, Hello, Hi, World!, World!]- in natural order
// Print all unique words
System.out.println(bag.toSortedSet()); // print [All!, Hello, Hi, World!]- in natural order
// Print count occurrences of words
System.out.println("Hello = " + bag.occurrencesOf("Hello")); // print 2
System.out.println("World = " + bag.occurrencesOf("World!")); // print 2
System.out.println("All = " + bag.occurrencesOf("All!")); // print 1
System.out.println("Hi = " + bag.occurrencesOf("Hi")); // print 1
System.out.println("Empty = " + bag.occurrencesOf("Empty")); // print 0
// Print count all words
System.out.println(bag.size()); //print 6
// Print count unique words
System.out.println(bag.toSet().size()); //print 4
3. Guava의 LinkedHashMultiset 사용 :
// Parse text to separate words
String INPUT_TEXT = "Hello World! Hello All! Hi World!";
// Create Multiset
Multiset<String> multiset = LinkedHashMultiset.create(Arrays.asList(INPUT_TEXT.split(" ")));
// Print count words
System.out.println(multiset); // print [Hello x 2, World! x 2, All!, Hi]- in predictable iteration order
// Print all unique words
System.out.println(multiset.elementSet()); // print [Hello, World!, All!, Hi] - in predictable iteration order
// Print count occurrences of words
System.out.println("Hello = " + multiset.count("Hello")); // print 2
System.out.println("World = " + multiset.count("World!")); // print 2
System.out.println("All = " + multiset.count("All!")); // print 1
System.out.println("Hi = " + multiset.count("Hi")); // print 1
System.out.println("Empty = " + multiset.count("Empty")); // print 0
// Print count all words
System.out.println(multiset.size()); //print 6
// Print count unique words
System.out.println(multiset.elementSet().size()); //print 4
내 github 프로젝트에서 더 많은 예제를 찾을 수 있습니다.
확실히 TreeMap을 선택합니다.
- TreeMap은 삽입시 자동으로 새 키를 정렬하므로 나중에 정렬 할 필요가 없습니다.
- 키가 이미 존재하면 HashMap과 동일한 성능을 갖습니다.
TreeSet은 내부적으로 TreeMap을 사용하므로 TreeMap을 직접 사용하지 마십시오.
속도 요구 사항에 따라 Trie를 사용할 수도 있습니다 . 그러나 TreeMap이 충분히 빠르면 그중 하나를 구현할 필요가 없습니다.
데이터 구조에 대한 추가 또는 삭제 빈도를 고려하십시오. TreeMap이 높으면 이상적이지 않습니다. 기존 항목 nLn에 대한 검색 외에도 빈번한 재조정이 수행됩니다.
반면에 해시 구조는 메모리에서 약간 화려합니다 (초과 할당). 그 총알을 물 수 있다면 해시 구조로 가서 필요할 때 정렬하십시오.
다음은 텍스트 파일을 읽고 키를 기준으로 정렬 한 다음 값을 기준으로 정렬하는 Java 예제입니다. 파일에서 단어의 발생 수에 따라.
public class SortFileWords {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<String, Integer>();
ValueCompare vc = new ValueCompare(map);
TreeMap<String, Integer> sorted_map = new TreeMap<String, Integer>(map);
List<String> list = new ArrayList<>();
Scanner sc;
try {
sc = new Scanner(new File("c:\\ReadMe1.txt"));
while (sc.hasNext()) {
list.add(sc.next());
}
sc.close();
} catch (FileNotFoundException e) {
e.printStackTrace();
}
for (String s : list) {
if (map.containsKey(s)) {
map.put(s, map.get(s) + 1);
} else
map.put(s, 1);
}
System.out.println("Unsorted map: " + map);
sorted_map.putAll(map);
System.out.println("Sorted map on keys: " + sorted_map);
TreeMap<String, Integer> sorted_value_map = new TreeMap<>(vc);
sorted_value_map.putAll(map);
System.out.println("Sorted map on values: " + sorted_value_map);
}
}
class ValueCompare implements Comparator<String> {
Map<String, Integer> map;
public ValueCompare(Map<String, Integer> map) {
this.map = map;
}
@Override
public int compare(String s1, String s2) {
if (map.get(s1) >= map.get(s2))
return -1;
else
return 1;
}
}
TreeSet을 사용하지 않는 이유는 무엇 입니까?
정의에 따라 "중복 요소를 포함하지 않는 컬렉션"인 집합이라는 점을 제외하면 TreeMap과 동일한 순서 지정 개념입니다.
문제 설명에서 세트가 필요한 것처럼 들리지만 함께 매핑하는 키와 값을 볼 수 없습니다.
이 클래스는 TreeMap 인스턴스가 지원하는 Set 인터페이스를 구현합니다. 이 클래스는 사용되는 생성자에 따라 정렬 된 집합이 요소의 자연스러운 순서 (Comparable 참조) 또는 집합 생성시 제공된 비교기에 따라 정렬되는 오름차순 요소 순서가되도록 보장합니다.
기본적으로 요구 사항에 따라 다릅니다. 때로는 해시 맵이 좋은 경우도 있습니다. 하지만 해시 맵을 사용하는 것이 더 낫습니다.
'IT이야기' 카테고리의 다른 글
| 'AuthController'를 활성화하는 동안 'Microsoft.AspNetCore.Identity.UserManager'유형에 대한 서비스를 확인할 수 없습니다. (0) | 2021.04.13 |
|---|---|
| UISearchController iOS 11 사용자 정의 (0) | 2021.04.13 |
| 레일에서-%>와 %>의 차이 (0) | 2021.04.13 |
| StringBuilder 대 StringWriter 및 PrintWriter의 문자열 어셈블리 (0) | 2021.04.13 |
| Mercurial에서 병합을 취소하고 나중에 해당 분기로 다시 병합 (0) | 2021.04.13 |