You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@kylin.apache.org by nj...@apache.org on 2018/03/26 14:26:33 UTC
[kylin] branch master updated: KYLIN-3314 refactor code for cube
planner algorithm
This is an automated email from the ASF dual-hosted git repository.
nju_yaho pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/kylin.git
The following commit(s) were added to refs/heads/master by this push:
new 03316e2 KYLIN-3314 refactor code for cube planner algorithm
03316e2 is described below
commit 03316e2ebf5efed203ef16e2cd27b7541d3ff09d
Author: Wang Ken <mi...@ebay.com>
AuthorDate: Wed Mar 7 16:22:36 2018 +0800
KYLIN-3314 refactor code for cube planner algorithm
Signed-off-by: Zhong <nj...@apache.org>
---
.../algorithm/AbstractRecommendAlgorithm.java | 24 +--
.../cube/cuboid/algorithm/BPUSCalculator.java | 56 ++---
.../kylin/cube/cuboid/algorithm/BenefitPolicy.java | 21 +-
.../cube/cuboid/algorithm/CuboidBenefitModel.java | 144 +------------
.../kylin/cube/cuboid/algorithm/CuboidStats.java | 37 ++--
.../cube/cuboid/algorithm/PBPUSCalculator.java | 14 +-
.../cube/cuboid/algorithm/SPBPUSCalculator.java | 10 +-
.../cuboid/algorithm/generic/BitsChromosome.java | 138 ++++++------
.../algorithm/generic/BitsChromosomeHelper.java | 120 +++++++++++
.../algorithm/generic/{lib => }/BitsMutation.java | 28 ++-
...ntCrossover.java => BitsOnePointCrossover.java} | 55 ++---
.../generic/CombinedStoppingCondition.java | 4 +-
.../cuboid/algorithm/generic/CuboidEncoder.java | 44 ----
.../cuboid/algorithm/generic/GeneticAlgorithm.java | 237 ++++-----------------
.../algorithm/generic/RouletteWheelSelection.java | 13 +-
.../cuboid/algorithm/generic/lib/Chromosome.java | 106 ---------
.../generic/lib/ChromosomeMismatchException.java | 48 -----
.../algorithm/generic/lib/ChromosomePair.java | 69 ------
.../algorithm/generic/lib/CrossoverPolicy.java | 39 ----
.../generic/lib/ElitisticListPopulation.java | 119 -----------
.../cube/cuboid/algorithm/generic/lib/Fitness.java | 35 ---
.../generic/lib/FixedGenerationCount.java | 73 -------
.../algorithm/generic/lib/ListPopulation.java | 225 -------------------
.../algorithm/generic/lib/MutationPolicy.java | 36 ----
.../cuboid/algorithm/generic/lib/Population.java | 61 ------
.../algorithm/generic/lib/SelectionPolicy.java | 35 ---
.../algorithm/generic/lib/StoppingCondition.java | 36 ----
.../algorithm/generic/lib/TournamentSelection.java | 116 ----------
.../cuboid/algorithm/greedy/GreedyAlgorithm.java | 61 +++---
.../cube/cuboid/algorithm/ITAlgorithmTestBase.java | 9 -
.../cuboid/algorithm/ITGeneticAlgorithmTest.java | 43 +++-
31 files changed, 447 insertions(+), 1609 deletions(-)
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 b35c738..094b960 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);
@@ -45,13 +46,18 @@ public abstract class AbstractRecommendAlgorithm implements CuboidRecommendAlgor
}
@Override
+ public List<Long> recommend(double expansionRate) {
+ double spaceLimit = cuboidStats.getBaseCuboidSize() * expansionRate;
+ return start(spaceLimit);
+ }
+
+ @Override
public void cancel() {
cancelRequested.set(true);
}
/**
* Checks whether the algorithm has been canceled or timed out.
- *
*/
protected boolean shouldCancel() {
if (canceled.get()) {
@@ -71,12 +77,4 @@ public abstract class AbstractRecommendAlgorithm implements CuboidRecommendAlgor
}
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 6d0b654..e293325 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 @@ public class BPUSCalculator implements BenefitPolicy {
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 class BPUSCalculator implements BenefitPolicy {
}
cuboidAggCostMap.put(cuboid, leastCost);
}
+ return cuboidAggCostMap;
}
@Override
@@ -88,22 +95,21 @@ public class BPUSCalculator implements BenefitPolicy {
}
@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 @@ public class BPUSCalculator implements BenefitPolicy {
}
private long getCuboidAggregationCost(long cuboid) {
- return cuboidAggCostMap.get(cuboid);
+ return processCuboidAggCostMap.get(cuboid);
}
@Override
@@ -139,11 +145,15 @@ public class BPUSCalculator implements BenefitPolicy {
@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 class BPUSCalculator implements BenefitPolicy {
@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 43bd3af..a10e51f 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 @@ import java.util.Set;
*/
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 42f1ecf..7e1edf5 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 class CuboidBenefitModel {
}
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 class CuboidBenefitModel {
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 class CuboidBenefitModel {
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 a1c191e..78a6c5b 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 class CuboidStats {
}
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 class CuboidStats {
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 @@ public class CuboidStats {
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 @@ public class CuboidStats {
/** 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 @@ public class CuboidStats {
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 @@ public class CuboidStats {
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 @@ public class CuboidStats {
}
}
- 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 6d3ddc7..9fddaec 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 class PBPUSCalculator extends BPUSCalculator {
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 @@ public class PBPUSCalculator extends BPUSCalculator {
}
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 c89bf49..e235de3 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 class SPBPUSCalculator extends PBPUSCalculator {
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 @@ public class SPBPUSCalculator extends PBPUSCalculator {
@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 6445ca6..81d7e20 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 @@ public class BitsChromosome extends Chromosome {
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 0000000..2b5d143
--- /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 073b947..2cd4b99 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 class BitsMutation implements MutationPolicy {
*/
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 5ef8cfa..00559d3
--- 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 @@ import org.apache.kylin.cube.cuboid.algorithm.generic.GeneticAlgorithm;
* /------------\ /-----\ /------------\ /-----\
* 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 @@ public class OnePointCrossover implements CrossoverPolicy {
* 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 class OnePointCrossover implements CrossoverPolicy {
/**
* 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 @@ public class OnePointCrossover implements CrossoverPolicy {
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 bc4bb99..a12c44d 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 7e48413..0000000
--- 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 ce4dc3e..27d59fa 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 class GeneticAlgorithm extends AbstractRecommendAlgorithm {
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 class GeneticAlgorithm extends AbstractRecommendAlgorithm {
}
}
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 b93ed31..555e57e 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 class RouletteWheelSelection implements SelectionPolicy {
}
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 a58abb1..0000000
--- 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 51d5cb3..0000000
--- 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 aa0f9df..0000000
--- 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 397075c..0000000
--- 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 f35b2e2..0000000
--- 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 9713f25..0000000
--- 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 ff45fa2..0000000
--- 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 435dc72..0000000
--- 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 183483a..0000000
--- 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 c22f518..0000000
--- 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 7ac14c5..0000000
--- 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 bf3a26d..0000000
--- 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 158ccd2..0000000
--- 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 5dbe189..0f2dcc3 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.apache.kylin.cube.cuboid.algorithm.CuboidStats;
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);
@@ -55,31 +54,23 @@ public class GreedyAlgorithm extends AbstractRecommendAlgorithm {
}
@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 class GreedyAlgorithm extends AbstractRecommendAlgorithm {
// 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 class GreedyAlgorithm extends AbstractRecommendAlgorithm {
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 @@ public class GreedyAlgorithm extends AbstractRecommendAlgorithm {
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 d8cc4e8..797d0db 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.CuboidCostComparator;
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 class ITAlgorithmTestBase {
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 4f60307..9ca7386 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,15 +18,54 @@
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);
GeneticAlgorithm algorithm = new GeneticAlgorithm(-1, benefitPolicy, cuboidStats);
--
To stop receiving notification emails like this one, please contact
nju_yaho@apache.org.