Clever Geek Handbook

The fastest collection contains a method with 5-10 integers

I have a small question: I have a collection with 5-10 integers. They don't change or anything else, but they are permanent here. So my question is, which Collection would be the best / fastest for the contains method: ArrayList, LinkedList, Vector, HashSet or ...?

+3


source to share


2 answers


Due to the way computers load data (CPU optimization assumes you are going to use nearby memory addresses)
Using small arrays will probably be the fastest solution here.

If the actual numbers are small, Java will optimize Integer (non primitives), so using an ArrayList should produce similar results using the int [] function. If you use a larger number (not -128 to 127), int [] will give better results.

The overhead of using a Hashset will probably cost more than it actually is, 5-10 are compared to an int [] array.



And you may want to include these numbers in a set of IF conditions.

All of the above will only have an impact on the fact that you perform these comparisons at least 100,000 times per second. Anything less than that, it doesn't really matter.

To summarize:
Code <int [] array <ArrayList <HashSet

+1


source


I would promise that the best results can be achieved with perfect hashing , assuming that you want to spend some non-negligible time creating the set. There are some general ways to calculate this hash, but in your case they might be worse than a simple array scan due to their fixed overhead.

In case the creation time is irrelevant, consider an algorithm similar to this answer of mine where an expression of the form



TABLE[(MULTIPLIER * c) >> SHIFT] == c

used to check if c

the set contains . It MULTIPLIER

takes some time to find the right one , but the test is very fast.

+1


source






More articles:


All Articles