[LANG-1176] Improve ArrayUtils removeElements time complexity to O(n)

• Type: Improvement
• Status: Closed
• Priority: Minor
• Resolution: Fixed
• Affects Version/s: 3.4
• Fix Version/s: 3.5
• Component/s: lang.*
• Assignee: Pascal Schumacher
• Reporter: jefferyyuan
• Created: 24/Oct/15 07:03
• Updated: 19/Oct/16 07:00
• Resolved: 24/May/16 14:59

Description

The current ArrayUtils removeElements implementation is not efficient when try to get all indexes that needed to be removed.

It's O(m*n): n is the length of origin array, m is the unique count of toBeRemoved.

        final BitSet toRemove = new BitSet();
        for (final Map.Entry<Byte, MutableInt> e : occurrences.entrySet()) {
            final Byte v = e.getKey();
            int found = 0;
            for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
                found = indexOf(array, v.byteValue(), found);
                if (found < 0) {
                    break;
                }
                toRemove.set(found++);
            }
        }

We can just scan the origin array once to get all indexes that needed to be removed.

        final BitSet toRemove = new BitSet();

        // the only change here, time complexity changed to O(n)
        for (int i = 0; i < array.length; i++) {
            final int key = array[i];

            final MutableInt count = occurrences.get(key);
            if (count != null) {
                count.decrement();
                if (count.intValue() == 0) {
                    occurrences.remove(key);
                }
                toRemove.set(i);
            }
        }

Issue Links

• is related to: LANG-1235 Add decrementAndGet/incrementAndGet to MutableInt class
• links to: GitHub Pull Request #144