diff options
-rw-r--r-- | model-integration/src/main/java/ai/vespa/rankingexpression/importer/DimensionRenamer.java | 77 | ||||
-rw-r--r-- | vespajlib/src/main/java/com/yahoo/collections/ListMap.java | 23 |
2 files changed, 64 insertions, 36 deletions
diff --git a/model-integration/src/main/java/ai/vespa/rankingexpression/importer/DimensionRenamer.java b/model-integration/src/main/java/ai/vespa/rankingexpression/importer/DimensionRenamer.java index af6008b07e3..9fe4560b7c6 100644 --- a/model-integration/src/main/java/ai/vespa/rankingexpression/importer/DimensionRenamer.java +++ b/model-integration/src/main/java/ai/vespa/rankingexpression/importer/DimensionRenamer.java @@ -2,10 +2,10 @@ package ai.vespa.rankingexpression.importer; import ai.vespa.rankingexpression.importer.operations.IntermediateOperation; +import com.yahoo.collections.ListMap; +import com.yahoo.lang.MutableInteger; import java.util.ArrayDeque; -import java.util.ArrayList; -import java.util.Collections; import java.util.Deque; import java.util.HashMap; import java.util.Iterator; @@ -13,7 +13,6 @@ import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Optional; -import java.util.function.Predicate; import java.util.stream.Collectors; /** @@ -25,11 +24,11 @@ import java.util.stream.Collectors; public class DimensionRenamer { private final String dimensionPrefix; - private final Map<String, List<Integer>> variables = new HashMap<>(); + private final ListMap<String, Integer> variables = new ListMap<>(); private final Map<Arc, Constraint> constraints = new HashMap<>(); - private final Map<String, Integer> renames = new HashMap<>(); - private int iterations = 0; + /** The solution to this, or null if no solution is found (yet) */ + private Map<String, Integer> renames = null; public DimensionRenamer() { this("d"); @@ -43,7 +42,7 @@ public class DimensionRenamer { * Add a dimension name variable. */ public void addDimension(String name) { - variables.computeIfAbsent(name, d -> new ArrayList<>()); + variables.put(name); } /** @@ -59,7 +58,7 @@ public class DimensionRenamer { * Retrieve resulting name of dimension after solving for constraints. */ public Optional<String> dimensionNameOf(String name) { - if (!renames.containsKey(name)) { + if ( ! renames.containsKey(name)) { return Optional.empty(); } return Optional.of(String.format("%s%d", dimensionPrefix, renames.get(name))); @@ -77,21 +76,22 @@ public class DimensionRenamer { * not typically result in a guaranteed ordering. If that is needed, the * algorithm below needs to be adapted with a backtracking (tree) search * to find solutions. + * + * @return the solution in the form of the renames to perform */ - private void solve(int maxIterations) { - initialize(); + private Map<String, Integer> solve(int maxIterations) { + variables.freeze(); + Map<String, Integer> renames = new HashMap<>(); // Todo: evaluate possible improved efficiency by using a heuristic such as min-conflicts - boolean solved = trySolve(maxIterations); + boolean solved = trySolve(variables, constraints, maxIterations, renames); if ( ! solved) { - List<Arc> softConstraints = constraints.entrySet().stream() - .filter(e -> e.getValue().isSoft()) - .map(e -> e.getKey()) - .collect(Collectors.toList()); - if ( ! softConstraints.isEmpty()) { - softConstraints.forEach(softConstraint -> constraints.remove(softConstraint)); - trySolve(maxIterations); - } + renames.clear(); + Map<Arc, Constraint> hardConstraints = new HashMap<>(); + constraints.entrySet().stream().filter(e -> ! e.getValue().isSoft()) + .forEach(e -> hardConstraints.put(e.getKey(), e.getValue())); + if (hardConstraints.size() < constraints.size()) + solved = trySolve(variables, hardConstraints, maxIterations, renames); } if ( ! solved) { throw new IllegalArgumentException("Could not find a dimension naming solution" + @@ -102,27 +102,36 @@ public class DimensionRenamer { // If a solution can't be found, look at the operation node in the arc // with the most remaining constraints, and inject a rename operation. // Then run this algorithm again. + + return renames; } - private boolean trySolve(int maxIterations) { + /** Try the solve the constraint problem given in the arguments, and put the result in renames */ + private static boolean trySolve(ListMap<String, Integer> inputVariables, + Map<Arc, Constraint> constraints, + int maxIterations, + Map<String, Integer> renames) { + var variables = new ListMap<>(inputVariables); + initialize(variables); + MutableInteger iterations = new MutableInteger(0); for (String dimension : variables.keySet()) { List<Integer> values = variables.get(dimension); if (values.size() > 1) { - if ( ! ac3()) return false; + if ( ! ac3(iterations, variables, constraints)) return false; values.sort(Integer::compare); - variables.put(dimension, Collections.singletonList(values.get(0))); + variables.put(dimension, values.get(0)); } renames.put(dimension, variables.get(dimension).get(0)); - if (iterations > maxIterations) return false; + if (iterations.get() > maxIterations) return false; } return true; } void solve() { - solve(100000); + renames = solve(100000); } - private void initialize() { + private static void initialize(ListMap<String, Integer> variables) { for (Map.Entry<String, List<Integer>> variable : variables.entrySet()) { List<Integer> values = variable.getValue(); for (int i = 0; i < variables.size(); ++i) { @@ -131,12 +140,14 @@ public class DimensionRenamer { } } - private boolean ac3() { + private static boolean ac3(MutableInteger iterations, + ListMap<String, Integer> variables, + Map<Arc, Constraint> constraints) { Deque<Arc> workList = new ArrayDeque<>(constraints.keySet()); - while (!workList.isEmpty()) { + while ( ! workList.isEmpty()) { Arc arc = workList.pop(); - iterations += 1; - if (revise(arc)) { + iterations.add(1); + if (revise(arc, variables, constraints)) { if (variables.get(arc.from).size() == 0) { return false; // no solution found } @@ -150,9 +161,11 @@ public class DimensionRenamer { return true; } - private boolean revise(Arc arc) { + private static boolean revise(Arc arc, + ListMap<String, Integer> variables, + Map<Arc, Constraint> constraints) { boolean revised = false; - for(Iterator<Integer> fromIterator = variables.get(arc.from).iterator(); fromIterator.hasNext(); ) { + for (Iterator<Integer> fromIterator = variables.get(arc.from).iterator(); fromIterator.hasNext(); ) { Integer from = fromIterator.next(); boolean satisfied = false; for (Iterator<Integer> toIterator = variables.get(arc.to).iterator(); toIterator.hasNext(); ) { @@ -161,7 +174,7 @@ public class DimensionRenamer { satisfied = true; } } - if (!satisfied) { + if ( ! satisfied) { fromIterator.remove(); revised = true; } diff --git a/vespajlib/src/main/java/com/yahoo/collections/ListMap.java b/vespajlib/src/main/java/com/yahoo/collections/ListMap.java index e851362a99d..052ea55d6fe 100644 --- a/vespajlib/src/main/java/com/yahoo/collections/ListMap.java +++ b/vespajlib/src/main/java/com/yahoo/collections/ListMap.java @@ -23,6 +23,12 @@ public class ListMap<K, V> { this(HashMap.class); } + /** Copy constructor. This will not be frozen even if the argument map is */ + public ListMap(ListMap<K, V> original) { + map = new HashMap<>(); + original.map.forEach((k, v) -> this.map.put(k, new ArrayList<>(v))); + } + @SuppressWarnings("unchecked") public ListMap(@SuppressWarnings("rawtypes") Class<? extends Map> implementation) { try { @@ -45,6 +51,15 @@ public class ListMap<K, V> { list.add(value); } + /** Put a key without adding a new value, such that there is an empty list of values if no values are already added */ + public void put(K key) { + List<V> list = map.get(key); + if (list == null) { + list = new ArrayList<>(); + map.put(key, list); + } + } + public void removeAll(K key) { map.remove(key); } @@ -73,13 +88,13 @@ public class ListMap<K, V> { /** * Returns the List containing the elements with this key, or an empty list - * if there are no elements for this key. The list returned is unmodifiable. + * if there are no elements for this key. + * The returned list can be modified to add and remove values if the value exists. */ public List<V> get(K key) { List<V> list = map.get(key); - if (list == null) - return ImmutableList.of();; - return ImmutableList.copyOf(list); + if (list == null) return ImmutableList.of();; + return list; } /** The same as get */ |