-
Enhancement
-
Resolution: Done
-
Major
-
7.23.0.Final
-
None
-
NEW
-
NEW
I provide code and a benchmark proving my hypothesis.
The current implementation ("DEFAULT") picks subpillars like this:
@Override
protected List<Object> createUpcomingSelection() {
List<Object> basePillar = selectBasePillar();
int basePillarSize = basePillar.size();
int min = (minimumSubPillarSize > basePillarSize) ? basePillarSize : minimumSubPillarSize;
int max = (maximumSubPillarSize > basePillarSize) ? basePillarSize : maximumSubPillarSize;
int subPillarSize = min + workingRandom.nextInt(max - min + 1);
Object[] sandboxPillar = basePillar.toArray();
List<Object> subPillar = new ArrayList<>(subPillarSize);
for (int i = 0; i < subPillarSize; i++) {
int index = i + workingRandom.nextInt(basePillarSize - i);
subPillar.add(sandboxPillar[index]);
sandboxPillar[index] = sandboxPillar[i];
}
return subPillar;
}
A better implementation ("LESS_RANDOM_AND_SIZED"), providing an average 10+ % ACC increase, would look like this:
@Override
protected List<Object> createUpcomingSelection() {
List<Object> basePillar = selectBasePillar();
int basePillarSize = basePillar.size();
int min = (minimumSubPillarSize > basePillarSize) ? basePillarSize : minimumSubPillarSize;
int max = (maximumSubPillarSize > basePillarSize) ? basePillarSize : maximumSubPillarSize;
int subPillarSize = min + workingRandom.nextInt(max - min + 1);
if (subPillarSize == basePillarSize) {
return basePillar;
}
return IntStream.generate(() -> workingRandom.nextInt(basePillarSize))
.distinct()
.limit(subPillarSize)
.sorted()
.mapToObj(basePillar::get)
.collect(Collectors.toCollection(() -> new ArrayList<>(subPillarSize)));
}
I also provide a "SEQUENTIAL" implementation, which sits in the middle, still better than "DEFAULT":
@Override
protected List<Object> createUpcomingSelection() {
List<Object> basePillar = selectBasePillar();
int basePillarSize = basePillar.size();
int min = (minimumSubPillarSize > basePillarSize) ? basePillarSize : minimumSubPillarSize;
int max = (maximumSubPillarSize > basePillarSize) ? basePillarSize : maximumSubPillarSize;
int subPillarSize = min + workingRandom.nextInt(max - min + 1);
if (subPillarSize == basePillarSize) {
return basePillar;
}
final int startIndexRange = basePillarSize - subPillarSize;
final int newStartIndex = workingRandom.nextInt(startIndexRange + 1);
final List<Object> subPillar = basePillar.subList(newStartIndex, newStartIndex + subPillarSize);
return new ArrayList<>(subPillar);
}
Here's the differences between the implementations:
- DEFAULT randomly chooses elements from a base pillar. So, from a pillar ABCD, it may randomly choose ABC or AD. Unfortunately, it can also choose ACB, reordering the elements. Although this doesn't hurt, it is unnecessary and complicates the algorithm.
- LESS_RANDOM_AND_SIZED also randomly chooses elements from a base pillar. But it only randomly generates the indexes, removing the possibility to reorder the subpillar. This results in less collection-related operations, and a faster algorithm overall.
- SEQUENTIAL implementation only randomly picks an index in the pillar, which will be the beginning of the subpillar. All the other elements in the subpillar are those that are directly following it in the base pillar.
If we decide that the DEFAULT should be replaced, I will provide a PR incl. tests.
- relates to
-
PLANNER-1600 Move selectors that understand entity sequences
-
- Resolved
-
