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 <[email protected]> Authored: Sat Dec 12 16:37:36 2015 +0900 Committer: Mariia Mykhailova <[email protected]> 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
