kyotoYaho closed pull request #124: KYLIN-3314 refactor code for cube planner
algorithm
URL: https://github.com/apache/kylin/pull/124
This is a PR merged from a forked repository.
As GitHub hides the original diff on merge, it is displayed below for
the sake of provenance:
As this is a foreign pull request (from a fork), the diff is supplied
below (as it won't show otherwise due to GitHub magic):
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/AbstractRecommendAlgorithm.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/AbstractRecommendAlgorithm.java
index b35c738645..094b960005 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/AbstractRecommendAlgorithm.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/AbstractRecommendAlgorithm.java
@@ -18,16 +18,17 @@
package org.apache.kylin.cube.cuboid.algorithm;
-import java.util.concurrent.atomic.AtomicBoolean;
-
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
+import java.util.List;
+import java.util.concurrent.atomic.AtomicBoolean;
+
public abstract class AbstractRecommendAlgorithm implements
CuboidRecommendAlgorithm {
private static final Logger logger =
LoggerFactory.getLogger(AbstractRecommendAlgorithm.class);
- private CuboidStats cuboidStats;
- private BenefitPolicy benefitPolicy;
+ protected final CuboidStats cuboidStats;
+ protected final BenefitPolicy benefitPolicy;
private AtomicBoolean cancelRequested = new AtomicBoolean(false);
private AtomicBoolean canceled = new AtomicBoolean(false);
@@ -44,6 +45,12 @@ public AbstractRecommendAlgorithm(final long timeout,
BenefitPolicy benefitPolic
this.benefitPolicy = benefitPolicy;
}
+ @Override
+ public List<Long> recommend(double expansionRate) {
+ double spaceLimit = cuboidStats.getBaseCuboidSize() * expansionRate;
+ return start(spaceLimit);
+ }
+
@Override
public void cancel() {
cancelRequested.set(true);
@@ -51,7 +58,6 @@ public void cancel() {
/**
* Checks whether the algorithm has been canceled or timed out.
- *
*/
protected boolean shouldCancel() {
if (canceled.get()) {
@@ -71,12 +77,4 @@ protected boolean shouldCancel() {
}
return false;
}
-
- public CuboidStats getCuboidStats() {
- return cuboidStats;
- }
-
- public BenefitPolicy getBenefitPolicy() {
- return benefitPolicy;
- }
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BPUSCalculator.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BPUSCalculator.java
index 6d0b654f75..e29332585f 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BPUSCalculator.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BPUSCalculator.java
@@ -18,15 +18,14 @@
package org.apache.kylin.cube.cuboid.algorithm;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Maps;
+import com.google.common.collect.Sets;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import com.google.common.collect.Maps;
-import com.google.common.collect.Sets;
+import java.util.Map;
+import java.util.Set;
/**
* Calculate the benefit based on Benefit Per Unit Space.
@@ -35,17 +34,24 @@
private static Logger logger =
LoggerFactory.getLogger(BPUSCalculator.class);
- protected CuboidStats cuboidStats;
- protected Map<Long, Long> cuboidAggCostMap;
+ protected final CuboidStats cuboidStats;
+ protected final ImmutableMap<Long, Long> initCuboidAggCostMap;
+ protected final Map<Long, Long> processCuboidAggCostMap;
public BPUSCalculator(CuboidStats cuboidStats) {
this.cuboidStats = cuboidStats;
- this.cuboidAggCostMap = Maps.newHashMap();
+ this.initCuboidAggCostMap =
ImmutableMap.copyOf(initCuboidAggCostMap());
+ this.processCuboidAggCostMap = Maps.newHashMap(initCuboidAggCostMap);
}
- @Override
- public void initBeforeStart() {
- cuboidAggCostMap.clear();
+ protected BPUSCalculator(CuboidStats cuboidStats, ImmutableMap<Long, Long>
initCuboidAggCostMap) {
+ this.cuboidStats = cuboidStats;
+ this.initCuboidAggCostMap = initCuboidAggCostMap;
+ this.processCuboidAggCostMap = Maps.newHashMap(initCuboidAggCostMap);
+ }
+
+ private Map<Long, Long> initCuboidAggCostMap() {
+ Map<Long, Long> cuboidAggCostMap = Maps.newHashMap();
//Initialize stats for mandatory cuboids
for (Long cuboid : cuboidStats.getAllCuboidsForMandatory()) {
if (getCuboidCost(cuboid) != null) {
@@ -66,6 +72,7 @@ public void initBeforeStart() {
}
cuboidAggCostMap.put(cuboid, leastCost);
}
+ return cuboidAggCostMap;
}
@Override
@@ -88,22 +95,21 @@ public void initBeforeStart() {
}
@Override
- public CuboidBenefitModel.BenefitModel calculateBenefitTotal(List<Long>
cuboidsToAdd, Set<Long> selected) {
+ public CuboidBenefitModel.BenefitModel calculateBenefitTotal(Set<Long>
cuboidsToAdd, Set<Long> selected) {
Set<Long> selectedInner = Sets.newHashSet(selected);
- Map<Long, Long> cuboidAggCostMapSnapshot =
Maps.newHashMap(cuboidAggCostMap);
+ Map<Long, Long> cuboidAggCostMapCopy =
Maps.newHashMap(processCuboidAggCostMap);
for (Long cuboid : cuboidsToAdd) {
selectedInner.add(cuboid);
- propagateAggregationCost(cuboid, selectedInner);
+ propagateAggregationCost(cuboid, selectedInner,
cuboidAggCostMapCopy);
}
double totalCostSaving = 0;
int benefitCount = 0;
- for (Long cuboid : cuboidAggCostMap.keySet()) {
- if (cuboidAggCostMap.get(cuboid) <
cuboidAggCostMapSnapshot.get(cuboid)) {
- totalCostSaving += cuboidAggCostMapSnapshot.get(cuboid) -
cuboidAggCostMap.get(cuboid);
+ for (Long cuboid : cuboidAggCostMapCopy.keySet()) {
+ if (cuboidAggCostMapCopy.get(cuboid) <
processCuboidAggCostMap.get(cuboid)) {
+ totalCostSaving += processCuboidAggCostMap.get(cuboid) -
cuboidAggCostMapCopy.get(cuboid);
benefitCount++;
}
}
- cuboidAggCostMap = cuboidAggCostMapSnapshot;
double benefitPerUnitSpace = totalCostSaving;
return new CuboidBenefitModel.BenefitModel(benefitPerUnitSpace,
benefitCount);
@@ -120,7 +126,7 @@ protected Long getCuboidCost(long cuboid) {
}
private long getCuboidAggregationCost(long cuboid) {
- return cuboidAggCostMap.get(cuboid);
+ return processCuboidAggCostMap.get(cuboid);
}
@Override
@@ -139,11 +145,15 @@ public double getMinBenefitRatio() {
@Override
public void propagateAggregationCost(long cuboid, Set<Long> selected) {
+ propagateAggregationCost(cuboid, selected, processCuboidAggCostMap);
+ }
+
+ public void propagateAggregationCost(long cuboid, Set<Long> selected,
Map<Long, Long> processCuboidAggCostMap) {
long aggregationCost = getCuboidCost(cuboid);
Set<Long> childrenCuboids = cuboidStats.getAllDescendants(cuboid);
for (Long child : childrenCuboids) {
if (!selected.contains(child) && (aggregationCost <
getCuboidAggregationCost(child))) {
- cuboidAggCostMap.put(child, aggregationCost);
+ processCuboidAggCostMap.put(child, aggregationCost);
}
}
}
@@ -158,8 +168,6 @@ public double calculateSpaceCost(long cuboid) {
@Override
public BenefitPolicy getInstance() {
- BPUSCalculator bpusCalculator = new BPUSCalculator(this.cuboidStats);
- bpusCalculator.cuboidAggCostMap.putAll(this.cuboidAggCostMap);
- return bpusCalculator;
+ return new BPUSCalculator(this.cuboidStats, this.initCuboidAggCostMap);
}
}
\ No newline at end of file
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BenefitPolicy.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BenefitPolicy.java
index 43bd3afd2b..a10e51fc53 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BenefitPolicy.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/BenefitPolicy.java
@@ -18,7 +18,6 @@
package org.apache.kylin.cube.cuboid.algorithm;
-import java.util.List;
import java.util.Set;
/**
@@ -27,15 +26,29 @@
*/
public interface BenefitPolicy {
+ /**
+ * @return a cloned instance with initial status
+ */
public BenefitPolicy getInstance();
- public void initBeforeStart();
-
+ /**
+ * @param selected should not be changed
+ * Will not change the inner instance status
+ */
public CuboidBenefitModel.BenefitModel calculateBenefit(long cuboid,
Set<Long> selected);
- public CuboidBenefitModel.BenefitModel calculateBenefitTotal(List<Long>
cuboidsToAdd, Set<Long> selected);
+ /**
+ * @param cuboidsToAdd should not be changed
+ * @param selected should not be changed
+ * Will not change the inner instance status
+ */
+ public CuboidBenefitModel.BenefitModel calculateBenefitTotal(Set<Long>
cuboidsToAdd, Set<Long> selected);
public boolean ifEfficient(CuboidBenefitModel best);
+ /**
+ * @param selected should not be changed
+ * Will update the inner instance status
+ */
public void propagateAggregationCost(long cuboid, Set<Long> selected);
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidBenefitModel.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidBenefitModel.java
index 42f1ecf0c1..7e1edf58d4 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidBenefitModel.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidBenefitModel.java
@@ -33,11 +33,11 @@ public void reset(CuboidModel cuboidModel, BenefitModel
benefitModel) {
}
public Long getCuboidId() {
- return cuboidModel == null ? null : cuboidModel.getCuboidId();
+ return cuboidModel == null ? null : cuboidModel.cuboidId;
}
public Double getBenefit() {
- return benefitModel == null ? null : benefitModel.getBenefit();
+ return benefitModel == null ? null : benefitModel.benefit;
}
@Override
@@ -45,45 +45,14 @@ public String toString() {
return "CuboidBenefitModel [cuboidModel=" + cuboidModel + ",
benefitModel=" + benefitModel + "]";
}
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + ((cuboidModel == null) ? 0 :
cuboidModel.hashCode());
- result = prime * result + ((benefitModel == null) ? 0 :
benefitModel.hashCode());
- return result;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- CuboidBenefitModel other = (CuboidBenefitModel) obj;
- if (cuboidModel == null) {
- if (other.cuboidModel != null)
- return false;
- } else if (!cuboidModel.equals(other.cuboidModel))
- return false;
- if (benefitModel == null) {
- if (other.benefitModel != null)
- return false;
- } else if (!benefitModel.equals(other.benefitModel))
- return false;
- return true;
- }
-
public static class CuboidModel {
- private long cuboidId;
+ public final long cuboidId;
- private long recordCount;
- private double spaceSize;
+ public final long recordCount;
+ public final double spaceSize;
- private double hitProbability;
- private long scanCount;
+ public final double hitProbability;
+ public final long scanCount;
public CuboidModel(long cuboId, long recordCount, double spaceSize,
double hitProbability, long scanCount) {
this.cuboidId = cuboId;
@@ -93,118 +62,25 @@ public CuboidModel(long cuboId, long recordCount, double
spaceSize, double hitPr
this.scanCount = scanCount;
}
- public long getCuboidId() {
- return cuboidId;
- }
-
- public long getRecordCount() {
- return recordCount;
- }
-
- public double getSpaceSize() {
- return spaceSize;
- }
-
- public double getHitProbability() {
- return hitProbability;
- }
-
- public long getScanCount() {
- return scanCount;
- }
-
@Override
public String toString() {
return "CuboidModel [cuboidId=" + cuboidId + ", recordCount=" +
recordCount + ", spaceSize=" + spaceSize
+ ", hitProbability=" + hitProbability + ", scanCount=" +
scanCount + "]";
}
-
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + (int) (cuboidId ^ (cuboidId >>> 32));
- result = prime * result + (int) (recordCount ^ (recordCount >>>
32));
- long temp;
- temp = Double.doubleToLongBits(spaceSize);
- result = prime * result + (int) (temp ^ (temp >>> 32));
- temp = Double.doubleToLongBits(hitProbability);
- result = prime * result + (int) (temp ^ (temp >>> 32));
- result = prime * result + (int) (scanCount ^ (scanCount >>> 32));
- return result;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
-
- CuboidModel other = (CuboidModel) obj;
- if (cuboidId != other.cuboidId)
- return false;
- if (recordCount != other.recordCount)
- return false;
- if (Double.doubleToLongBits(spaceSize) !=
Double.doubleToLongBits(other.spaceSize))
- return false;
- if (hitProbability != other.hitProbability)
- return false;
- if (scanCount != other.scanCount)
- return false;
- return true;
- }
}
public static class BenefitModel {
- private double benefit;
- private int benefitCount;
+ public final double benefit;
+ public final int benefitCount;
public BenefitModel(double benefit, int benefitCount) {
this.benefit = benefit;
this.benefitCount = benefitCount;
}
- public double getBenefit() {
- return benefit;
- }
-
- public int getBenefitCount() {
- return benefitCount;
- }
-
@Override
public String toString() {
return "BenefitModel [benefit=" + benefit + ", benefitCount=" +
benefitCount + "]";
}
-
- @Override
- public int hashCode() {
- final int prime = 31;
- int result = 1;
- long temp;
- temp = Double.doubleToLongBits(benefit);
- result = prime * result + (int) (temp ^ (temp >>> 32));
- result = prime * result + benefitCount;
- return result;
- }
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- BenefitModel other = (BenefitModel) obj;
- if (Double.doubleToLongBits(benefit) !=
Double.doubleToLongBits(other.benefit))
- return false;
- if (benefitCount != other.benefitCount)
- return false;
- return true;
- }
}
-}
+}
\ No newline at end of file
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidStats.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidStats.java
index a1c191ef4a..78a6c5b517 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidStats.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/CuboidStats.java
@@ -18,18 +18,17 @@
package org.apache.kylin.cube.cuboid.algorithm;
-import java.util.List;
-import java.util.Map;
-import java.util.Set;
-
-import org.slf4j.Logger;
-import org.slf4j.LoggerFactory;
-
import com.google.common.base.Preconditions;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.List;
+import java.util.Map;
+import java.util.Set;
public class CuboidStats {
private static final Logger logger =
LoggerFactory.getLogger(CuboidStats.class);
@@ -67,7 +66,7 @@ public Builder setRollingUpCountSourceMap(Map<Long, Map<Long,
Long>> rollingUpCo
}
public Builder setRollingUpCountSourceMap(Map<Long, Map<Long, Long>>
rollingUpCountSourceMap,
- long rollUpThresholdForMandatory) {
+ long
rollUpThresholdForMandatory) {
this.rollingUpCountSourceMap = rollingUpCountSourceMap;
this.rollUpThresholdForMandatory = rollUpThresholdForMandatory;
return this;
@@ -125,7 +124,7 @@ public CuboidStats build() {
private Map<Long, Set<Long>> allDescendantsCache;
private CuboidStats(String key, long baseCuboidId, Set<Long>
mandatoryCuboids, Map<Long, Long> statistics,
- Map<Long, Double> size, Map<Long, Long> hitFrequencyMap, Map<Long,
Map<Long, Long>> scanCountSourceMap) {
+ Map<Long, Double> size, Map<Long, Long>
hitFrequencyMap, Map<Long, Map<Long, Long>> scanCountSourceMap) {
this.key = key;
this.baseCuboid = baseCuboidId;
@@ -142,8 +141,8 @@ private CuboidStats(String key, long baseCuboidId,
Set<Long> mandatoryCuboids, M
cuboidsForSelection.removeAll(cuboidsForMandatory);
//There's no overlap between mandatoryCuboidSet and selectionCuboidSet
- this.mandatoryCuboidSet = ImmutableSet.<Long>
builder().addAll(cuboidsForMandatory).build();
- this.selectionCuboidSet = ImmutableSet.<Long>
builder().addAll(cuboidsForSelection).build();
+ this.mandatoryCuboidSet =
ImmutableSet.<Long>builder().addAll(cuboidsForMandatory).build();
+ this.selectionCuboidSet =
ImmutableSet.<Long>builder().addAll(cuboidsForSelection).build();
if (selectionCuboidSet.isEmpty()) {
logger.warn("The selection set should not be empty!!!");
}
@@ -151,8 +150,8 @@ private CuboidStats(String key, long baseCuboidId,
Set<Long> mandatoryCuboids, M
/** Initialize row count for mandatory cuboids */
CuboidStatsUtil.complementRowCountForMandatoryCuboids(statistics,
baseCuboid, mandatoryCuboidSet);
- this.cuboidCountMap = ImmutableMap.<Long, Long>
builder().putAll(statistics).build();
- this.cuboidSizeMap = ImmutableMap.<Long, Double>
builder().putAll(size).build();
+ this.cuboidCountMap = ImmutableMap.<Long,
Long>builder().putAll(statistics).build();
+ this.cuboidSizeMap = ImmutableMap.<Long,
Double>builder().putAll(size).build();
/** Initialize the hit probability for each selection cuboid */
Map<Long, Double> tmpCuboidHitProbabilityMap =
Maps.newHashMapWithExpectedSize(selectionCuboidSet.size());
@@ -179,7 +178,7 @@ private CuboidStats(String key, long baseCuboidId,
Set<Long> mandatoryCuboids, M
tmpCuboidHitProbabilityMap.put(cuboid, 1.0 /
selectionCuboidSet.size());
}
}
- this.cuboidHitProbabilityMap = ImmutableMap.<Long, Double>
builder().putAll(tmpCuboidHitProbabilityMap).build();
+ this.cuboidHitProbabilityMap = ImmutableMap.<Long,
Double>builder().putAll(tmpCuboidHitProbabilityMap).build();
/** Initialize the scan count when query for each selection cuboid +
one base cuboid */
Map<Long, Long> tmpCuboidScanCountMap =
Maps.newHashMapWithExpectedSize(1 + selectionCuboidSet.size());
@@ -187,16 +186,16 @@ private CuboidStats(String key, long baseCuboidId,
Set<Long> mandatoryCuboids, M
for (Long cuboid : selectionCuboidSet) {
tmpCuboidScanCountMap.put(cuboid, getExpScanCount(cuboid,
statistics, scanCountSourceMap));
}
- this.cuboidScanCountMap = ImmutableMap.<Long, Long>
builder().putAll(tmpCuboidScanCountMap).build();
+ this.cuboidScanCountMap = ImmutableMap.<Long,
Long>builder().putAll(tmpCuboidScanCountMap).build();
- this.directChildrenCache = ImmutableMap.<Long, List<Long>> builder()
+ this.directChildrenCache = ImmutableMap.<Long, List<Long>>builder()
.putAll(CuboidStatsUtil.createDirectChildrenCache(statistics.keySet())).build();
this.allDescendantsCache = Maps.newConcurrentMap();
}
private long getExpScanCount(long sourceCuboid, Map<Long, Long> statistics,
- Map<Long, Map<Long, Long>> scanCountSourceMap) {
+ Map<Long, Map<Long, Long>>
scanCountSourceMap) {
Preconditions.checkNotNull(statistics.get(sourceCuboid),
"The statistics for source cuboid " + sourceCuboid + " does
not exist!!!");
if (scanCountSourceMap == null || scanCountSourceMap.get(sourceCuboid)
== null
@@ -240,11 +239,11 @@ private void getAllDescendants(long cuboid, Set<Long>
allDescendants) {
}
}
- public Set<Long> getAllCuboidsForSelection() {
+ public ImmutableSet<Long> getAllCuboidsForSelection() {
return selectionCuboidSet;
}
- public Set<Long> getAllCuboidsForMandatory() {
+ public ImmutableSet<Long> getAllCuboidsForMandatory() {
return mandatoryCuboidSet;
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/PBPUSCalculator.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/PBPUSCalculator.java
index 6d3ddc7a24..9fddaecb88 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/PBPUSCalculator.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/PBPUSCalculator.java
@@ -19,6 +19,7 @@
package org.apache.kylin.cube.cuboid.algorithm;
import com.google.common.base.Preconditions;
+import com.google.common.collect.ImmutableMap;
/**
* Calculate the benefit based on Benefit Per Unit Space with query
probability distribution.
@@ -29,6 +30,10 @@ public PBPUSCalculator(final CuboidStats cuboidStats) {
super(cuboidStats);
}
+ protected PBPUSCalculator(CuboidStats cuboidStats, ImmutableMap<Long,
Long> initCuboidAggCostMap) {
+ super(cuboidStats, initCuboidAggCostMap);
+ }
+
@Override
protected double getCostSaving(long descendant, long cuboid) {
return getCuboidHitProbability(descendant) *
super.getCostSaving(descendant, cuboid);
@@ -39,15 +44,14 @@ protected double getCuboidHitProbability(long cuboid) {
}
public double getMinBenefitRatio() {
-
Preconditions.checkArgument(cuboidStats.getAllCuboidsForSelection().size() > 0,
+ int cuboidDomainSize = cuboidStats.getAllCuboidsForSelection().size();
+ Preconditions.checkArgument(cuboidDomainSize > 0,
"The set of cuboids for selection is empty!!!");
- return super.getMinBenefitRatio() /
cuboidStats.getAllCuboidsForSelection().size();
+ return super.getMinBenefitRatio() / cuboidDomainSize;
}
@Override
public BenefitPolicy getInstance() {
- PBPUSCalculator pbpusCalculator = new PBPUSCalculator(cuboidStats);
- pbpusCalculator.cuboidAggCostMap.putAll(this.cuboidAggCostMap);
- return pbpusCalculator;
+ return new PBPUSCalculator(this.cuboidStats,
this.initCuboidAggCostMap);
}
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/SPBPUSCalculator.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/SPBPUSCalculator.java
index c89bf498b4..e235de3c53 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/SPBPUSCalculator.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/SPBPUSCalculator.java
@@ -18,6 +18,8 @@
package org.apache.kylin.cube.cuboid.algorithm;
+import com.google.common.collect.ImmutableMap;
+
/**
* Calculate the benefit based on Benefit Per Unit Space with query
probability distribution and updated cost.
*/
@@ -27,6 +29,10 @@ public SPBPUSCalculator(final CuboidStats cuboidStats) {
super(cuboidStats);
}
+ protected SPBPUSCalculator(CuboidStats cuboidStats, ImmutableMap<Long,
Long> initCuboidAggCostMap) {
+ super(cuboidStats, initCuboidAggCostMap);
+ }
+
@Override
protected Long getCuboidCost(long cuboid) {
return cuboidStats.getCuboidQueryCost(cuboid);
@@ -34,8 +40,6 @@ protected Long getCuboidCost(long cuboid) {
@Override
public BenefitPolicy getInstance() {
- SPBPUSCalculator spbpusCalculator = new SPBPUSCalculator(cuboidStats);
- spbpusCalculator.cuboidAggCostMap.putAll(this.cuboidAggCostMap);
- return spbpusCalculator;
+ return new SPBPUSCalculator(this.cuboidStats,
this.initCuboidAggCostMap);
}
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java
index 6445ca6ddb..81d7e20386 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosome.java
@@ -18,70 +18,72 @@
package org.apache.kylin.cube.cuboid.algorithm.generic;
-import java.util.BitSet;
-import java.util.List;
-import java.util.Set;
-
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Sets;
+import org.apache.commons.math3.genetics.Chromosome;
import org.apache.kylin.cube.cuboid.algorithm.BenefitPolicy;
import org.apache.kylin.cube.cuboid.algorithm.CuboidBenefitModel;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Chromosome;
-import org.apache.kylin.cube.cuboid.algorithm.CuboidStats;
-import com.google.common.collect.Sets;
+import java.util.BitSet;
public class BitsChromosome extends Chromosome {
- private BitSet key;
- private int length;
- private BenefitPolicy benefitPolicy;
- private CuboidStats cuboidStats;
- private CuboidEncoder cuboidEncoder;
- private double spaceLimit;
- private double spaceCost;
- private double fitness = -1;
-
- public BitsChromosome(final BitSet key, final BenefitPolicy benefitPolicy,
final CuboidStats cuboidStats,
- final double spaceLimit) {
- super();
- this.key = key;
- this.length = cuboidStats.getAllCuboidsForSelection().size();
- this.benefitPolicy = benefitPolicy.getInstance();
- this.cuboidStats = cuboidStats;
- this.cuboidEncoder = new CuboidEncoder(cuboidStats);
- this.spaceLimit = spaceLimit;
- initSpaceCost();
- }
+ /**
+ * Global unmodified
+ */
+ private final BitsChromosomeHelper helper;
+
+ /**
+ * BitSet representing the chromosome
+ */
+ private final BitSet representation;
+ private final ImmutableSet<Long> cuboids;
+
+ private final BenefitPolicy benefitPolicy;
- public BitsChromosome newBitsChromosome(BitSet newkey) {
- return new BitsChromosome(newkey, this.benefitPolicy,
this.cuboidStats, this.spaceLimit);
+ private final double spaceCost;
+
+ public BitsChromosome(final BitSet representation, final BenefitPolicy
benefitPolicy, BitsChromosomeHelper helper) {
+ this.helper = helper;
+
+ this.representation = representation;
+ this.cuboids =
ImmutableSet.copyOf(helper.toCuboidList(representation));
+
+ this.benefitPolicy = benefitPolicy;
+
+ this.spaceCost = helper.getCuboidSize(Sets.newHashSet(cuboids));
}
- private void initSpaceCost() {
- spaceCost = 0;
- List<Long> remainingCuboids = cuboidEncoder.toCuboidList(key);
- for (Long cuboid : remainingCuboids) {
- spaceCost += cuboidStats.getCuboidSize(cuboid);
- }
+ public BitsChromosome newBitsChromosome(BitSet newRepresentation) {
+ return new BitsChromosome(newRepresentation,
benefitPolicy.getInstance(), helper);
}
- public BitSet getKey() {
- return key;
+ public BitSet getRepresentation() {
+ return representation;
}
+ /**
+ * Returns the length of the chromosome.
+ *
+ * @return the length of the chromosome
+ */
public int getLength() {
- return length;
+ return helper.getLength();
}
- public CuboidEncoder getCuboidEncoder() {
- return cuboidEncoder;
+ public ImmutableSet<Long> getCuboids() {
+ return cuboids;
}
@Override
- public double fitness() {
- if (fitness == -1) {
- fitness = calculateFitness();
+ public synchronized double fitness() {
+ CuboidBenefitModel.BenefitModel benefitModel =
benefitPolicy.calculateBenefitTotal(cuboids,
+ helper.getMandatoryCuboids());
+ double totalBenefit = benefitModel.benefit;
+ if (spaceCost > helper.spaceLimit) {
+ totalBenefit = totalBenefit * helper.spaceLimit / spaceCost;
}
- return fitness;
+ return totalBenefit;
}
@Override
@@ -89,45 +91,25 @@ protected boolean isSame(final Chromosome another) {
return this.equals(another);
}
- private synchronized double calculateFitness() {
- List<Long> remainingCuboids = cuboidEncoder.toCuboidList(key);
- Set<Long> selectedCuboidSets = Sets.newHashSet();
- selectedCuboidSets.addAll(cuboidStats.getAllCuboidsForMandatory());
+ @Override
+ public boolean equals(Object o) {
+ if (this == o)
+ return true;
+ if (o == null || getClass() != o.getClass())
+ return false;
+
+ BitsChromosome that = (BitsChromosome) o;
+
+ if (helper != null ? !helper.equals(that.helper) : that.helper != null)
+ return false;
+ return representation != null ?
representation.equals(that.representation) : that.representation == null;
- CuboidBenefitModel.BenefitModel benefitModel =
benefitPolicy.calculateBenefitTotal(remainingCuboids, selectedCuboidSets);
- double totalBenefit = benefitModel.getBenefit();
- if (spaceCost > spaceLimit) {
- totalBenefit = totalBenefit * spaceLimit / spaceCost;
- }
- return totalBenefit;
}
@Override
public int hashCode() {
- final int prime = 31;
- int result = 1;
- result = prime * result + ((key == null) ? 0 : key.hashCode());
- result = prime * result + length;
+ int result = helper != null ? helper.hashCode() : 0;
+ result = 31 * result + (representation != null ?
representation.hashCode() : 0);
return result;
}
-
- @Override
- public boolean equals(Object obj) {
- if (this == obj)
- return true;
- if (obj == null)
- return false;
- if (getClass() != obj.getClass())
- return false;
- BitsChromosome other = (BitsChromosome) obj;
- if (length != other.length) {
- return false;
- }
- if (key == null) {
- if (other.key != null)
- return false;
- } else if (!key.equals(other.key))
- return false;
- return true;
- }
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosomeHelper.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosomeHelper.java
new file mode 100644
index 0000000000..2b5d143ae5
--- /dev/null
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsChromosomeHelper.java
@@ -0,0 +1,120 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+*/
+
+package org.apache.kylin.cube.cuboid.algorithm.generic;
+
+import com.google.common.collect.ImmutableList;
+import com.google.common.collect.ImmutableSet;
+import com.google.common.collect.Lists;
+import org.apache.kylin.cube.cuboid.algorithm.CuboidStats;
+
+import java.util.BitSet;
+import java.util.Collections;
+import java.util.List;
+import java.util.Set;
+
+public class BitsChromosomeHelper {
+
+ public final double spaceLimit;
+ private final CuboidStats cuboidStats;
+ private final CuboidEncoder cuboidEncoder;
+
+ public BitsChromosomeHelper(final double spaceLimit, final CuboidStats
cuboidStats) {
+ this.spaceLimit = spaceLimit;
+ this.cuboidStats = cuboidStats;
+ this.cuboidEncoder = new
CuboidEncoder(cuboidStats.getAllCuboidsForSelection());
+ }
+
+ public ImmutableSet<Long> getMandatoryCuboids() {
+ return cuboidStats.getAllCuboidsForMandatory();
+ }
+
+ public List<Long> toCuboidList(BitSet bits) {
+ return cuboidEncoder.toCuboidList(bits);
+ }
+
+ public double getCuboidSize(Set<Long> cuboids) {
+ double ret = 0;
+ for (Long cuboid : cuboids) {
+ ret += cuboidStats.getCuboidSize(cuboid);
+ }
+ return ret;
+ }
+
+ public double getCuboidSizeByBitIndex(int index) {
+ return
cuboidStats.getCuboidSize(cuboidEncoder.cuboidDomain.get(index));
+ }
+
+ public int getLength() {
+ return cuboidEncoder.cuboidDomain.size();
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o)
+ return true;
+ if (o == null || getClass() != o.getClass())
+ return false;
+
+ BitsChromosomeHelper that = (BitsChromosomeHelper) o;
+
+ return cuboidEncoder != null ?
cuboidEncoder.equals(that.cuboidEncoder) : that.cuboidEncoder == null;
+
+ }
+
+ @Override
+ public int hashCode() {
+ return cuboidEncoder != null ? cuboidEncoder.hashCode() : 0;
+ }
+
+ private static class CuboidEncoder {
+ public final ImmutableList<Long> cuboidDomain;
+
+ public CuboidEncoder(Set<Long> cuboidSet) {
+ List<Long> cuboidList = Lists.newArrayList(cuboidSet);
+ Collections.sort(cuboidList, Collections.reverseOrder());
+ this.cuboidDomain = ImmutableList.copyOf(cuboidList);
+ }
+
+ public List<Long> toCuboidList(BitSet bits) {
+ List<Long> cuboids =
Lists.newArrayListWithExpectedSize(bits.cardinality());
+ for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i +
1)) {
+ cuboids.add(cuboidDomain.get(i));
+ }
+ return cuboids;
+ }
+
+ @Override
+ public boolean equals(Object o) {
+ if (this == o)
+ return true;
+ if (o == null || getClass() != o.getClass())
+ return false;
+
+ CuboidEncoder that = (CuboidEncoder) o;
+
+ return cuboidDomain != null ?
cuboidDomain.equals(that.cuboidDomain) : that.cuboidDomain == null;
+
+ }
+
+ @Override
+ public int hashCode() {
+ return cuboidDomain != null ? cuboidDomain.hashCode() : 0;
+ }
+ }
+}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsMutation.java
similarity index 70%
rename from
core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java
rename to
core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsMutation.java
index 073b947510..2cd4b99654 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/BitsMutation.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsMutation.java
@@ -16,18 +16,20 @@
* limitations under the License.
*/
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
+package org.apache.kylin.cube.cuboid.algorithm.generic;
-import java.util.BitSet;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.util.DummyLocalizable;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.GeneticAlgorithm;
+import org.apache.commons.math3.genetics.MutationPolicy;
-import org.apache.kylin.cube.cuboid.algorithm.generic.BitsChromosome;
-import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm;
+import java.util.BitSet;
/**
* Modified from the BinaryMutation.java in
https://github.com/apache/commons-math
- *
+ * <p>
* Mutation for {@link BitsChromosome}s. Randomly changes one gene.
- *
*/
public class BitsMutation implements MutationPolicy {
@@ -40,22 +42,18 @@
*/
public Chromosome mutate(Chromosome original) throws
IllegalArgumentException {
if (!(original instanceof BitsChromosome)) {
- throw new IllegalArgumentException("Chromosome " +
original.getClass() + " must be of type BitsChromosome.");
+ throw new MathIllegalArgumentException(new DummyLocalizable("bits
mutation only works on BitsChromosome"));
}
BitsChromosome origChrom = (BitsChromosome) original;
- BitSet newNey = (BitSet) origChrom.getKey().clone();
+ BitSet newNey = (BitSet) origChrom.getRepresentation().clone();
// randomly select a gene
- int geneIndex = getMutationGeneIndex(origChrom);
+ int geneIndex =
GeneticAlgorithm.getRandomGenerator().nextInt(origChrom.getLength());
// change it
- boolean value = newNey.get(geneIndex);
- newNey.set(geneIndex, !value);
+ newNey.set(geneIndex, !newNey.get(geneIndex));
+
Chromosome newChrom = origChrom.newBitsChromosome(newNey);
return newChrom;
}
-
- protected int getMutationGeneIndex(BitsChromosome origChrom) {
- return GeneticAlgorithm.RANDGEN.get().nextInt(origChrom.getLength());
- }
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsOnePointCrossover.java
old mode 100755
new mode 100644
similarity index 72%
rename from
core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java
rename to
core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsOnePointCrossover.java
index 5ef8cfa3be..00559d360c
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/OnePointCrossover.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/BitsOnePointCrossover.java
@@ -16,20 +16,25 @@
* limitations under the License.
*/
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
+package org.apache.kylin.cube.cuboid.algorithm.generic;
-import java.util.BitSet;
+import org.apache.commons.math3.exception.DimensionMismatchException;
+import org.apache.commons.math3.exception.MathIllegalArgumentException;
+import org.apache.commons.math3.exception.util.DummyLocalizable;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.ChromosomePair;
+import org.apache.commons.math3.genetics.CrossoverPolicy;
+import org.apache.commons.math3.genetics.GeneticAlgorithm;
-import org.apache.kylin.cube.cuboid.algorithm.generic.BitsChromosome;
-import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm;
+import java.util.BitSet;
/**
* Modified from the OnePointCrossover.java in
https://github.com/apache/commons-math
- *
+ * <p>
* One point crossover policy. A random crossover point is selected and the
* first part from each parent is copied to the corresponding child, and the
* second parts are copied crosswise.
- *
+ * <p>
* Example:
* <pre>
* -C- denotes a crossover point
@@ -41,19 +46,17 @@
* /------------\ /-----\ /------------\ /-----\
* c1 = (1 0 1 0 0 1 | 1 1 1) X c2 = (0 1 1 0 1 0 | 0 1 1)
* </pre>
- *
+ * <p>
* This policy works only on {@link BitsChromosome}, and therefore it
* is parameterized by T. Moreover, the chromosomes must have same lengths.
- *
- *
*/
-public class OnePointCrossover implements CrossoverPolicy {
+public class BitsOnePointCrossover implements CrossoverPolicy {
/**
* Performs one point crossover. A random crossover point is selected and
the
* first part from each parent is copied to the corresponding child, and
the
* second parts are copied crosswise.
- *
+ * <p>
* Example:
* <pre>
* -C- denotes a crossover point
@@ -66,20 +69,20 @@
* c1 = (1 0 1 0 0 1 | 1 1 1) X c2 = (0 1 1 0 1 0 | 0 1 1)
* </pre>
*
- * @param first first parent (p1)
+ * @param first first parent (p1)
* @param second second parent (p2)
* @return pair of two children (c1,c2)
- * @throws IllegalArgumentException if one of the chromosomes is
- * not an instance of {@link BitsChromosome}
- * @throws ChromosomeMismatchException if the length of the two
chromosomes is different
+ * @throws IllegalArgumentException if one of the chromosomes is
+ * not an instance of {@link
BitsChromosome}
+ * @throws MathIllegalArgumentException if the length of the two
chromosomes is different
*/
@SuppressWarnings("unchecked") // OK because of instanceof checks
public ChromosomePair crossover(final Chromosome first, final Chromosome
second)
- throws IllegalArgumentException, ChromosomeMismatchException {
+ throws DimensionMismatchException, MathIllegalArgumentException {
if (!(first instanceof BitsChromosome && second instanceof
BitsChromosome)) {
- throw new IllegalArgumentException("Chromosome first " +
first.getClass() + " and second "
- + second.getClass() + " must be of type BitsChromosome.");
+ throw new MathIllegalArgumentException(
+ new DummyLocalizable("bits one-point crossover only works
on BitsChromosome"));
}
return crossover((BitsChromosome) first, (BitsChromosome) second);
}
@@ -87,26 +90,26 @@ public ChromosomePair crossover(final Chromosome first,
final Chromosome second)
/**
* Helper for {@link #crossover(Chromosome, Chromosome)}. Performs the
actual crossover.
*
- * @param first the first chromosome.
+ * @param first the first chromosome.
* @param second the second chromosome.
* @return the pair of new chromosomes that resulted from the crossover.
- * @throws ChromosomeMismatchException if the length of the two
chromosomes is different
+ * @throws DimensionMismatchException if the length of the two chromosomes
is different
*/
private ChromosomePair crossover(final BitsChromosome first, final
BitsChromosome second)
- throws ChromosomeMismatchException {
+ throws DimensionMismatchException {
final int length = first.getLength();
if (length != second.getLength()) {
- throw new ChromosomeMismatchException("BitsChromosome length
mismatch.", second.getLength(), length);
+ throw new DimensionMismatchException(second.getLength(), length);
}
- final BitSet parent1Key = first.getKey();
- final BitSet parent2Key = second.getKey();
+ final BitSet parent1Key = first.getRepresentation();
+ final BitSet parent2Key = second.getRepresentation();
final BitSet child1Key = new BitSet(length);
final BitSet child2Key = new BitSet(length);
// select a crossover point at random (0 and length makes no sense)
- final int crossoverIndex = 1 +
(GeneticAlgorithm.RANDGEN.get().nextInt(length - 2));
+ final int crossoverIndex = 1 +
(GeneticAlgorithm.getRandomGenerator().nextInt(length - 2));
BitSet a = (BitSet) parent1Key.clone();
a.clear(crossoverIndex, length);
@@ -125,4 +128,4 @@ private ChromosomePair crossover(final BitsChromosome
first, final BitsChromosom
child2Key.or(b);
return new ChromosomePair(first.newBitsChromosome(child1Key),
second.newBitsChromosome(child2Key));
}
-}
+}
\ No newline at end of file
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java
index bc4bb99024..a12c44deb2 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CombinedStoppingCondition.java
@@ -18,8 +18,8 @@
package org.apache.kylin.cube.cuboid.algorithm.generic;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Population;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.StoppingCondition;
+import org.apache.commons.math3.genetics.Population;
+import org.apache.commons.math3.genetics.StoppingCondition;
import java.util.List;
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java
deleted file mode 100755
index 7e4841357a..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/CuboidEncoder.java
+++ /dev/null
@@ -1,44 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic;
-
-import java.util.BitSet;
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.kylin.cube.cuboid.algorithm.CuboidStats;
-
-import com.google.common.collect.Lists;
-
-public class CuboidEncoder {
- private List<Long> selectionCuboids;
-
- public CuboidEncoder(CuboidStats cuboidStats) {
- selectionCuboids =
Lists.newArrayList(cuboidStats.getAllCuboidsForSelection());
- Collections.sort(selectionCuboids, Collections.reverseOrder());
- }
-
- public List<Long> toCuboidList(BitSet bits) {
- List<Long> cuboids =
Lists.newArrayListWithCapacity(bits.cardinality());
- for (int i = bits.nextSetBit(0); i >= 0; i = bits.nextSetBit(i + 1)) {
- cuboids.add(selectionCuboids.get(i));
- }
- return cuboids;
- }
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java
index ce4dc3e213..27d59fa88f 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/GeneticAlgorithm.java
@@ -18,91 +18,70 @@
package org.apache.kylin.cube.cuboid.algorithm.generic;
-import java.util.BitSet;
-import java.util.List;
-import java.util.Random;
-
+import com.google.common.collect.Lists;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.ElitisticListPopulation;
+import org.apache.commons.math3.genetics.FixedGenerationCount;
+import org.apache.commons.math3.genetics.Population;
+import org.apache.commons.math3.genetics.StoppingCondition;
import org.apache.kylin.cube.cuboid.algorithm.AbstractRecommendAlgorithm;
import org.apache.kylin.cube.cuboid.algorithm.BenefitPolicy;
import org.apache.kylin.cube.cuboid.algorithm.CuboidStats;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.BitsMutation;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Chromosome;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ChromosomePair;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.CrossoverPolicy;
-import
org.apache.kylin.cube.cuboid.algorithm.generic.lib.ElitisticListPopulation;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.FixedGenerationCount;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.MutationPolicy;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.OnePointCrossover;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Population;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.SelectionPolicy;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.StoppingCondition;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import com.google.common.collect.Lists;
+import java.util.BitSet;
+import java.util.List;
/**
- * Modified from the GeneticAlgorithm.java in
https://github.com/apache/commons-math
- *
- * Implementation of a genetic algorithm to recommend a list of cuboids. All
factors that govern the processing
- * of the algorithm can be configured.
- *
+ * Implementation of a genetic algorithm to recommend a list of cuboids.
+ * All factors that govern the processing of the algorithm can be configured.
*/
public class GeneticAlgorithm extends AbstractRecommendAlgorithm {
private static final Logger logger =
LoggerFactory.getLogger(GeneticAlgorithm.class);
- public static ThreadLocal<Random> RANDGEN = new ThreadLocal<Random>() {
- @Override
- protected Random initialValue() {
- return new Random(System.currentTimeMillis() *
Thread.currentThread().getId());
- }
- };
- /** the rate of crossover for the algorithm. */
+
+ private final org.apache.commons.math3.genetics.GeneticAlgorithm
geneticAlgorithm;
+
+ /**
+ * the rate of crossover for the algorithm.
+ */
private final double crossoverRate = 0.9;
- /** the rate of mutation for the algorithm. */
+ /**
+ * the rate of mutation for the algorithm.
+ */
private final double mutationRate = 0.001;
- /** the init population size. */
+ /**
+ * the init population size.
+ */
private final int populationSize = 500;
- /** the max population size. */
+ /**
+ * the max population size.
+ */
private final int maxPopulationSize = 510;
- private CrossoverPolicy crossoverPolicy;
- private MutationPolicy mutationPolicy;
- private SelectionPolicy selectionPolicy;
- private CuboidEncoder cuboidEncoder;
- /** the number of generations evolved to reach {@link StoppingCondition}
in the last run. */
- private int generationsEvolved = 0;
public GeneticAlgorithm(final long timeout, BenefitPolicy benefitPolicy,
CuboidStats cuboidStats) {
super(timeout, benefitPolicy, cuboidStats);
- this.crossoverPolicy = new OnePointCrossover();
- this.mutationPolicy = new BitsMutation();
- this.selectionPolicy = new RouletteWheelSelection();
-
- this.cuboidEncoder = new CuboidEncoder(getCuboidStats());
- }
-
- @Override
- public List<Long> recommend(double expansionRate) {
- double spaceLimit = getCuboidStats().getBaseCuboidSize() *
expansionRate;
- return start(spaceLimit);
+ this.geneticAlgorithm = new
org.apache.commons.math3.genetics.GeneticAlgorithm(new BitsOnePointCrossover(),
+ crossoverRate, new BitsMutation(), mutationRate, new
RouletteWheelSelection());
}
@Override
public List<Long> start(double maxSpaceLimit) {
logger.debug("Genetic Algorithm started.");
- getBenefitPolicy().initBeforeStart();
-
//Initial mandatory cuboids
double remainingSpace = maxSpaceLimit;
- for (Long mandatoryOne : getCuboidStats().getAllCuboidsForMandatory())
{
- if (getCuboidStats().getCuboidSize(mandatoryOne) != null) {
- remainingSpace -= getCuboidStats().getCuboidSize(mandatoryOne);
+ for (Long mandatoryOne : cuboidStats.getAllCuboidsForMandatory()) {
+ if (cuboidStats.getCuboidSize(mandatoryOne) != null) {
+ remainingSpace -= cuboidStats.getCuboidSize(mandatoryOne);
}
}
+ BitsChromosomeHelper helper = new BitsChromosomeHelper(remainingSpace,
cuboidStats);
+
//Generate a population randomly
- Population initial = initRandomPopulation(remainingSpace);
+ Population initial = initRandomPopulation(helper);
//Set stopping condition
List<StoppingCondition> conditions = Lists.newArrayList();
@@ -110,17 +89,17 @@ public GeneticAlgorithm(final long timeout, BenefitPolicy
benefitPolicy, CuboidS
CombinedStoppingCondition stopCondition = new
CombinedStoppingCondition(conditions);
//Start the evolution
- Population current = evolve(initial, stopCondition);
+ Population current = geneticAlgorithm.evolve(initial, stopCondition);
BitsChromosome chromosome = (BitsChromosome)
current.getFittestChromosome();
logger.debug("Genetic Algorithm finished.");
List<Long> finalList = Lists.newArrayList();
- finalList.addAll(getCuboidStats().getAllCuboidsForMandatory());
- finalList.addAll(cuboidEncoder.toCuboidList(chromosome.getKey()));
+ finalList.addAll(helper.getMandatoryCuboids());
+ finalList.addAll(chromosome.getCuboids());
double totalSpace = 0;
if (logger.isTraceEnabled()) {
for (Long cuboid : finalList) {
- Double unitSpace = getCuboidStats().getCuboidSize(cuboid);
+ Double unitSpace = cuboidStats.getCuboidSize(cuboid);
if (unitSpace != null) {
logger.trace(String.format("cuboidId %d and Space: %f",
cuboid, unitSpace));
totalSpace += unitSpace;
@@ -129,157 +108,31 @@ public GeneticAlgorithm(final long timeout,
BenefitPolicy benefitPolicy, CuboidS
}
}
logger.trace("Total Space:" + totalSpace);
- logger.trace("Space Expansion Rate:" + totalSpace /
getCuboidStats().getBaseCuboidSize());
+ logger.trace("Space Expansion Rate:" + totalSpace /
cuboidStats.getBaseCuboidSize());
}
return finalList;
}
- protected Population initRandomPopulation(double maxSpaceLimit) {
+ protected Population initRandomPopulation(BitsChromosomeHelper helper) {
List<Chromosome> chromosomeList =
Lists.newArrayListWithCapacity(populationSize);
- List<Long> cuboidsForSelection =
Lists.newArrayList(getCuboidStats().getAllCuboidsForSelection());
- int selectionSize = cuboidsForSelection.size();
while (chromosomeList.size() < populationSize) {
- BitSet bitSetForSelection = new BitSet(selectionSize);
+ BitSet bitSetForSelection = new BitSet(helper.getLength());
//Initialize selection genes
double totalSpace = 0;
- while (totalSpace < maxSpaceLimit) {
- int j = RANDGEN.get().nextInt(selectionSize);
+ while (totalSpace < helper.spaceLimit) {
+ int j =
org.apache.commons.math3.genetics.GeneticAlgorithm.getRandomGenerator()
+ .nextInt(helper.getLength());
if (!bitSetForSelection.get(j)) {
- totalSpace +=
getCuboidStats().getCuboidSize(cuboidsForSelection.get(j));
+ totalSpace += helper.getCuboidSizeByBitIndex(j);
bitSetForSelection.set(j);
}
}
- Chromosome chromosome = new BitsChromosome(bitSetForSelection,
getBenefitPolicy(), getCuboidStats(),
- maxSpaceLimit);
+ Chromosome chromosome = new BitsChromosome(bitSetForSelection,
benefitPolicy.getInstance(), helper);
chromosomeList.add(chromosome);
}
return new ElitisticListPopulation(chromosomeList, maxPopulationSize,
0.8);
}
-
- /**
- * Evolve the given population. Evolution stops when the stopping condition
- * is satisfied. Updates the {@link #getGenerationsEvolved()
generationsEvolved}
- * property with the number of generations evolved before the
StoppingCondition
- * is satisfied.
- *
- * @param initial the initial, seed population.
- * @param condition the stopping condition used to stop evolution.
- * @return the population that satisfies the stopping condition.
- */
- protected Population evolve(final Population initial, final
StoppingCondition condition) {
- Population current = initial;
- generationsEvolved = 0;
- while (!condition.isSatisfied(current) && (!shouldCancel())) {
- current = nextGeneration(current);
- generationsEvolved++;
- logger.trace("Generations evolved count:" + generationsEvolved);
- }
- return current;
- }
-
- /**
- * Evolve the given population into the next generation.
- * <p>
- * <ol>
- * <li>Get nextGeneration population to fill from <code>current</code>
- * generation, using its nextGeneration method</li>
- * <li>Loop until new generation is filled:</li>
- * <ul><li>Apply configured SelectionPolicy to select a pair of parents
- * from <code>current</code></li>
- * <li>With probability = {@link #getCrossoverRate()}, apply
- * configured {@link CrossoverPolicy} to parents</li>
- * <li>With probability = {@link #getMutationRate()}, apply
- * configured {@link MutationPolicy} to each of the offspring</li>
- * <li>Add offspring individually to nextGeneration,
- * space permitting</li>
- * </ul>
- * <li>Return nextGeneration</li>
- * </ol>
- *
- * @param current the current population.
- * @return the population for the next generation.
- */
- protected Population nextGeneration(final Population current) {
- Population nextGeneration = current.nextGeneration();
-
- while (nextGeneration.getPopulationSize() <
nextGeneration.getPopulationLimit()) {
- // select parent chromosomes
- ChromosomePair pair = getSelectionPolicy().select(current);
-
- // crossover?
- if (RANDGEN.get().nextDouble() < getCrossoverRate()) {
- // apply crossover policy to create two offspring
- pair = getCrossoverPolicy().crossover(pair.getFirst(),
pair.getSecond());
- }
-
- // mutation?
- if (RANDGEN.get().nextDouble() < getMutationRate()) {
- // apply mutation policy to the chromosomes
- pair = new
ChromosomePair(getMutationPolicy().mutate(pair.getFirst()),
- getMutationPolicy().mutate(pair.getSecond()));
- }
-
- // add the first chromosome to the population
- nextGeneration.addChromosome(pair.getFirst());
- // is there still a place for the second chromosome?
- if (nextGeneration.getPopulationSize() <
nextGeneration.getPopulationLimit()) {
- // add the second chromosome to the population
- nextGeneration.addChromosome(pair.getSecond());
- }
- }
- return nextGeneration;
- }
-
- /**
- * Returns the crossover policy.
- * @return crossover policy
- */
- public CrossoverPolicy getCrossoverPolicy() {
- return crossoverPolicy;
- }
-
- /**
- * Returns the crossover rate.
- * @return crossover rate
- */
- public double getCrossoverRate() {
- return crossoverRate;
- }
-
- /**
- * Returns the mutation policy.
- * @return mutation policy
- */
- public MutationPolicy getMutationPolicy() {
- return mutationPolicy;
- }
-
- /**
- * Returns the mutation rate.
- * @return mutation rate
- */
- public double getMutationRate() {
- return mutationRate;
- }
-
- /**
- * Returns the selection policy.
- * @return selection policy
- */
- public SelectionPolicy getSelectionPolicy() {
- return selectionPolicy;
- }
-
- /**
- * Returns the number of generations evolved to reach {@link
StoppingCondition} in the last run.
- *
- * @return number of generations evolved
- */
- public int getGenerationsEvolved() {
- return generationsEvolved;
- }
-
}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java
index b93ed313b5..555e57e759 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/RouletteWheelSelection.java
@@ -19,11 +19,12 @@
package org.apache.kylin.cube.cuboid.algorithm.generic;
import com.google.common.collect.Lists;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Chromosome;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ChromosomePair;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.ListPopulation;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.Population;
-import org.apache.kylin.cube.cuboid.algorithm.generic.lib.SelectionPolicy;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.commons.math3.genetics.ChromosomePair;
+import org.apache.commons.math3.genetics.GeneticAlgorithm;
+import org.apache.commons.math3.genetics.ListPopulation;
+import org.apache.commons.math3.genetics.Population;
+import org.apache.commons.math3.genetics.SelectionPolicy;
import java.util.List;
@@ -47,7 +48,7 @@ public ChromosomePair select(Population population) throws
IllegalArgumentExcept
}
private Chromosome rouletteWheel(final List<Chromosome> chromosomes, final
double totalFitness) {
- double rnd = (GeneticAlgorithm.RANDGEN.get().nextDouble() *
totalFitness);
+ double rnd = (GeneticAlgorithm.getRandomGenerator().nextDouble() *
totalFitness);
double runningScore = 0;
for (Chromosome o : chromosomes) {
if (rnd >= runningScore && rnd <= runningScore + o.getFitness()) {
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java
deleted file mode 100755
index a58abb1e4d..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Chromosome.java
+++ /dev/null
@@ -1,106 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the Chromosome.java in https://github.com/apache/commons-math
- *
- * Individual in a population. Chromosomes are compared based on their fitness.
- * <p>
- * The chromosomes are IMMUTABLE, and so their fitness is also immutable and
- * therefore it can be cached.
- *
- */
-public abstract class Chromosome implements Comparable<Chromosome>, Fitness {
- /** Value assigned when no fitness has been computed yet. */
- private static final double NO_FITNESS = Double.NEGATIVE_INFINITY;
-
- /** Cached value of the fitness of this chromosome. */
- private double fitness = NO_FITNESS;
-
- /**
- * Access the fitness of this chromosome. The bigger the fitness, the
better the chromosome.
- * <p>
- * Computation of fitness is usually very time-consuming task, therefore
the fitness is cached.
- *
- * @return the fitness
- */
- public double getFitness() {
- if (this.fitness == NO_FITNESS) {
- // no cache - compute the fitness
- this.fitness = fitness();
- }
- return this.fitness;
- }
-
- /**
- * Compares two chromosomes based on their fitness. The bigger the
fitness, the better the chromosome.
- *
- * @param another another chromosome to compare
- * @return
- * <ul>
- * <li>-1 if <code>another</code> is better than <code>this</code></li>
- * <li>1 if <code>another</code> is worse than <code>this</code></li>
- * <li>0 if the two chromosomes have the same fitness</li>
- * </ul>
- */
- public int compareTo(final Chromosome another) {
- return Double.compare(getFitness(), another.getFitness());
- }
-
- /**
- * Returns <code>true</code> iff <code>another</code> has the same
representation and therefore the same fitness. By
- * default, it returns false -- override it in your implementation if you
need it.
- *
- * @param another chromosome to compare
- * @return true if <code>another</code> is equivalent to this chromosome
- */
- protected boolean isSame(final Chromosome another) {
- return false;
- }
-
- /**
- * Searches the <code>population</code> for another chromosome with the
same representation. If such chromosome is
- * found, it is returned, if no such chromosome exists, returns
<code>null</code>.
- *
- * @param population Population to search
- * @return Chromosome with the same representation, or <code>null</code>
if no such chromosome exists.
- */
- protected Chromosome findSameChromosome(final Population population) {
- for (Chromosome anotherChr : population) {
- if (this.isSame(anotherChr)) {
- return anotherChr;
- }
- }
- return null;
- }
-
- /**
- * Searches the population for a chromosome representing the same
solution, and if it finds one,
- * updates the fitness to its value.
- *
- * @param population Population to search
- */
- public void searchForFitnessUpdate(final Population population) {
- Chromosome sameChromosome = findSameChromosome(population);
- if (sameChromosome != null) {
- fitness = sameChromosome.getFitness();
- }
- }
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java
deleted file mode 100755
index 51d5cb3f42..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomeMismatchException.java
+++ /dev/null
@@ -1,48 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Exception to be thrown when two Chromosomes length differ.
- *
- */
-public class ChromosomeMismatchException extends IllegalArgumentException {
- private static final long serialVersionUID = -7483865132286153255L;
-
- private final int length;
-
- /**
- * Construct an exception from the mismatched chromosomes.
- *
- * @param errorMsg error info.
- * @param wrong Wrong length.
- * @param expected Expected length.
- */
- public ChromosomeMismatchException(String errorMsg, int wrong, int
expected) {
- super(errorMsg);
- length = expected;
- }
-
- /**
- * @return the expected length.
- */
- public int getLength() {
- return length;
- }
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java
deleted file mode 100755
index aa0f9df8a7..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ChromosomePair.java
+++ /dev/null
@@ -1,69 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the ChromosomePair.java in
https://github.com/apache/commons-math
- *
- * A pair of {@link Chromosome} objects.
- *
- */
-public class ChromosomePair {
- /** the first chromosome in the pair. */
- private final Chromosome first;
-
- /** the second chromosome in the pair. */
- private final Chromosome second;
-
- /**
- * Create a chromosome pair.
- *
- * @param c1 the first chromosome.
- * @param c2 the second chromosome.
- */
- public ChromosomePair(final Chromosome c1, final Chromosome c2) {
- super();
- first = c1;
- second = c2;
- }
-
- /**
- * Access the first chromosome.
- *
- * @return the first chromosome.
- */
- public Chromosome getFirst() {
- return first;
- }
-
- /**
- * Access the second chromosome.
- *
- * @return the second chromosome.
- */
- public Chromosome getSecond() {
- return second;
- }
-
- /** {@inheritDoc} */
- @Override
- public String toString() {
- return String.format("(%s,%s)", getFirst(), getSecond());
- }
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java
deleted file mode 100755
index 397075c238..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/CrossoverPolicy.java
+++ /dev/null
@@ -1,39 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the CrossoverPolicy.java in
https://github.com/apache/commons-math
- *
- * Policy used to create a pair of new chromosomes by performing a crossover
- * operation on a source pair of chromosomes.
- *
- */
-public interface CrossoverPolicy {
-
- /**
- * Perform a crossover operation on the given chromosomes.
- *
- * @param first the first chromosome.
- * @param second the second chromosome.
- * @return the pair of new chromosomes that resulted from the crossover.
- * @throws IllegalArgumentException if the given chromosomes are not
compatible with this {@link CrossoverPolicy}
- */
- ChromosomePair crossover(Chromosome first, Chromosome second) throws
IllegalArgumentException;
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java
deleted file mode 100755
index f35b2e2c05..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ElitisticListPopulation.java
+++ /dev/null
@@ -1,119 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-import java.util.Collections;
-import java.util.List;
-
-import org.apache.commons.math3.exception.NotPositiveException;
-import org.apache.commons.math3.exception.NullArgumentException;
-import org.apache.commons.math3.exception.NumberIsTooLargeException;
-import org.apache.commons.math3.exception.OutOfRangeException;
-import org.apache.commons.math3.exception.util.LocalizedFormats;
-import org.apache.commons.math3.util.FastMath;
-
-/**
- * Modified from the ElitisticListPopulation.java in
https://github.com/apache/commons-math
- *
- * Population of chromosomes which uses elitism (certain percentage of the best
- * chromosomes is directly copied to the next generation).
- *
- */
-public class ElitisticListPopulation extends ListPopulation {
-
- /** percentage of chromosomes copied to the next generation */
- private double elitismRate = 0.9;
-
- /**
- * Creates a new {@link ElitisticListPopulation} instance.
- *
- * @param chromosomes list of chromosomes in the population
- * @param populationLimit maximal size of the population
- * @param elitismRate how many best chromosomes will be directly
transferred to the next generation [in %]
- * @throws NullArgumentException if the list of chromosomes is {@code null}
- * @throws NotPositiveException if the population limit is not a positive
number (< 1)
- * @throws NumberIsTooLargeException if the list of chromosomes exceeds
the population limit
- * @throws OutOfRangeException if the elitism rate is outside the [0, 1]
range
- */
- public ElitisticListPopulation(final List<Chromosome> chromosomes, final
int populationLimit,
- final double elitismRate)
- throws NullArgumentException, NotPositiveException,
NumberIsTooLargeException, OutOfRangeException {
-
- super(chromosomes, populationLimit);
- setElitismRate(elitismRate);
- }
-
- /**
- * Creates a new {@link ElitisticListPopulation} instance and initializes
its inner chromosome list.
- *
- * @param populationLimit maximal size of the population
- * @param elitismRate how many best chromosomes will be directly
transferred to the next generation [in %]
- * @throws NotPositiveException if the population limit is not a positive
number (< 1)
- * @throws OutOfRangeException if the elitism rate is outside the [0, 1]
range
- */
- public ElitisticListPopulation(final int populationLimit, final double
elitismRate)
- throws NotPositiveException, OutOfRangeException {
-
- super(populationLimit);
- setElitismRate(elitismRate);
- }
-
- /**
- * Start the population for the next generation. The <code>{@link
#elitismRate}</code>
- * percents of the best chromosomes are directly copied to the next
generation.
- *
- * @return the beginnings of the next generation.
- */
- public Population nextGeneration() {
- // initialize a new generation with the same parameters
- ElitisticListPopulation nextGeneration = new
ElitisticListPopulation(getPopulationLimit(), getElitismRate());
-
- final List<Chromosome> oldChromosomes = getChromosomeList();
- Collections.sort(oldChromosomes);
-
- // index of the last "not good enough" chromosome
- int boundIndex = (int) FastMath.ceil((1.0 - getElitismRate()) *
oldChromosomes.size());
- for (int i = boundIndex; i < oldChromosomes.size(); i++) {
- nextGeneration.addChromosome(oldChromosomes.get(i));
- }
- return nextGeneration;
- }
-
- /**
- * Access the elitism rate.
- * @return the elitism rate
- */
- public double getElitismRate() {
- return this.elitismRate;
- }
-
- /**
- * Sets the elitism rate, i.e. how many best chromosomes will be directly
transferred to the next generation [in %].
- *
- * @param elitismRate how many best chromosomes will be directly
transferred to the next generation [in %]
- * @throws OutOfRangeException if the elitism rate is outside the [0, 1]
range
- */
- public void setElitismRate(final double elitismRate) throws
OutOfRangeException {
- if (elitismRate < 0 || elitismRate > 1) {
- throw new OutOfRangeException(LocalizedFormats.ELITISM_RATE,
elitismRate, 0, 1);
- }
- this.elitismRate = elitismRate;
- }
-
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java
deleted file mode 100755
index 9713f25c4b..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Fitness.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the Fitness.java in https://github.com/apache/commons-math
- *
- * Fitness of a chromosome.
- *
- */
-public interface Fitness {
-
- /**
- * Compute the fitness.
- * @return fitness
- */
- double fitness();
-
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java
deleted file mode 100755
index ff45fa2298..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/FixedGenerationCount.java
+++ /dev/null
@@ -1,73 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-import org.apache.commons.math3.exception.NumberIsTooSmallException;
-
-/**
- * Modified from the FixedGenerationCount.java in
https://github.com/apache/commons-math
- *
- * Stops after a fixed number of generations. Each time {@link
#isSatisfied(Population)} is invoked, a generation
- * counter is incremented. Once the counter reaches the configured
<code>maxGenerations</code> value,
- * {@link #isSatisfied(Population)} returns true.
- *
- */
-public class FixedGenerationCount implements StoppingCondition {
- /** Maximum number of generations (stopping criteria) */
- private final int maxGenerations;
- /** Number of generations that have passed */
- private int numGenerations = 0;
-
- /**
- * Create a new FixedGenerationCount instance.
- *
- * @param maxGenerations number of generations to evolve
- * @throws NumberIsTooSmallException if the number of generations is < 1
- */
- public FixedGenerationCount(final int maxGenerations) throws
NumberIsTooSmallException {
- if (maxGenerations <= 0) {
- throw new NumberIsTooSmallException(maxGenerations, 1, true);
- }
- this.maxGenerations = maxGenerations;
- }
-
- /**
- * Determine whether or not the given number of generations have passed.
Increments the number of generations
- * counter if the maximum has not been reached.
- *
- * @param population ignored (no impact on result)
- * @return <code>true</code> IFF the maximum number of generations has
been exceeded
- */
- public boolean isSatisfied(final Population population) {
- if (this.numGenerations < this.maxGenerations) {
- numGenerations++;
- return false;
- }
- return true;
- }
-
- /**
- * Returns the number of generations that have already passed.
- * @return the number of generations that have passed
- */
- public int getNumGenerations() {
- return numGenerations;
- }
-
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java
deleted file mode 100755
index 435dc72fa9..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/ListPopulation.java
+++ /dev/null
@@ -1,225 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-import java.util.ArrayList;
-import java.util.Collection;
-import java.util.Collections;
-import java.util.Iterator;
-import java.util.List;
-
-import org.apache.commons.math3.exception.NotPositiveException;
-import org.apache.commons.math3.exception.NullArgumentException;
-import org.apache.commons.math3.exception.NumberIsTooLargeException;
-import org.apache.commons.math3.exception.NumberIsTooSmallException;
-import org.apache.commons.math3.exception.util.LocalizedFormats;
-
-/**
- * Modified from the ListPopulation.java in
https://github.com/apache/commons-math
- *
- * Population of chromosomes represented by a {@link List}.
- *
- */
-public abstract class ListPopulation implements Population {
-
- /** List of chromosomes */
- private List<Chromosome> chromosomes;
-
- /** maximal size of the population */
- private int populationLimit;
-
- /**
- * Creates a new ListPopulation instance and initializes its inner
chromosome list.
- *
- * @param populationLimit maximal size of the population
- * @throws NotPositiveException if the population limit is not a positive
number (< 1)
- */
- public ListPopulation(final int populationLimit) throws
NotPositiveException {
- this(Collections.<Chromosome> emptyList(), populationLimit);
- }
-
- /**
- * Creates a new ListPopulation instance.
- * <p>
- * Note: the chromosomes of the specified list are added to the population.
- *
- * @param chromosomes list of chromosomes to be added to the population
- * @param populationLimit maximal size of the population
- * @throws NullArgumentException if the list of chromosomes is {@code null}
- * @throws NotPositiveException if the population limit is not a positive
number (< 1)
- * @throws NumberIsTooLargeException if the list of chromosomes exceeds
the population limit
- */
- public ListPopulation(final List<Chromosome> chromosomes, final int
populationLimit)
- throws NullArgumentException, NotPositiveException,
NumberIsTooLargeException {
-
- if (chromosomes == null) {
- throw new NullArgumentException();
- }
- if (populationLimit <= 0) {
- throw new
NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE,
populationLimit);
- }
- if (chromosomes.size() > populationLimit) {
- throw new
NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE,
- chromosomes.size(), populationLimit, false);
- }
- this.populationLimit = populationLimit;
- this.chromosomes = new ArrayList<Chromosome>(populationLimit);
- this.chromosomes.addAll(chromosomes);
- }
-
- /**
- * Add a {@link Collection} of chromosomes to this {@link Population}.
- * @param chromosomeColl a {@link Collection} of chromosomes
- * @throws NumberIsTooLargeException if the population would exceed the
population limit when
- * adding this chromosome
- * @since 3.1
- */
- public void addChromosomes(final Collection<Chromosome> chromosomeColl)
throws NumberIsTooLargeException {
- if (chromosomes.size() + chromosomeColl.size() > populationLimit) {
- throw new
NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE,
- chromosomes.size(), populationLimit, false);
- }
- this.chromosomes.addAll(chromosomeColl);
- }
-
- /**
- * Returns an unmodifiable list of the chromosomes in this population.
- * @return the unmodifiable list of chromosomes
- */
- public List<Chromosome> getChromosomes() {
- return Collections.unmodifiableList(chromosomes);
- }
-
- /**
- * Sets the list of chromosomes.
- * <p>
- * Note: this method removes all existing chromosomes in the population
and adds all chromosomes
- * of the specified list to the population.
- *
- * @param chromosomes the list of chromosomes
- * @throws NullArgumentException if the list of chromosomes is {@code null}
- * @throws NumberIsTooLargeException if the list of chromosomes exceeds
the population limit
- * @deprecated use {@link #addChromosomes(Collection)} instead
- */
- @Deprecated
- public void setChromosomes(final List<Chromosome> chromosomes)
- throws NullArgumentException, NumberIsTooLargeException {
-
- if (chromosomes == null) {
- throw new NullArgumentException();
- }
- if (chromosomes.size() > populationLimit) {
- throw new
NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE,
- chromosomes.size(), populationLimit, false);
- }
- this.chromosomes.clear();
- this.chromosomes.addAll(chromosomes);
- }
-
- /**
- * Access the list of chromosomes.
- * @return the list of chromosomes
- * @since 3.1
- */
- protected List<Chromosome> getChromosomeList() {
- return chromosomes;
- }
-
- /**
- * Add the given chromosome to the population.
- *
- * @param chromosome the chromosome to add.
- * @throws NumberIsTooLargeException if the population would exceed the
{@code populationLimit} after
- * adding this chromosome
- */
- public void addChromosome(final Chromosome chromosome) throws
NumberIsTooLargeException {
- if (chromosomes.size() >= populationLimit) {
- throw new
NumberIsTooLargeException(LocalizedFormats.LIST_OF_CHROMOSOMES_BIGGER_THAN_POPULATION_SIZE,
- chromosomes.size(), populationLimit, false);
- }
- this.chromosomes.add(chromosome);
- }
-
- /**
- * Access the fittest chromosome in this population.
- * @return the fittest chromosome.
- */
- public Chromosome getFittestChromosome() {
- // best so far
- Chromosome bestChromosome = this.chromosomes.get(0);
- for (Chromosome chromosome : this.chromosomes) {
- if (chromosome.compareTo(bestChromosome) > 0) {
- // better chromosome found
- bestChromosome = chromosome;
- }
- }
- return bestChromosome;
- }
-
- /**
- * Access the maximum population size.
- * @return the maximum population size.
- */
- public int getPopulationLimit() {
- return this.populationLimit;
- }
-
- /**
- * Sets the maximal population size.
- * @param populationLimit maximal population size.
- * @throws NotPositiveException if the population limit is not a positive
number (< 1)
- * @throws NumberIsTooSmallException if the new population size is smaller
than the current number
- * of chromosomes in the population
- */
- public void setPopulationLimit(final int populationLimit) throws
NotPositiveException, NumberIsTooSmallException {
- if (populationLimit <= 0) {
- throw new
NotPositiveException(LocalizedFormats.POPULATION_LIMIT_NOT_POSITIVE,
populationLimit);
- }
- if (populationLimit < chromosomes.size()) {
- throw new NumberIsTooSmallException(populationLimit,
chromosomes.size(), true);
- }
- this.populationLimit = populationLimit;
- }
-
- /**
- * Access the current population size.
- * @return the current population size.
- */
- public int getPopulationSize() {
- return this.chromosomes.size();
- }
-
- /**
- * {@inheritDoc}
- */
- @Override
- public String toString() {
- return this.chromosomes.toString();
- }
-
- /**
- * Returns an iterator over the unmodifiable list of chromosomes.
- * <p>Any call to {@link Iterator#remove()} will result in a {@link
UnsupportedOperationException}.</p>
- *
- * @return chromosome iterator
- */
- public Iterator<Chromosome> iterator() {
- return getChromosomes().iterator();
- }
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java
deleted file mode 100755
index 183483a3ab..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/MutationPolicy.java
+++ /dev/null
@@ -1,36 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the MutationPolicy.java in
https://github.com/apache/commons-math
- *
- * Algorithm used to mutate a chromosome.
- *
- */
-public interface MutationPolicy {
-
- /**
- * Mutate the given chromosome.
- * @param original the original chromosome.
- * @return the mutated chromosome.
- * @throws IllegalArgumentException if the given chromosome is not
compatible with this {@link MutationPolicy}
- */
- Chromosome mutate(Chromosome original) throws IllegalArgumentException;
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java
deleted file mode 100755
index c22f518148..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/Population.java
+++ /dev/null
@@ -1,61 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-import org.apache.commons.math3.exception.NumberIsTooLargeException;
-
-/**
- * Modified from the Population.java in https://github.com/apache/commons-math
- *
- * A collection of chromosomes that facilitates generational evolution.
- *
- */
-public interface Population extends Iterable<Chromosome> {
- /**
- * Access the current population size.
- * @return the current population size.
- */
- int getPopulationSize();
-
- /**
- * Access the maximum population size.
- * @return the maximum population size.
- */
- int getPopulationLimit();
-
- /**
- * Start the population for the next generation.
- * @return the beginnings of the next generation.
- */
- Population nextGeneration();
-
- /**
- * Add the given chromosome to the population.
- * @param chromosome the chromosome to add.
- * @throws NumberIsTooLargeException if the population would exceed the
population limit when adding
- * this chromosome
- */
- void addChromosome(Chromosome chromosome) throws NumberIsTooLargeException;
-
- /**
- * Access the fittest chromosome in this population.
- * @return the fittest chromosome.
- */
- Chromosome getFittestChromosome();
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java
deleted file mode 100755
index 7ac14c5a7e..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/SelectionPolicy.java
+++ /dev/null
@@ -1,35 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the SelectionPolicy.java in
https://github.com/apache/commons-math
- *
- * Algorithm used to select a chromosome pair from a population.
- *
- */
-public interface SelectionPolicy {
- /**
- * Select two chromosomes from the population.
- * @param population the population from which the chromosomes are choosen.
- * @return the selected chromosomes.
- * @throws IllegalArgumentException if the population is not compatible
with this {@link SelectionPolicy}
- */
- ChromosomePair select(Population population) throws
IllegalArgumentException;
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java
deleted file mode 100755
index bf3a26d52d..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/StoppingCondition.java
+++ /dev/null
@@ -1,36 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-/**
- * Modified from the StoppingCondition.java in
https://github.com/apache/commons-math
- *
- * Algorithm used to determine when to stop evolution.
- *
- */
-public interface StoppingCondition {
- /**
- * Determine whether or not the given population satisfies the stopping
condition.
- *
- * @param population the population to test.
- * @return <code>true</code> if this stopping condition is met by the
given population,
- * <code>false</code> otherwise.
- */
- boolean isSatisfied(Population population);
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java
deleted file mode 100755
index 158ccd24f7..0000000000
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/generic/lib/TournamentSelection.java
+++ /dev/null
@@ -1,116 +0,0 @@
-/*
- * Licensed to the Apache Software Foundation (ASF) under one
- * or more contributor license agreements. See the NOTICE file
- * distributed with this work for additional information
- * regarding copyright ownership. The ASF licenses this file
- * to you under the Apache License, Version 2.0 (the
- * "License"); you may not use this file except in compliance
- * with the License. You may obtain a copy of the License at
- *
- * http://www.apache.org/licenses/LICENSE-2.0
- *
- * Unless required by applicable law or agreed to in writing, software
- * distributed under the License is distributed on an "AS IS" BASIS,
- * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
- * See the License for the specific language governing permissions and
- * limitations under the License.
-*/
-
-package org.apache.kylin.cube.cuboid.algorithm.generic.lib;
-
-import java.util.List;
-
-import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm;
-
-import com.google.common.collect.Lists;
-
-/**
- * Modified from the TournamentSelection.java in
https://github.com/apache/commons-math
- *
- * Tournament selection scheme. Each of the two selected chromosomes is
selected
- * based on n-ary tournament -- this is done by drawing {@link #arity} random
- * chromosomes without replacement from the population, and then selecting the
- * fittest chromosome among them.
- *
- */
-public class TournamentSelection implements SelectionPolicy {
-
- /** number of chromosomes included in the tournament selections */
- private int arity;
-
- /**
- * Creates a new TournamentSelection instance.
- *
- * @param arity how many chromosomes will be drawn to the tournament
- */
- public TournamentSelection(final int arity) {
- this.arity = arity;
- }
-
- /**
- * Select two chromosomes from the population. Each of the two selected
- * chromosomes is selected based on n-ary tournament -- this is done by
- * drawing {@link #arity} random chromosomes without replacement from the
- * population, and then selecting the fittest chromosome among them.
- *
- * @param population the population from which the chromosomes are chosen.
- * @return the selected chromosomes.
- * @throws IllegalArgumentException if the tournament arity is bigger than
the population size
- */
- public ChromosomePair select(final Population population) throws
IllegalArgumentException {
- return new ChromosomePair(tournament((ListPopulation) population),
tournament((ListPopulation) population));
- }
-
- /**
- * Helper for {@link #select(Population)}. Draw {@link #arity} random
chromosomes without replacement from the
- * population, and then select the fittest chromosome among them.
- *
- * @param population the population from which the chromosomes are chosen.
- * @return the selected chromosome.
- * @throws IllegalArgumentException if the tournament arity is bigger than
the population size
- */
- private Chromosome tournament(final ListPopulation population) throws
IllegalArgumentException {
- if (population.getPopulationSize() < this.arity) {
- throw new IllegalArgumentException("Tournament arty is too
large.");
- }
- // auxiliary population
- ListPopulation tournamentPopulation = new ListPopulation(this.arity) {
- /** {@inheritDoc} */
- public Population nextGeneration() {
- // not useful here
- return null;
- }
- };
-
- // create a copy of the chromosome list
- List<Chromosome> chromosomes =
Lists.newArrayList(population.getChromosomes());
- for (int i = 0; i < this.arity; i++) {
- // select a random individual and add it to the tournament
- int rind =
GeneticAlgorithm.RANDGEN.get().nextInt(chromosomes.size());
- tournamentPopulation.addChromosome(chromosomes.get(rind));
- // do not select it again
- chromosomes.remove(rind);
- }
- // the winner takes it all
- return tournamentPopulation.getFittestChromosome();
- }
-
- /**
- * Gets the arity (number of chromosomes drawn to the tournament).
- *
- * @return arity of the tournament
- */
- public int getArity() {
- return arity;
- }
-
- /**
- * Sets the arity (number of chromosomes drawn to the tournament).
- *
- * @param arity arity of the tournament
- */
- public void setArity(final int arity) {
- this.arity = arity;
- }
-
-}
diff --git
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
index 5dbe189c85..0f2dcc39fc 100755
---
a/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
+++
b/core-cube/src/main/java/org/apache/kylin/cube/cuboid/algorithm/greedy/GreedyAlgorithm.java
@@ -18,13 +18,10 @@
package org.apache.kylin.cube.cuboid.algorithm.greedy;
-import java.util.List;
-import java.util.Set;
-import java.util.concurrent.CountDownLatch;
-import java.util.concurrent.ExecutorService;
-import java.util.concurrent.Executors;
-import java.util.concurrent.atomic.AtomicReference;
-
+import com.google.common.base.Preconditions;
+import com.google.common.collect.Lists;
+import com.google.common.collect.Sets;
+import com.google.common.util.concurrent.ThreadFactoryBuilder;
import org.apache.kylin.cube.cuboid.algorithm.AbstractRecommendAlgorithm;
import org.apache.kylin.cube.cuboid.algorithm.BenefitPolicy;
import org.apache.kylin.cube.cuboid.algorithm.CuboidBenefitModel;
@@ -32,15 +29,17 @@
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
-import com.google.common.base.Preconditions;
-import com.google.common.collect.Lists;
-import com.google.common.collect.Sets;
-import com.google.common.util.concurrent.ThreadFactoryBuilder;
+import java.util.List;
+import java.util.Set;
+import java.util.concurrent.CountDownLatch;
+import java.util.concurrent.ExecutorService;
+import java.util.concurrent.Executors;
+import java.util.concurrent.atomic.AtomicReference;
/**
-* A simple implementation of the Greedy Algorithm , it chooses the cuboids
which give
-* the greatest benefit based on expansion rate and time limitation.
-*/
+ * A simple implementation of the Greedy Algorithm , it chooses the cuboids
which give
+ * the greatest benefit based on expansion rate and time limitation.
+ */
public class GreedyAlgorithm extends AbstractRecommendAlgorithm {
private static final Logger logger =
LoggerFactory.getLogger(GreedyAlgorithm.class);
@@ -54,32 +53,24 @@ public GreedyAlgorithm(final long timeout, BenefitPolicy
benefitPolicy, CuboidSt
super(timeout, benefitPolicy, cuboidStats);
}
- @Override
- public List<Long> recommend(double expansionRate) {
- double spaceLimit = getCuboidStats().getBaseCuboidSize() *
expansionRate;
- return start(spaceLimit);
- }
-
@Override
public List<Long> start(double spaceLimit) {
logger.info("Greedy Algorithm started.");
executor = Executors.newFixedThreadPool(THREAD_NUM,
new
ThreadFactoryBuilder().setNameFormat("greedy-algorithm-benefit-calculator-pool-%d").build());
- getBenefitPolicy().initBeforeStart();
-
//Initial mandatory cuboids
selected.clear();
double remainingSpace = spaceLimit;
- for (Long mandatoryOne : getCuboidStats().getAllCuboidsForMandatory())
{
+ for (Long mandatoryOne : cuboidStats.getAllCuboidsForMandatory()) {
selected.add(mandatoryOne);
- if (getCuboidStats().getCuboidSize(mandatoryOne) != null) {
- remainingSpace -= getCuboidStats().getCuboidSize(mandatoryOne);
+ if (cuboidStats.getCuboidSize(mandatoryOne) != null) {
+ remainingSpace -= cuboidStats.getCuboidSize(mandatoryOne);
}
}
//Initial remaining cuboid set
remaining.clear();
- remaining.addAll(getCuboidStats().getAllCuboidsForSelection());
+ remaining.addAll(cuboidStats.getAllCuboidsForSelection());
long round = 0;
while (true) {
@@ -95,18 +86,18 @@ public GreedyAlgorithm(final long timeout, BenefitPolicy
benefitPolicy, CuboidSt
// If we finally find the cuboid selected does not meet a minimum
threshold of benefit (for
// example, a cuboid with 0.99M roll up from a parent cuboid with
1M
// rows), then we should finish the process and return
- if (!getBenefitPolicy().ifEfficient(best)) {
+ if (!benefitPolicy.ifEfficient(best)) {
break;
}
- remainingSpace -=
getCuboidStats().getCuboidSize(best.getCuboidId());
+ remainingSpace -= cuboidStats.getCuboidSize(best.getCuboidId());
// If we finally find there is no remaining space, then we should
finish the process and return
if (remainingSpace <= 0) {
break;
}
selected.add(best.getCuboidId());
remaining.remove(best.getCuboidId());
- getBenefitPolicy().propagateAggregationCost(best.getCuboidId(),
selected);
+ benefitPolicy.propagateAggregationCost(best.getCuboidId(),
selected);
round++;
if (logger.isTraceEnabled()) {
logger.trace(String.format("Recommend in round %d : %s",
round, best.toString()));
@@ -126,10 +117,10 @@ public GreedyAlgorithm(final long timeout, BenefitPolicy
benefitPolicy, CuboidSt
logger.trace("Excluded cuboidId detail:");
for (Long cuboid : excluded) {
logger.trace(String.format("cuboidId %d and Cost: %d and
Space: %f", cuboid,
- getCuboidStats().getCuboidQueryCost(cuboid),
getCuboidStats().getCuboidSize(cuboid)));
+ cuboidStats.getCuboidQueryCost(cuboid),
cuboidStats.getCuboidSize(cuboid)));
}
logger.trace("Total Space:" + (spaceLimit - remainingSpace));
- logger.trace("Space Expansion Rate:" + (spaceLimit -
remainingSpace) / getCuboidStats().getBaseCuboidSize());
+ logger.trace("Space Expansion Rate:" + (spaceLimit -
remainingSpace) / cuboidStats.getBaseCuboidSize());
}
return Lists.newArrayList(selected);
}
@@ -145,13 +136,13 @@ private CuboidBenefitModel recommendBestOne() {
public void run() {
CuboidBenefitModel currentBest = best.get();
assert (selected.size() == selectedSize);
- CuboidBenefitModel.BenefitModel benefitModel =
getBenefitPolicy().calculateBenefit(cuboid, selected);
+ CuboidBenefitModel.BenefitModel benefitModel =
benefitPolicy.calculateBenefit(cuboid, selected);
if (benefitModel != null && (currentBest == null ||
currentBest.getBenefit() == null
- || benefitModel.getBenefit() >
currentBest.getBenefit())) {
+ || benefitModel.benefit >
currentBest.getBenefit())) {
while (!best.compareAndSet(currentBest,
- new
CuboidBenefitModel(getCuboidStats().getCuboidModel(cuboid), benefitModel))) {
+ new
CuboidBenefitModel(cuboidStats.getCuboidModel(cuboid), benefitModel))) {
currentBest = best.get();
- if (benefitModel.getBenefit() <=
currentBest.getBenefit()) {
+ if (benefitModel.benefit <=
currentBest.getBenefit()) {
break;
}
}
diff --git
a/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITAlgorithmTestBase.java
b/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITAlgorithmTestBase.java
index d8cc4e8485..797d0db86a 100755
---
a/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITAlgorithmTestBase.java
+++
b/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITAlgorithmTestBase.java
@@ -30,7 +30,6 @@
import org.apache.kylin.cube.cuboid.TreeCuboidScheduler.CuboidTree;
import org.junit.After;
import org.junit.Before;
-import org.junit.Test;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
@@ -57,14 +56,6 @@ public void setUp() throws Exception {
public void after() throws Exception {
}
- @Test
- public void testMandatoryRowCountEstimation() {
- for (long mandatoryCuboid : mandatoryCuboids) {
- System.out.println("Cuboid id: " + mandatoryCuboid + "; Row Count:
"
- + cuboidStats.getStatistics().get(mandatoryCuboid));
- }
- }
-
/** better if closer to 1, worse if closer to 0*/
public double getQueryCostRatio(CuboidStats cuboidStats, List<Long>
recommendList) {
CuboidTree cuboidTree = CuboidTree.createFromCuboids(recommendList,
diff --git
a/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITGeneticAlgorithmTest.java
b/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITGeneticAlgorithmTest.java
index 4f60307a9c..9ca7386815 100755
---
a/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITGeneticAlgorithmTest.java
+++
b/kylin-it/src/test/java/org/apache/kylin/cube/cuboid/algorithm/ITGeneticAlgorithmTest.java
@@ -18,14 +18,53 @@
package org.apache.kylin.cube.cuboid.algorithm;
-import java.util.List;
-
+import com.google.common.collect.Sets;
+import org.apache.commons.math3.genetics.Chromosome;
+import org.apache.kylin.cube.cuboid.algorithm.generic.BitsChromosome;
+import org.apache.kylin.cube.cuboid.algorithm.generic.BitsChromosomeHelper;
import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm;
import org.junit.Test;
+import java.util.BitSet;
+import java.util.List;
+import java.util.Set;
+
+import static org.junit.Assert.assertEquals;
+
//@Ignore("testBPUSCalculator() is unsable; whole test takes too long")
public class ITGeneticAlgorithmTest extends ITAlgorithmTestBase {
+ @Test
+ public void testChromosomeIsSame() {
+ BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats);
+
+ double maxSpaceLimit = cuboidStats.getBaseCuboidSize() * 10;
+ BitsChromosomeHelper helper = new BitsChromosomeHelper(maxSpaceLimit,
cuboidStats);
+
+ double maxSpaceLimit1 = cuboidStats.getBaseCuboidSize() * 12;
+ BitsChromosomeHelper helper1 = new
BitsChromosomeHelper(maxSpaceLimit1, cuboidStats);
+
+ BitSet representation = new BitSet();
+ representation.set(10);
+ Chromosome chromosome = new BitsChromosome(representation,
benefitPolicy, helper);
+ Set<Chromosome> chromosomeSet = Sets.newHashSet(chromosome);
+
+ BitSet representation1 = new BitSet();
+ representation1.set(10);
+ chromosomeSet.add(((BitsChromosome)
chromosome).newBitsChromosome(representation1));
+ assertEquals(1, chromosomeSet.size());
+
+ BitSet representation2 = new BitSet();
+ representation2.set(12);
+ chromosomeSet.add(((BitsChromosome)
chromosome).newBitsChromosome(representation2));
+ assertEquals(2, chromosomeSet.size());
+
+ BitSet representation3 = new BitSet();
+ representation3.set(12);
+ chromosomeSet.add(new BitsChromosome(representation3, benefitPolicy,
helper1));
+ assertEquals(2, chromosomeSet.size());
+ }
+
@Test
public void testBPUSCalculator() {
BenefitPolicy benefitPolicy = new BPUSCalculator(cuboidStats);
----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
[email protected]
With regards,
Apache Git Services
