You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@reef.apache.org by ma...@apache.org on 2015/12/18 00:12:44 UTC
reef git commit: [REEF-1073] Improve
ConstructorDefImpl.equalsIgnoreOrder algorithm
Repository: reef
Updated Branches:
refs/heads/master f13ab65c8 -> 6338420b5
[REEF-1073] Improve ConstructorDefImpl.equalsIgnoreOrder algorithm
This replaces O(N^2) comparison of two arrays with O(N log N) one.
JIRA:
[REEF-1073](https://issues.apache.org/jira/browse/REEF-1073)
Pull Request:
This closes #726
Project: http://git-wip-us.apache.org/repos/asf/reef/repo
Commit: http://git-wip-us.apache.org/repos/asf/reef/commit/6338420b
Tree: http://git-wip-us.apache.org/repos/asf/reef/tree/6338420b
Diff: http://git-wip-us.apache.org/repos/asf/reef/diff/6338420b
Branch: refs/heads/master
Commit: 6338420b533cab7583734b48e0bc6899f2ddcc04
Parents: f13ab65
Author: Dongjoon Hyun <do...@apache.org>
Authored: Sat Dec 12 16:37:36 2015 +0900
Committer: Mariia Mykhailova <ma...@apache.org>
Committed: Thu Dec 17 15:11:15 2015 -0800
----------------------------------------------------------------------
.../types/ConstructorDefImpl.java | 32 ++++++++++++--------
1 file changed, 19 insertions(+), 13 deletions(-)
----------------------------------------------------------------------
http://git-wip-us.apache.org/repos/asf/reef/blob/6338420b/lang/java/reef-tang/tang/src/main/java/org/apache/reef/tang/implementation/types/ConstructorDefImpl.java
----------------------------------------------------------------------
diff --git a/lang/java/reef-tang/tang/src/main/java/org/apache/reef/tang/implementation/types/ConstructorDefImpl.java b/lang/java/reef-tang/tang/src/main/java/org/apache/reef/tang/implementation/types/ConstructorDefImpl.java
index c774947..0115c51 100644
--- a/lang/java/reef-tang/tang/src/main/java/org/apache/reef/tang/implementation/types/ConstructorDefImpl.java
+++ b/lang/java/reef-tang/tang/src/main/java/org/apache/reef/tang/implementation/types/ConstructorDefImpl.java
@@ -24,6 +24,7 @@ import org.apache.reef.tang.types.ConstructorArg;
import org.apache.reef.tang.types.ConstructorDef;
import java.util.Arrays;
+import java.util.HashMap;
public class ConstructorDefImpl<T> implements ConstructorDef<T> {
private final ConstructorArg[] args;
@@ -94,24 +95,17 @@ public class ConstructorDefImpl<T> implements ConstructorDef<T> {
* Check to see if two boundConstructors take indistinguishable arguments. If
* so (and they are in the same class), then this would lead to ambiguous
* injection targets, and we want to fail fast.
- * <p>
- * TODO could be faster. Currently O(n^2) in number of parameters.
*
* @param def
* @return
*/
private boolean equalsIgnoreOrder(final ConstructorDef<?> def) {
- if (getArgs().length != def.getArgs().length) {
- return false;
+ HashMap map = new HashMap();
+ for (ConstructorArg a : def.getArgs()) {
+ map.put(a.getName(), null);
}
- for (int i = 0; i < getArgs().length; i++) {
- boolean found = false;
- for (int j = 0; j < def.getArgs().length; j++) {
- if (getArgs()[i].getName().equals(def.getArgs()[j].getName())) {
- found = true;
- }
- }
- if (!found) {
+ for (ConstructorArg a : getArgs()) {
+ if (!map.containsKey(a.getName())) {
return false;
}
}
@@ -126,7 +120,19 @@ public class ConstructorDefImpl<T> implements ConstructorDef<T> {
if (o == null || getClass() != o.getClass()) {
return false;
}
- return equalsIgnoreOrder((ConstructorDef<?>) o);
+
+ int length = getArgs().length;
+ ConstructorDef<?> def = (ConstructorDef<?>) o;
+ if (length != def.getArgs().length) {
+ return false;
+ }
+ if (length == 0) {
+ return true;
+ }
+ if (length == 1) {
+ return getArgs()[0].getName().equals(def.getArgs()[0].getName());
+ }
+ return equalsIgnoreOrder(def);
}
@Override