From dddea012f920f922a94157c740d99a3b5a474f6e Mon Sep 17 00:00:00 2001 From: OszkarSemerath Date: Tue, 8 Aug 2023 17:52:58 +0200 Subject: Non-lazy NeighbourhoodCalculator for more accurate StateCoderBuilderImpl. --- .../internal/StateCoderBuilderImpl.java | 9 +- .../AbstractNeighbourhoodCalculator.java | 19 +-- .../CollectionNeighbourhoodCalculator.java | 131 --------------------- .../neighbourhood/LazyNeighbourhoodCalculator.java | 31 +++-- .../LazyNeighbourhoodCalculatorFactory.java | 20 ---- .../neighbourhood/NeighbourhoodCalculator.java | 112 ++++++++++++++++++ .../statecoding/neighbourhood/ObjectCodeImpl.java | 11 +- 7 files changed, 152 insertions(+), 181 deletions(-) delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java delete mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java create mode 100644 subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java (limited to 'subprojects') diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java index 8268a826..05b47c52 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/internal/StateCoderBuilderImpl.java @@ -10,11 +10,8 @@ import tools.refinery.store.model.ModelStore; import tools.refinery.store.model.ModelStoreBuilder; import tools.refinery.store.representation.AnySymbol; import tools.refinery.store.representation.Symbol; -import tools.refinery.store.statecoding.StateCodeCalculatorFactory; -import tools.refinery.store.statecoding.StateCoderBuilder; -import tools.refinery.store.statecoding.StateCoderStoreAdapter; -import tools.refinery.store.statecoding.StateEquivalenceChecker; -import tools.refinery.store.statecoding.neighbourhood.LazyNeighbourhoodCalculatorFactory; +import tools.refinery.store.statecoding.*; +import tools.refinery.store.statecoding.neighbourhood.NeighbourhoodCalculator; import tools.refinery.store.statecoding.stateequivalence.StateEquivalenceCheckerImpl; import tools.refinery.store.tuple.Tuple1; @@ -24,7 +21,7 @@ public class StateCoderBuilderImpl implements StateCoderBuilder { Set excluded = new HashSet<>(); IntHashSet individuals = new IntHashSet(); - StateCodeCalculatorFactory calculator = new LazyNeighbourhoodCalculatorFactory(); + StateCodeCalculatorFactory calculator = NeighbourhoodCalculator::new; StateEquivalenceChecker checker = new StateEquivalenceCheckerImpl(); @Override diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java index c3f8a586..8fcf24b1 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/AbstractNeighbourhoodCalculator.java @@ -7,7 +7,6 @@ package tools.refinery.store.statecoding.neighbourhood; import org.eclipse.collections.api.set.primitive.IntSet; import org.eclipse.collections.impl.map.mutable.primitive.IntLongHashMap; -import org.eclipse.collections.impl.map.mutable.primitive.LongIntHashMap; import tools.refinery.store.model.Interpretation; import tools.refinery.store.statecoding.ObjectCode; import tools.refinery.store.tuple.Tuple; @@ -20,6 +19,8 @@ public abstract class AbstractNeighbourhoodCalculator { protected final LinkedHashMap, long[]> impactValues; protected final IntLongHashMap individualHashValues; + protected static final long PRIME = 31; + protected AbstractNeighbourhoodCalculator(List> interpretations, IntSet individuals) { this.nullImpactValues = new ArrayList<>(); this.impactValues = new LinkedHashMap<>(); @@ -45,25 +46,25 @@ public abstract class AbstractNeighbourhoodCalculator { } } - protected void initializeWithIndividuals(ObjectCodeImpl previous, LongIntHashMap hash2Amount) { + protected void initializeWithIndividuals(ObjectCodeImpl previous) { for (var entry : individualHashValues.keyValuesView()) { previous.set(entry.getOne(), entry.getTwo()); - hash2Amount.put(entry.getTwo(), 1); } } protected long getTupleHash1(Tuple tuple, Object value, ObjectCode objectCodeImpl) { long result = Objects.hashCode(value); - result = result * 31 + objectCodeImpl.get(tuple.get(0)); + result = result * PRIME + objectCodeImpl.get(tuple.get(0)); return result; } protected long getTupleHash2(Tuple tuple, Object value, ObjectCode objectCodeImpl) { long result = Objects.hashCode(value); - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - result = result * 31 + objectCodeImpl.get(tuple.get(1)); + result = result * PRIME + objectCodeImpl.get(tuple.get(0)); + result = result * PRIME + objectCodeImpl.get(tuple.get(1)); if (tuple.get(0) == tuple.get(1)) { - result *= 31; + result += PRIME; + result *= PRIME; } return result; } @@ -71,7 +72,7 @@ public abstract class AbstractNeighbourhoodCalculator { protected long getTupleHashN(Tuple tuple, Object value, ObjectCode objectCodeImpl) { long result = Objects.hashCode(value); for (int i = 0; i < tuple.getSize(); i++) { - result = result * 31 + objectCodeImpl.get(tuple.get(i)); + result = result * PRIME + objectCodeImpl.get(tuple.get(i)); } return result; } @@ -84,7 +85,7 @@ public abstract class AbstractNeighbourhoodCalculator { protected long calculateModelCode(long lastSum) { long result = 0; for (var nullImpactValue : nullImpactValues) { - result = result * 31 + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); + result = result * PRIME + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); } result += lastSum; return result; diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java deleted file mode 100644 index 058750ee..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/CollectionNeighbourhoodCalculator.java +++ /dev/null @@ -1,131 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.statecoding.neighbourhood; - -import org.eclipse.collections.api.set.primitive.MutableLongSet; -import org.eclipse.collections.impl.set.mutable.primitive.LongHashSet; -import tools.refinery.store.model.Interpretation; -import tools.refinery.store.statecoding.StateCodeCalculator; -import tools.refinery.store.statecoding.StateCoderResult; -import tools.refinery.store.tuple.Tuple; -import tools.refinery.store.tuple.Tuple0; - -import java.util.ArrayList; -import java.util.LinkedHashMap; -import java.util.List; -import java.util.Random; - -public class CollectionNeighbourhoodCalculator implements StateCodeCalculator { - protected final List> nullImpactValues; - protected final LinkedHashMap, long[]> impactValues; - - public CollectionNeighbourhoodCalculator(List> interpretations) { - this.nullImpactValues = new ArrayList<>(); - this.impactValues = new LinkedHashMap<>(); - Random random = new Random(1); - - for (Interpretation interpretation : interpretations) { - int arity = interpretation.getSymbol().arity(); - if (arity == 0) { - nullImpactValues.add(interpretation); - } else { - long[] impact = new long[arity]; - for (int i = 0; i < arity; i++) { - impact[i] = random.nextLong(); - } - impactValues.put(interpretation, impact); - } - } - } - - @Override - public StateCoderResult calculateCodes() { - ObjectCodeImpl previous = new ObjectCodeImpl(); - ObjectCodeImpl next = new ObjectCodeImpl(); - - int previousSize = 1; - long lastSum; - boolean grows; - - do{ - for (var impactValueEntry : this.impactValues.entrySet()) { - Interpretation interpretation = impactValueEntry.getKey(); - long[] impact = impactValueEntry.getValue(); - var cursor = interpretation.getAll(); - while (cursor.move()) { - Tuple tuple = cursor.getKey(); - Object value = cursor.getValue(); - long tupleHash = getTupleHash(tuple, value, previous); - addHash(next, tuple, impact, tupleHash); - } - } - - previous = next; - next = null; - lastSum = 0; - MutableLongSet codes = new LongHashSet(); - for (int i = 0; i < previous.getSize(); i++) { - long objectHash = previous.get(i); - codes.add(objectHash); - - final long shifted1 = objectHash>>> 32; - final long shifted2 = objectHash << 32; - lastSum += shifted1 + shifted2; - } - int nextSize = codes.size(); - grows = previousSize < nextSize; - previousSize = nextSize; - - if(grows) { - next = new ObjectCodeImpl(previous); - } - } while (grows); - - long result = 1; - for (var nullImpactValue : nullImpactValues) { - result = result * 31 + nullImpactValue.get(Tuple0.INSTANCE).hashCode(); - } - result += lastSum; - - return new StateCoderResult((int) result, previous); - } - - protected long getTupleHash(Tuple tuple, Object value, ObjectCodeImpl objectCodeImpl) { - long result = value.hashCode(); - int arity = tuple.getSize(); - if (arity == 1) { - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - } else if (arity == 2) { - result = result * 31 + objectCodeImpl.get(tuple.get(0)); - result = result * 31 + objectCodeImpl.get(tuple.get(1)); - if (tuple.get(0) == tuple.get(1)) { - result++; - } - } else if (arity > 2) { - for (int i = 0; i < arity; i++) { - result = result * 31 + objectCodeImpl.get(tuple.get(i)); - } - } - return result; - } - - protected void addHash(ObjectCodeImpl objectCodeImpl, Tuple tuple, long[] impact, long tupleHashCode) { - if (tuple.getSize() == 1) { - addHash(objectCodeImpl, tuple.get(0), impact[0], tupleHashCode); - } else if (tuple.getSize() == 2) { - addHash(objectCodeImpl, tuple.get(0), impact[0], tupleHashCode); - addHash(objectCodeImpl, tuple.get(1), impact[1], tupleHashCode); - } else if (tuple.getSize() > 2) { - for (int i = 0; i < tuple.getSize(); i++) { - addHash(objectCodeImpl, tuple.get(i), impact[i], tupleHashCode); - } - } - } - - protected void addHash(ObjectCodeImpl objectCodeImpl, int o, long impact, long tupleHash) { - objectCodeImpl.set(o, objectCodeImpl.get(o) + tupleHash * impact); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java index 98a75e08..2ffbef5e 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculator.java @@ -22,34 +22,41 @@ public class LazyNeighbourhoodCalculator extends AbstractNeighbourhoodCalculator } public StateCoderResult calculateCodes() { - ObjectCodeImpl previous = new ObjectCodeImpl(); - LongIntHashMap hash2Amount = new LongIntHashMap(); - - initializeWithIndividuals(previous, hash2Amount); + ObjectCodeImpl previousObjectCode = new ObjectCodeImpl(); + LongIntHashMap prevHash2Amount = new LongIntHashMap(); long lastSum; // All hash code is 0, except to the individuals. - int lastSize = hash2Amount.size() + 1; + int lastSize = 1; + boolean first = true; boolean grows; + int rounds = 0; do { - ObjectCodeImpl next = new ObjectCodeImpl(); - constructNextObjectCodes(previous, next, hash2Amount); + final ObjectCodeImpl nextObjectCode; + if (first) { + nextObjectCode = new ObjectCodeImpl(); + initializeWithIndividuals(nextObjectCode); + } else { + nextObjectCode = new ObjectCodeImpl(previousObjectCode); + } + constructNextObjectCodes(previousObjectCode, nextObjectCode, prevHash2Amount); LongIntHashMap nextHash2Amount = new LongIntHashMap(); - lastSum = calculateLastSum(previous, next, hash2Amount, nextHash2Amount); + lastSum = calculateLastSum(previousObjectCode, nextObjectCode, prevHash2Amount, nextHash2Amount); int nextSize = nextHash2Amount.size(); grows = nextSize > lastSize; lastSize = nextSize; + first = false; - previous = next; - hash2Amount = nextHash2Amount; - } while (grows); + previousObjectCode = nextObjectCode; + prevHash2Amount = nextHash2Amount; + } while (grows && rounds++ < 4/*&& lastSize < previousObjectCode.getSize()*/); long result = calculateModelCode(lastSum); - return new StateCoderResult((int) result, previous); + return new StateCoderResult((int) result, previousObjectCode); } private long calculateLastSum(ObjectCodeImpl previous, ObjectCodeImpl next, LongIntMap hash2Amount, diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java deleted file mode 100644 index 2e499f95..00000000 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/LazyNeighbourhoodCalculatorFactory.java +++ /dev/null @@ -1,20 +0,0 @@ -/* - * SPDX-FileCopyrightText: 2023 The Refinery Authors - * - * SPDX-License-Identifier: EPL-2.0 - */ -package tools.refinery.store.statecoding.neighbourhood; - -import org.eclipse.collections.api.set.primitive.IntSet; -import tools.refinery.store.model.Interpretation; -import tools.refinery.store.statecoding.StateCodeCalculator; -import tools.refinery.store.statecoding.StateCodeCalculatorFactory; - -import java.util.List; - -public class LazyNeighbourhoodCalculatorFactory implements StateCodeCalculatorFactory { - @Override - public StateCodeCalculator create(List> interpretations, IntSet individuals) { - return new LazyNeighbourhoodCalculator(interpretations,individuals); - } -} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java new file mode 100644 index 00000000..d3b3ccae --- /dev/null +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/NeighbourhoodCalculator.java @@ -0,0 +1,112 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.statecoding.neighbourhood; + +import org.eclipse.collections.api.set.primitive.IntSet; +import tools.refinery.store.map.Cursor; +import tools.refinery.store.model.Interpretation; +import tools.refinery.store.statecoding.ObjectCode; +import tools.refinery.store.statecoding.StateCodeCalculator; +import tools.refinery.store.statecoding.StateCoderResult; +import tools.refinery.store.tuple.Tuple; +import tools.refinery.store.tuple.Tuple0; + +import java.util.List; +import java.util.Objects; + +public class NeighbourhoodCalculator extends AbstractNeighbourhoodCalculator implements StateCodeCalculator { + public NeighbourhoodCalculator(List> interpretations, IntSet individuals) { + super(interpretations, individuals); + } + + public StateCoderResult calculateCodes() { + ObjectCodeImpl previousObjectCode = new ObjectCodeImpl(); + initializeWithIndividuals(previousObjectCode); + + int rounds = 0; + do { + final ObjectCodeImpl nextObjectCode = rounds == 0 ? new ObjectCodeImpl() : + new ObjectCodeImpl(previousObjectCode.getSize()); + + constructNextObjectCodes(previousObjectCode, nextObjectCode); + previousObjectCode = nextObjectCode; + rounds++; + } while (rounds <= 7 && rounds <= previousObjectCode.getSize()); + + long result = calculateLastSum(previousObjectCode); + return new StateCoderResult((int) result, previousObjectCode); + } + + private long calculateLastSum(ObjectCode codes) { + long result = 0; + for (var nullImpactValue : nullImpactValues) { + result = result * 31 + Objects.hashCode(nullImpactValue.get(Tuple0.INSTANCE)); + } + + for (int i = 0; i < codes.getSize(); i++) { + final long hash = codes.get(i); + result += hash*PRIME; + } + + return result; + } + + private void constructNextObjectCodes(ObjectCodeImpl previous, ObjectCodeImpl next) { + for (var impactValueEntry : this.impactValues.entrySet()) { + Interpretation interpretation = impactValueEntry.getKey(); + var cursor = interpretation.getAll(); + int arity = interpretation.getSymbol().arity(); + long[] impactValue = impactValueEntry.getValue(); + + if (arity == 1) { + while (cursor.move()) { + impactCalculation1(previous, next, impactValue, cursor); + } + } else if (arity == 2) { + while (cursor.move()) { + impactCalculation2(previous, next, impactValue, cursor); + } + } else { + while (cursor.move()) { + impactCalculationN(previous, next, impactValue, cursor); + } + } + } + } + + + private void impactCalculation1(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { + + Tuple tuple = cursor.getKey(); + int o = tuple.get(0); + Object value = cursor.getValue(); + long tupleHash = getTupleHash1(tuple, value, previous); + addHash(next, o, impactValues[0], tupleHash); + } + + private void impactCalculation2(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { + final Tuple tuple = cursor.getKey(); + final int o1 = tuple.get(0); + final int o2 = tuple.get(1); + + Object value = cursor.getValue(); + long tupleHash = getTupleHash2(tuple, value, previous); + + addHash(next, o1, impactValues[0], tupleHash); + addHash(next, o2, impactValues[1], tupleHash); + } + + private void impactCalculationN(ObjectCodeImpl previous, ObjectCodeImpl next, long[] impactValues, Cursor cursor) { + final Tuple tuple = cursor.getKey(); + + Object value = cursor.getValue(); + long tupleHash = getTupleHashN(tuple, value, previous); + + for (int i = 0; i < tuple.getSize(); i++) { + addHash(next, tuple.get(i), impactValues[i], tupleHash); + } + } +} diff --git a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java index c4d86cf1..0d629176 100644 --- a/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java +++ b/subprojects/store/src/main/java/tools/refinery/store/statecoding/neighbourhood/ObjectCodeImpl.java @@ -18,9 +18,14 @@ public class ObjectCodeImpl implements ObjectCode { size = 0; } - public ObjectCodeImpl(ObjectCodeImpl sameSize) { - this.vector = new long[sameSize.size]; - this.size = sameSize.size; + public ObjectCodeImpl(int size) { + this.vector = new long[size]; + this.size = size; + } + + public ObjectCodeImpl(ObjectCodeImpl copy) { + this.vector = Arrays.copyOf(copy.vector,copy.size); + this.size = copy.size; } public void ensureSize(int object) { -- cgit v1.2.3-54-g00ecf