[
https://issues.apache.org/jira/browse/LANG-1176?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
jefferyyuan updated LANG-1176:
------------------------------
Summary: Improve ArrayUtils removeElements time complexity to O(n) (was:
Improve ArrayUtils removeElements)
> 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: Bug
> 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.
> 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)
