CODEWITHSUNDEEP
javaalgorithmdata-structures
caasdads
caasdads

Reputation: 419

How to count occurrencies of an entity in a list with repetitions?

I have a list of 5-digit combinations (possibly with repetitions: doubles, triples, etc). I need to count how often every combination appears in that list. Actually, a combination is a unique BitSet with respective bits set (if combination contains digit 5 then 5th bit is set, etc.)

Given list 

12345
34578
12345
98710
12345

I shall get

12345 -> 3
34578 -> 1
98710 -> 1

Is there anything ready to solve this task? Like I add 12345 string to this data structure three times and then I query it for 12345 (respective Bitset object) and it returns 3 as number of occurrencies. I thought of Apache Commons Frequency class, but it does not help.

Upvotes: 2

Views: 231

Answers (3)

danidemi
danidemi

Reputation: 4706

You can use the plain Collections.frequency method that does exactly that.

import java.util.List;
import static java.util.Collections.frequency;

List list = List.of("12345", "34578", "12345", "98710", "12345");
System.out.println( frequency(list, "12345") );

Upvotes: 0

Alex Shesterov
Alex Shesterov

Reputation: 27565

If you are looking for a ready-to-use data structure which stores elements with counts, then Guava's Multiset does exactly that.

If you just need to convert a list to a map of counts, please read on.

You can convert a list to a map of counts in a single statement using Java 8 Streams API: 

final var list = List.of("12345", "34578", "12345", "98710", "12345");

final var counts = list.stream()
    .collect(Collectors.toMap(
        Function.identity(), // Map keys are list elements
        value -> 1, // Map values are counts, a single item counts "1"
        (count1, count2) -> count1 + count2 // On duplicate keys, counts are added
    ));

Under the hood, this solution uses a hash map (elements to counts) as a data structure.

You may also use the groupingBy collector, as Peter Lawrey kindly suggested: 

final var list = List.of("12345", "34578", "12345", "98710", "12345");

final var counts = list.stream()
    .collect(Collectors.groupingBy(
        Function.identity(), // Group the elements by equality relation
        Collectors.counting() // Map values are counts of elements in the equality groups
    ));

Sometimes (while learning) it's beneficial to implement everything "by hand" to understand the algorithms. So here a version without Java 8 goodies like streams, collectors and new map methods like Map.compute():

final List<Stream> list = List.of("12345", "34578", "12345", "98710", "12345"); // Use ArrayList if you're below Java 9

final Map<String, Integer> counts = new HashMap<>();
for (final String item : list) {
    // Note: I'm deliberately NOT using Map.compute() here
    // to demonstrate how to do everything "manually"
    Integer count = counts.get(item);
    if (count == null) {
        count = 0;
    }
    counts.put(item, count + 1);
}

Upvotes: 5

user4695271
user4695271

Reputation:

Assuming your list are strings (if not you might need a "comparator"). Loop over the entire list adding the elements to a HashMap and a counter of themselves; but right before doing that, check if the element in question exists, updating the counter accordingly.

Eventually, Java streams can help too.

Upvotes: 0

Related Questions