Java: как найти 10 самых распространенных String + frequency в ArrayList?

Question

Я пытаюсь найти 10 самых распространенных строк в ArrayList + их счет (частота появления).

Как я могу это сделать с наилучшей временной сложностью?

Ниже код находит наиболее общее слово + частоты в виде (String = INT)

Е.Г. a = 2

public static Entry<String, Integer> get10MostCommon(WordStream words) { 

    ArrayList<String> list = new ArrayList<String>(); 
    Map<String, Integer> stringsCount = new HashMap<>(); 
    Map.Entry<String, Integer> mostRepeated = null; 

    for (String i : words) { 
     list.add(i); 
    } 

    for (String s : list) { 
     Integer c = stringsCount.get(s); 
     if (c == null) 
     c = new Integer(0); 
     c++; 
     stringsCount.put(s, c); 
    } 

    for (Map.Entry<String, Integer> e : stringsCount.entrySet()) { 
     if (mostRepeated == null || mostRepeated.getValue() < e.getValue()) 
     mostRepeated = e; 
    } 
    return mostRepeated; 
    } 

Answer 1

Вы могли бы сделать это в два этапа, с использованием Java 8 потоков:

Map<String, Long> map = list.stream() 
     .collect(Collectors.groupingBy(w -> w, Collectors.counting())); 

List<Map.Entry<String, Long>> result = map.entrySet().stream() 
     .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder())) 
     .limit(10) 
     .collect(Collectors.toList()); 

Первый поток MAPS слов их частоте используя Collectors.groupingBy() вместе с Collectors.counting().

Это возвращает карту, записи которой передаются и сортируются по значению записи карты в обратном порядке. Затем поток ограничен, чтобы сохранить только 10 элементов, которые, наконец, собраны в список.

Answer 2

Я бы разложил это на два метода.

Первый не будет делать ничего, кроме создания карты частот слов.

Второй будет возвращать n наивысших частотных слов.

Что должен делать ваш код, если вы запрашиваете n наиболее часто встречающихся слов, но Map имеет меньше, чем это число в качестве ключей?

Это ваш шанс попробовать JDK 8 lambdas и эффективно фильтровать частоту Map.

import java.util.Arrays; 
import java.util.LinkedHashMap; 
import java.util.List; 
import java.util.Map; 

/** 
* Calculate word frequencies from a List of words 
* User: mduffy 
* Date: 3/14/2016 
* Time: 1:07 PM 
* @link http://stackoverflow.com/questions/35992891/java-how-to-find-top-10-most-common-string-frequency-in-arraylist/35993252#35993252 
*/ 
public class WordFrequencyDemo { 

    public static void main(String[] args) { 
     List<String> words = Arrays.asList(args); 
     Map<String, Integer> wordFrequencies = WordFrequencyDemo.getWordFrequencies(words); 
     System.out.println(wordFrequencies); 
    } 

    public static Map<String, Integer> getWordFrequencies(List<String> words) { 
     Map<String, Integer> wordFrequencies = new LinkedHashMap<String, Integer>(); 
     if (words != null) { 
      for (String word : words) { 
       if (word != null) { 
        word = word.trim(); 
        if (!wordFrequencies.containsKey(word)) { 
         wordFrequencies.put(word, 0); 
        } 
        int count = wordFrequencies.get(word); 
        wordFrequencies.put(word, ++count); 
       } 
      } 
     } 
     return wordFrequencies; 
    } 
} 

Answer 3

Вы всегда будете использовать хэш для подсчета слов первого, который будет использования конечно O (п) и O (п) пространство. Это первый шаг.

Тогда вы узнаете, как выбрать верхнюю часть 10. Вы можете использовать сортировку, которая занимает не менее O (nlogn). Но есть лучший способ, который заключается в использовании кучи. Скажем, k = 10 в вашем случае. Вам нужно добавить парный объект слова и его частоту в минимальную кучу размера k, где мы используем частоту в качестве ключа для мини-кучи. Если куча заполнена, удалите минимальный элемент (верхний) из кучи и добавьте новую пару слов-слов только в том случае, если частота этого слова имеет частоту, большую, чем верхнее слово в куче. После того, как мы сканировали все слова на карте, и куча была должным образом обновлена, элементы, содержащиеся в мини-куче, являются самыми большими. Ниже приведен пример кода. Просто немного измените код, чтобы взять ArrayList, а не массив, который сделает вашу работу.

class Pair { 
    String key; 
    int value; 

    Pair(String key, int value) { 
     this.key = key; 
     this.value = value; 
    } 
} 

public class Solution { 
    /** 
    * @param words an array of string 
    * @param k an integer 
    * @return an array of string 
    */ 

    private Comparator<Pair> pairComparator = new Comparator<Pair>() { 
     public int compare(Pair left, Pair right) { 
      if (left.value != right.value) { 
       return left.value - right.value; 
      } 
      return right.key.compareTo(left.key); 
     } 
    }; 

    public String[] topKFrequentWords(String[] words, int k) { 
     if (k == 0) { 
      return new String[0]; 
     } 

     HashMap<String, Integer> counter = new HashMap<>(); 
     for (String word : words) { 
      if (counter.containsKey(word)) { 
       counter.put(word, counter.get(word) + 1); 
      } else { 
       counter.put(word, 1); 
      } 
     } 

     PriorityQueue<Pair> Q = new PriorityQueue<Pair>(k, pairComparator); 
     for (String word : counter.keySet()) { 
      Pair peak = Q.peek(); 
      Pair newPair = new Pair(word, counter.get(word)); 
      if (Q.size() < k) { 
       Q.add(newPair); 
      } else if (pairComparator.compare(newPair, peak) > 0) { 
       Q.poll(); 
       Q.add(new Pair(word, counter.get(word))); 
      } 
     } 

     String[] result = new String[k]; 
     int index = 0; 
     while (!Q.isEmpty()) { 
      result[index++] = Q.poll().key; 
     } 

     // reverse 
     for (int i = 0; i < index/2; i++) { 
      String temp = result[i]; 
      result[i] = result[index - i - 1]; 
      result[index - i - 1] = temp; 
     } 

     return result; 
    } 
} 

Answer 4

Вам придется повторять слова от начала до конца, по крайней мере один раз, так что вы не закончится лучше, чем O(n), где n является размер слова. Затем происходит извлечение m верхних записей (10 в вашем случае). Предположим, у вас есть k уникальных слов в ваших n слов в общей сложности, чтобы найти m топ записей, вам нужно запустить max Поиск m раз на k записей, что приводит к m * k операций, что дает вам O(m * n) в худшем случае (когда все слова являются уникальными) , В общей сложности это дает вам O(n * (m + 1)) операций, или O(11 * n) в вашем случае (10 раз max поиск плюс начальный запуск группировки).

Вот моя попытка (JDK8 +, не тестировался):

public static Collection<Map.Entry<String, Integer>> topOccurences(List<String> words, int topThreshold) { 
    Map<String, Integer> occurences = new HashMap<>(); 
    words.stream().forEach((word) -> { 
     int count = 1; 
     if (occurences.containsKey(word)) { 
      count = occurences.get(word) + 1; 
     } 
     occurences.put(word, count); 
    }); 

    List<Map.Entry<String, Integer>> entries = new LinkedList<>(occurences.entrySet()); 
    List<Map.Entry<String, Integer>> tops = new LinkedList<>(); 
    Comparator<Map.Entry<String, Integer>> valueComp = Comparator.comparing((Map.Entry<String, Integer> t) -> t.getValue()); 
    int topcount = 0; 
    while (topcount < topThreshold && !entries.isEmpty()) { 
     Map.Entry<String, Integer> max = Collections.max(entries, valueComp); 
     tops.add(max); 
     entries.remove(max); 
     topcount++; 
    } 
    return tops; 
}