Home > Software engineering >  Generating a TreeMap of Frequencies for each Number in a List
Generating a TreeMap of Frequencies for each Number in a List

Time:07-31

I have a method which is meant to return a TreeMap with the keys being the numbers and the values being the frequencies of these numbers in the given array:

public TreeMap<Integer, Integer> getFrequencyCount(List<Integer> array) {
    Collections.sort(array);
    TreeMap<Integer, Integer> a = new TreeMap<>();

    for (int i = 0; i < array.size(); i  ){
        if (array.indexOf(array.get(i)) == 0 || array.get(i) != array.get(i - 1)){
            a.put(array.get(i), 1);
            
        } else if (array.get(i) == array.get(i - 1)) {
            int votes = a.get(array.get(i));
            a.put(array.get(i), votes   1);
        }   
    }
    return a;
}

Every value is correct except for the first value of the map, which is always 1. I can't figure out why it's happens.

CodePudding user response:

the first value of the map, which is always 1

That happens because when an element is equal to the first element in the sorted list - indexOf() == 0 in the snippet below, the value associated with it will always be 1. The second part of this condition is also fishy.

if (array.indexOf(array.get(i)) == 0 || array.get(i) != array.get(i - 1)) {
   a.put(array.get(i), 1);
}

I guess instead the condition should be if (!a.containsKey(array.get(i)))

There's a few more issues with your code:

  • Don't compare objects using == or != unless you don't need to make sure that two references point to the same object. Instances of Integer are objects. To compare values of the objects, use equals() method.

  • Don't confuse array and ArrayList (and avoid using confusing names). Array is the simplest data container built-in into the language, it has no behavior. On the other hand, ArrayList is a Collection, backed by an array (and there are some others apart from ArrayList), which offers lots of useful methods.

  • Write your code against interfaces. We have a contract NavigableMap, use it as a type when you need TreeMap.

  • By sorting the list data, you're not getting a performance advantage. If your goal was to try implementing this task by iterating over the sorted list - that's fine. But mind that method get() and put() have a time complexity of O(n) for TreeMap. If you want to go this route (meaning to sort data in the list) it would be chipper to store the results into LinkedHashMap and then dump it into TreeMap (method putAll() is capable of taking advantage of the previously sorted data of the map passed into it).

Here's an alternative way of implementing this task using Java 8 method merge():

public NavigableMap<Integer, Integer> getFrequencyCount(List<Integer> list) {

    Map<Integer, Integer> frequencies = new HashMap<>();

    for (Integer next: list) {
        frequencies.merge(next, 1, Integer::sum);
    }

    return new TreeMap<>(frequencies);
}

And if you're comfortable with streams, you can make use of one of the flavors of Collectors.toMap():

public NavigableMap<Integer, Integer> getFrequencyCount(List<Integer> list) {

    return list.stream()
        .collect(Collectors.toMap(
            Function.identity(),
            i -> 1,
            Integer::sum,
            TreeMap::new
        ));
}

CodePudding user response:

There is an easier way to do this:

TreeMap<Integer, Long> map = array.stream()
        .collect(Collectors.groupingBy(
                Function.identity(),
                TreeMap::new,
                Collectors.counting()
        ));
  • Related