Какую структуру данных вы бы использовали:TreeMap или HashMap?(Джава)
https://stackoverflow.com/questions/302371
-
08-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Описание | Программа на 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 выполняет итерацию в порядке естественного ключа.
РЕДАКТИРОВАТЬ: Я думаю, что комментарий Конрада, возможно, предлагал " использовать HashMap, а затем сортировать. " Это хорошо, потому что, хотя у нас изначально будет N итераций, к концу у нас будет K & Lt; = N ключей из-за дубликатов. Мы могли бы также сохранить дорогой бит (сортировку) до конца, когда у нас будет меньше ключей, чем получить небольшой, но непостоянный удар по сохранению сортировки на ходу.
Сказав это, я придерживаюсь своего ответа на данный момент: потому что это самый простой способ достижения цели. Мы действительно не знаем, что OP особенно беспокоится о производительности, но вопрос подразумевает, что он обеспокоен элегантностью и краткостью. Использование TreeMap делает это невероятно коротким, что мне нравится. Я подозреваю, что если производительность действительно является проблемой, может быть лучший способ атаковать ее, чем TreeMap или HashMap:)
Другие советы
TreeMap превосходит HashMap, потому что TreeMap уже отсортирован для вас.
Однако вы можете рассмотреть возможность использования более подходящей структуры данных - пакета. Увидеть Коллекции общин - и TreeBag class:
Это имеет хорошую оптимизированную внутреннюю структуру и API:
bag.add("big")
bag.add("small")
bag.add("big")
int count = bag.getCount("big")
РЕДАКТИРОВАТЬ: Jon - HashMap ответил на вопрос о производительности HashMap и TreeMap, и сортировка может быть быстрее (попробуйте!), но TreeBag проще. То же самое относится и к сумкам. Существует HashBag, а также TreeBag. На основе реализации (использует изменяемое целое число) пакет должен превосходить эквивалентную простую карту Integer. Единственный способ узнать наверняка - это проверить, как и любой вопрос производительности.
Я вижу, что довольно много людей говорят "!", поиск по TreeMap занимает O(n log n) & "!! Как так?
Я не знаю, как это было реализовано, но в моей голове это занимает O(log n).
Это потому, что поиск в дереве можно выполнить в O(n + k log k). Вы не сортируете все дерево каждый раз, когда вставляете в него элемент. Вот и вся идея использования дерева!
Следовательно, возвращаясь к исходному вопросу, цифры для сравнения получаются:
Подход HashMap: O(k + n log k) в среднем случае, наихудший случай может быть намного больше
Подход TreeMap: <=> наихудший случай
где n = количество слов в тексте, k = количество отдельных слов в тексте.
Хэш-карта должна быть намного быстрее. Вы не должны выбирать контейнер в зависимости от того, как вы хотите, чтобы элементы были расположены в конце концов; Просто отсортируйте список (слово, частота) -пар в конце. Обычно таких пар будет меньше, чем слов в файлах, поэтому асимптотическая (и реальная) производительность с хэш-картой будет лучше.
Вы не можете присвоить TreeMap<String,Number> переменной типа Map<String,Integer>. Double, Long и т. д. можно & поставить " в 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 проверок журнала 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();
}
}
}
Для этого способа, на мой взгляд, лучше использовать ХэшБэг от Коллекции Apache Commons или ХэшМультисет от Гуава или ХэшБэг от Коллекции затмений (формально Коллекции 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. Использование SynchronizedSortedBag от Apache:
// 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.Использование TreeBag из Eclipse (GC):
// 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. Использование LinkedHashMultiset из Guava:
// 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, за исключением того, что это Set - который, по определению, является " Коллекция, которая не содержит повторяющихся элементов " ;.
Из вашего описания проблемы звучит так, как будто вам нужен набор, я не вижу, какие ключи и значения вы отображаете вместе.
Этот класс реализует интерфейс Set, поддерживаемый экземпляром TreeMap. Этот класс гарантирует, что отсортированный набор будет в порядке возрастания элементов, отсортирован в соответствии с естественным порядком элементов (см. Comparable) или компаратором, предоставленным во время создания набора, в зависимости от того, какой конструктор используется.
В основном это зависит от требования. Иногда карта хеша хороша, иногда карта дерева. но хэш-карту лучше использовать только для ограничения издержек на ее сортировку.
