Counting items in a list of records efficiently

Question

Given a list of records, I'm trying to get a count of how many records each author has written. The obvious way is to use a map, with the keys being the authors' names and the values the count that gets incremented. But is there a more efficient way to do this, without doing a lookup every iteration?

If I know the authors in advance, I can just create variables for each author and increment them without a lookup and then finally create the map once I'm done reading input. However I only know a few of the authors in the data.

Thanks in advance.

Answer 1

Your solution based on a map of authors' names to counts is a pretty good one (if you use a HashMap, it'll have an overall average time complexity of O(n)).

If I were you, I'd use this approach until I can demonstrate that it's unsuitable (too slow, uses too much memory etc) and only then would I try to replace it with something that addresses the problem that's arisen. In all likelihood, that day would never come.

Answer 2

Average case for lookup with a Java HashMap is going to be O(1), meaning it won't drastically increase your running time.

Unless you're really trying to squeeze everything out of this, you're likely just over-optimizing.

Answer 3

If number of authors is relatively small, compared to total number of records, hash lookup will be the most effective technique in such situation.

More affective algorithms are possible, if records are already sorted (or you have some sort of btree index, which is sorted structure also).

Answer 4

You might find TObjectIntHashMap more efficient than HashMap but both will be fairly efficient. You should be able to scan 100K records in a few milli-seconds. If that is not fast enough, you can maintain a Map of counts when you add/update/remove a record so you can just look this up.