Efficient Mode of a Distribution

[Ike]

If I have an ArrayList of Integers, what would be an efficient means of
determining which of those Integers occured the most times in that
ArrayList? For example, suppose I have an ArrayList of 100 items, which can
contain an Integer of any value between, say, 0 and 10,000. How can I
efficiently determine which Integer(s) in the ArrayList occur with greatest
frequency?

Thanks, Ike

 

[Eric Sosman]

If I have an ArrayList of Integers, what would be an efficient means of
determining which of those Integers occured the most times in that
ArrayList? For example, suppose I have an ArrayList of 100 items, which can
contain an Integer of any value between, say, 0 and 10,000. How can I
efficiently determine which Integer(s) in the ArrayList occur with greatest
frequency?

Method 1: Sort the list to bring groups of identical
values together, then make one pass over the list to find
the group sizes and pick the group of greatest size.

Method 2: Use a HashMap that maps each Integer value
to a count of the number of times it's been encountered.
Make one pass over the list to populate the map, then make
one pass over the map to find the Integer with the greatest
count.

Method 2a: Use an ordinary int[] array of counts instead
of the map in Method 2. This assumes that the range of
Integer values is not too large and is known (approximately)
in advance.

 

[Filip Larsen]

Eric Sosman wrote

Method 2: Use a HashMap that maps each Integer value
to a count of the number of times it's been encountered.
Make one pass over the list to populate the map, then make
one pass over the map to find the Integer with the greatest
count.

Let me add that in some situations it might be more efficient to update
information about the highest count so far in the first pass and skip
the second pass completely. This would be the case, for instance, if the
counts are held in an int array of a much larger size than the number of
samples.


Regards,