[jira] [Created] (LANG-1176) Improve ArrayUtils removeElements

["jefferyyuan (JIRA)" <ji...@apache.org>]

jefferyyuan created LANG-1176:
---------------------------------

             Summary: Improve ArrayUtils removeElements
                 Key: LANG-1176
                 URL: https://issues.apache.org/jira/browse/LANG-1176
             Project: Commons Lang
          Issue Type: Bug
          Components: lang.*
    Affects Versions: 3.4
            Reporter: jefferyyuan
            Priority: Minor
             Fix For: 3.5


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();
        for (final Map.Entry<Integer, MutableInt> e : occurrences.entrySet()) {
            final Integer v = e.getKey();
            int found = 0;
            for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
                found = indexOf(array, v.intValue(), found);
                if (found < 0) {
                    break;
                }
                toRemove.set(found++);
            }
        }



--
This message was sent by Atlassian JIRA
(v6.3.4#6332)