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

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

     [ https://issues.apache.org/jira/browse/LANG-1176?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Sebb resolved LANG-1176.
------------------------
    Resolution: Fixed

> Improve ArrayUtils removeElements time complexity to O(n)
> ---------------------------------------------------------
>
>                 Key: LANG-1176
>                 URL: https://issues.apache.org/jira/browse/LANG-1176
>             Project: Commons Lang
>          Issue Type: Improvement
>          Components: lang.*
>    Affects Versions: 3.4
>            Reporter: jefferyyuan
>            Priority: Minor
>             Fix For: 3.5
>
>   Original Estimate: 24h
>  Remaining Estimate: 24h
>
> 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.
> {code:java}
>         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++);
>             }
>         }
> {code}
> We can just scan the origin array once to get all indexes that needed to be removed.
> {code:java}
>         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);
>             }
>         }
> {code}



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