0
$\begingroup$

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.

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

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.