4
\$\begingroup\$

With the following code, I want to count the Vote objects from a collection, filtering on one of their fields, Candidate.

I have the feeling that I can get this done much more efficiently.

// Get all votes from the database
Collection<Vote> votes = getVotesFromCategoryAndRegion(c, r);

// Filter distinct candidates
Collection<Candidate> candidates = votes
            .stream()
            .map(Vote::getCandidate)
            .distinct()
            .collect(Collectors.toList());


List<VoteResult> results = new ArrayList<>();


// If vote.candidate == candidate, candidates's vote counter ++
for (Candidate currentCandidate : candidates) {
      int currentVoteCount = 0;
      for (Vote v : votes)
          if (v.getCandidate().equals(currentCandidate))
              currentVoteCount++;

      results.add(new VoteResult(currentCandidate, currentVoteCount));
    }


    Collections.sort(results);
    return results;

If you have any suggestions, please tell.

\$\endgroup\$
2
\$\begingroup\$

can get this done much more efficiently.

Yes, I agree.

If C candidates each receive an average of V votes (total of C * V votes cast), then your complexity is quadratic in number of candidates: O(C * C * V).

There's nothing so bad about making a pair of linear passes, to accumulate candidates and then votes.

But there's no need, you can make a single pass to do both. Create a HashMap, iterate over all votes, probe the map to see if you should add a zero entry for a new candidate, and then increment the entry so you'll have vote totals at the end.

\$\endgroup\$
2
\$\begingroup\$

You were right that this can be made in just one pass. You are not aware of Collectors.groupingBy.

It is basically a one-liner:

    Map<Candidate, Long> results1 = votes.stream()
            .collect(Collectors.groupingBy(
                    Vote::getCandidate,
                    TreeMap::new,
                    Collectors.counting()));

    // Results are sorted, but by the key of the TreeMap: the Candidate name.
    results1.entrySet().stream().forEach(e ->
            System.out.printf("%30s: %d%n", e.getKey(), e.getValue()));

    List<VoteResult> results = results1.entrySet().stream()
            .map(e -> new VoteResult(e.getKey(), Math.toIntExact(e.getValue())))
            .collect(Collectors.toList());
    // Results are sorted by VoteResult, which uses the vote count.
    Collections.sort(results);
    results.forEach(vr -> System.out.printf("%30s: %d%n", vr.getCandidate(), vr.getVoteCount()));

Note that Candidate must implement Comparable and that it must also define equals() and hashCode. VoteResult must also implement Comparable.

\$\endgroup\$
1
\$\begingroup\$

Instead of looping over every candidate and every vote you could just loop over the votes and have a Map<Candidate, Integer> with vote count for every candidate. This way your code would have a complexity of \$O(n)\$ instead of \$O(n^2)\$ (at least I think so, I'm not sure about this but it should greatly improve performance nonetheless). Another advantage of this approach is that you wouldn't need to distinct all of these candidates which improves performance even more.

Here's more less how it could be improved (untested)

Collection<Vote> votes = getVotes(x, y);
Map<Candidate, Integer> votesPerCandidate = new HashMap<>();

for (Vote vote : votes) {
    int votes = votesPerCandidate.getOrDefault(vote.getCandidate(), 0);
    votesPerCandidate.put(vote.getCandidate(), votes + 1);
}

List<VoteResult> results = new ArrayList<>();
for (Map.Entry<Candidate, Integer> result : votesPerCandidate.entrySet()) {
    results.add(new VoteResult(result.getKey(), result.getValue());
}

Collections.sort(results);
return results;
\$\endgroup\$
  • \$\begingroup\$ In Java 8, the body of the first loop can be simplified to votesPerCandidate.merge(vote.getCandidate(), 1, (v, one) -> v + one); \$\endgroup\$ – BenC Aug 26 '17 at 0:30
  • \$\begingroup\$ @BenC What does the (v, one) -> v + one part exactly do? \$\endgroup\$ – mrkflp Aug 26 '17 at 7:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.