Telling unique values in a short array

I have thousands of short arrays (length less than 9) holding integers. These numbers can be identical with high probability (in many arrays there are two triples of equal numbers). I need to remove the duplicates in each array, as efficiently as possible.

An obvious solution is to sort using a fast sort (such as straight selection), then to compress with a linear pass. But is there a smarter way ?

Worth to know: the identical values are often consecutive (but not always). In-place processing is preferred.

• Is there a range/constrain in which the integer elements in each array belong to? Commented Feb 12, 2023 at 10:42
• @ArunMadhav: no, they can span the whole 32 bits range.
– user16034
Commented Feb 12, 2023 at 10:42
• Doing what you described will take around $10^{-5}-10^{-4}$ seconds. Is it a problem? Commented Feb 12, 2023 at 19:36
• @Dmitry: yes, my time scale is milliseconds total time. So optimizations matter.
– user16034
Commented Feb 12, 2023 at 19:39
• Then the fastest approach is probably to just write the relevant parts in assembler. Commented Feb 12, 2023 at 19:39

After posting my question, I realized that it contains the answer. As there can be many duplicates, the size of the compressed array tends to be quite short. So

• it is advisable to avoid eliminating the duplicates as soon as possible. A modified straight insertion sort could do, the modification consisting of just dropping an element when it is found to be a duplicate,

• there is little benefit in keeping the values sorted. (The cost of keeping sorted order is that one might have to shift elements many times.)

Hence I will try this solution:

• consider every element in turn,

• search backward among the elements previously considered and kept,

• if the same value is found, drop the element; otherwise append it to those that were kept.

This is easily implemented in-place.