You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@commons.apache.org by pa...@apache.org on 2016/05/22 15:25:18 UTC
[2/2] [lang] LANG-1176: Improve ArrayUtils removeElements time
complexity to O(n) (closes #144)
LANG-1176: Improve ArrayUtils removeElements time complexity to O(n) (closes #144)
based on patch submitted by Jeffery Yuan
Project: http://git-wip-us.apache.org/repos/asf/commons-lang/repo
Commit: http://git-wip-us.apache.org/repos/asf/commons-lang/commit/5b223744
Tree: http://git-wip-us.apache.org/repos/asf/commons-lang/tree/5b223744
Diff: http://git-wip-us.apache.org/repos/asf/commons-lang/diff/5b223744
Branch: refs/heads/master
Commit: 5b223744b49d3ceac9608959d2db82bbadb47897
Parents: f8b1f6e
Author: pascalschumacher <pa...@gmx.net>
Authored: Thu May 19 21:52:51 2016 +0200
Committer: pascalschumacher <pa...@gmx.net>
Committed: Sun May 22 17:23:46 2016 +0200
----------------------------------------------------------------------
src/changes/changes.xml | 1 +
.../org/apache/commons/lang3/ArrayUtils.java | 144 +++++++++----------
2 files changed, 73 insertions(+), 72 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/commons-lang/blob/5b223744/src/changes/changes.xml
----------------------------------------------------------------------
diff --git a/src/changes/changes.xml b/src/changes/changes.xml
index 4dd3cbf..f334131 100644
--- a/src/changes/changes.xml
+++ b/src/changes/changes.xml
@@ -22,6 +22,7 @@
<body>
<release version="3.5" date="tba" description="tba">
+ <action issue="LANG-1176" type="update" dev="pschumacher" due-to="Jeffery Yuan">Improve ArrayUtils removeElements time complexity to O(n)</action>
<action issue="LANG-1234" type="update" dev="pschumacher" due-to="Jonatan J�nsson">getLevenshteinDistance with a threshold: optimize implementation if the strings lengths differ more than the threshold</action>
<action issue="LANG-1168" type="add" dev="pschumacher" due-to="pschumacher">Add SystemUtils.IS_OS_WINDOWS_10 property</action>
<action issue="LANG-1232" type="fix" dev="pschumacher" due-to="Nick Manley">DiffBuilder: Add null check on fieldName when appending Object or Object[]</action>
http://git-wip-us.apache.org/repos/asf/commons-lang/blob/5b223744/src/main/java/org/apache/commons/lang3/ArrayUtils.java
----------------------------------------------------------------------
diff --git a/src/main/java/org/apache/commons/lang3/ArrayUtils.java b/src/main/java/org/apache/commons/lang3/ArrayUtils.java
index 6fe185d..0d6a02a 100644
--- a/src/main/java/org/apache/commons/lang3/ArrayUtils.java
+++ b/src/main/java/org/apache/commons/lang3/ArrayUtils.java
@@ -6581,15 +6581,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<T, MutableInt> e : occurrences.entrySet()) {
- final T v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v, found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final T key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
@SuppressWarnings("unchecked") // removeAll() always creates an array of the same type as its input
@@ -6673,15 +6673,15 @@ public class ArrayUtils {
}
}
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;
+ for (int i = 0; i < array.length; i++) {
+ final byte key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (byte[]) removeAll(array, toRemove);
@@ -6762,15 +6762,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<Short, MutableInt> e : occurrences.entrySet()) {
- final Short v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v.shortValue(), found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final short key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (short[]) removeAll(array, toRemove);
@@ -6851,15 +6851,15 @@ public class ArrayUtils {
}
}
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;
+ 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(found++);
+ toRemove.set(i);
}
}
return (int[]) removeAll(array, toRemove);
@@ -6940,15 +6940,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<Character, MutableInt> e : occurrences.entrySet()) {
- final Character v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v.charValue(), found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final char key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (char[]) removeAll(array, toRemove);
@@ -7029,15 +7029,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<Long, MutableInt> e : occurrences.entrySet()) {
- final Long v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v.longValue(), found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final long key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (long[]) removeAll(array, toRemove);
@@ -7118,15 +7118,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<Float, MutableInt> e : occurrences.entrySet()) {
- final Float v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v.floatValue(), found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final float key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (float[]) removeAll(array, toRemove);
@@ -7207,15 +7207,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<Double, MutableInt> e : occurrences.entrySet()) {
- final Double v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v.doubleValue(), found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final double key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (double[]) removeAll(array, toRemove);
@@ -7292,15 +7292,15 @@ public class ArrayUtils {
}
}
final BitSet toRemove = new BitSet();
- for (final Map.Entry<Boolean, MutableInt> e : occurrences.entrySet()) {
- final Boolean v = e.getKey();
- int found = 0;
- for (int i = 0, ct = e.getValue().intValue(); i < ct; i++) {
- found = indexOf(array, v.booleanValue(), found);
- if (found < 0) {
- break;
+ for (int i = 0; i < array.length; i++) {
+ final boolean key = array[i];
+ final MutableInt count = occurrences.get(key);
+ if (count != null) {
+ count.decrement();
+ if (count.intValue() == 0) {
+ occurrences.remove(key);
}
- toRemove.set(found++);
+ toRemove.set(i);
}
}
return (boolean[]) removeAll(array, toRemove);