This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch remove_duplicate_doubles_sorted_views in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 5f8fc5c22dcaf2dfeb30f68b97d872e711237f94 Author: Lee Rhodes <[email protected]> AuthorDate: Wed Mar 20 16:38:22 2024 -0700 Removed the duplicate Doubles Sorted Views between KLL and Classic quantiles. This had a rippling effect across a number of classes. --- .../apache/datasketches/kll/KllDoublesSketch.java | 167 ++++++++-- .../kll/KllDoublesSketchSortedView.java | 129 +------- .../apache/datasketches/kll/KllItemsSketch.java | 3 +- .../quantiles/CompactDoublesSketch.java | 2 +- .../quantiles/DirectDoublesSketchAccessor.java | 1 + .../quantiles/DirectUpdateDoublesSketch.java | 2 +- .../quantiles/DoublesArrayAccessor.java | 3 +- .../quantiles/DoublesBufferAccessor.java | 4 +- .../datasketches/quantiles/DoublesSketch.java | 250 ++++++++++++++- .../quantiles/DoublesSketchSortedView.java | 354 --------------------- .../datasketches/quantiles/DoublesUnionImpl.java | 6 +- .../quantiles/HeapUpdateDoublesSketch.java | 2 +- .../apache/datasketches/quantiles/ItemsSketch.java | 131 ++++---- .../datasketches/quantiles/KolmogorovSmirnov.java | 6 +- .../quantilescommon/DoublesSketchSortedView.java | 118 +++++++ .../quantiles/CustomQuantilesTest.java | 3 +- .../apache/datasketches/quantiles/UtilTest.java | 3 +- .../quantilescommon/CrossCheckQuantilesTest.java | 29 +- .../quantilescommon/ReflectUtilityTest.java | 15 +- 19 files changed, 603 insertions(+), 625 deletions(-) diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java index 8883734c..ab241f7b 100644 --- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketch.java @@ -25,6 +25,7 @@ import static org.apache.datasketches.common.ByteArrayUtil.putDoubleLE; import static org.apache.datasketches.kll.KllSketch.SketchStructure.UPDATABLE; import static org.apache.datasketches.kll.KllSketch.SketchType.DOUBLES_SKETCH; +import java.util.Arrays; import java.util.Objects; import org.apache.datasketches.common.ArrayOfItemsSerDe; @@ -35,7 +36,7 @@ import org.apache.datasketches.memory.DefaultMemoryRequestServer; import org.apache.datasketches.memory.Memory; import org.apache.datasketches.memory.MemoryRequestServer; import org.apache.datasketches.memory.WritableMemory; -import org.apache.datasketches.quantilescommon.DoublesSortedView; +import org.apache.datasketches.quantilescommon.DoublesSketchSortedView; import org.apache.datasketches.quantilescommon.QuantileSearchCriteria; import org.apache.datasketches.quantilescommon.QuantilesDoublesAPI; import org.apache.datasketches.quantilescommon.QuantilesDoublesSketchIterator; @@ -46,7 +47,7 @@ import org.apache.datasketches.quantilescommon.QuantilesDoublesSketchIterator; * @see org.apache.datasketches.kll.KllSketch */ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDoublesAPI { - private KllDoublesSketchSortedView kllDoublesSV = null; + private DoublesSketchSortedView doublesSV = null; final static int ITEM_BYTES = Double.BYTES; KllDoublesSketch( @@ -171,21 +172,21 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou public double[] getCDF(final double[] splitPoints, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } refreshSortedView(); - return kllDoublesSV.getCDF(splitPoints, searchCrit); + return doublesSV.getCDF(splitPoints, searchCrit); } @Override public double[] getPMF(final double[] splitPoints, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } refreshSortedView(); - return kllDoublesSV.getPMF(splitPoints, searchCrit); + return doublesSV.getPMF(splitPoints, searchCrit); } @Override public double getQuantile(final double rank, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } refreshSortedView(); - return kllDoublesSV.getQuantile(rank, searchCrit); + return doublesSV.getQuantile(rank, searchCrit); } @Override @@ -195,7 +196,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou final int len = ranks.length; final double[] quantiles = new double[len]; for (int i = 0; i < len; i++) { - quantiles[i] = kllDoublesSV.getQuantile(ranks[i], searchCrit); + quantiles[i] = doublesSV.getQuantile(ranks[i], searchCrit); } return quantiles; } @@ -224,7 +225,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou public double getRank(final double quantile, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } refreshSortedView(); - return kllDoublesSV.getRank(quantile, searchCrit); + return doublesSV.getRank(quantile, searchCrit); } /** @@ -254,17 +255,17 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou final int len = quantiles.length; final double[] ranks = new double[len]; for (int i = 0; i < len; i++) { - ranks[i] = kllDoublesSV.getRank(quantiles[i], searchCrit); + ranks[i] = doublesSV.getRank(quantiles[i], searchCrit); } return ranks; } @Override @SuppressFBWarnings(value = "EI_EXPOSE_REP", justification = "OK in this case.") - public DoublesSortedView getSortedView() { + public DoublesSketchSortedView getSortedView() { if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } refreshSortedView(); - return kllDoublesSV; + return doublesSV; } @Override @@ -278,9 +279,9 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou if (readOnly || sketchStructure != UPDATABLE) { throw new SketchesArgumentException(TGT_IS_READ_ONLY_MSG); } if (this == other) { throw new SketchesArgumentException(SELF_MERGE_MSG); } final KllDoublesSketch othDblSk = (KllDoublesSketch)other; - if (othDblSk.isEmpty()) { return; } //then check empty + if (othDblSk.isEmpty()) { return; } KllDoublesHelper.mergeDoubleImpl(this, othDblSk); - kllDoublesSV = null; + doublesSV = null; } /** @@ -299,7 +300,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou setMinItem(Double.NaN); setMaxItem(Double.NaN); setDoubleItemsArray(new double[k]); - kllDoublesSV = null; + doublesSV = null; } @Override @@ -323,7 +324,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou if (Double.isNaN(item)) { return; } //ignore if (readOnly) { throw new SketchesArgumentException(TGT_IS_READ_ONLY_MSG); } KllDoublesHelper.updateDouble(this, item); - kllDoublesSV = null; + doublesSV = null; } /** @@ -337,7 +338,7 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou if (weight < 1L) { throw new SketchesArgumentException("Weight is less than one."); } if (weight == 1L) { KllDoublesHelper.updateDouble(this, item); } else { KllDoublesHelper.updateDouble(this, item, weight); } - kllDoublesSV = null; + doublesSV = null; } //restricted @@ -393,11 +394,6 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou return levelsArr[getNumLevels()] * Double.BYTES; } - private final void refreshSortedView() { - kllDoublesSV = (kllDoublesSV == null) - ? new KllDoublesSketchSortedView(this) : kllDoublesSV; - } - abstract void setDoubleItemsArray(double[] doubleItems); abstract void setDoubleItemsArrayAt(int index, double item); @@ -416,4 +412,135 @@ public abstract class KllDoublesSketch extends KllSketch implements QuantilesDou } } + private final DoublesSketchSortedView refreshSortedView() { + if (doublesSV == null) { + final CreateSortedView csv = new CreateSortedView(); + doublesSV = csv.getSV(); + } + return doublesSV; + } + + private final class CreateSortedView { + double[] quantiles; + long[] cumWeights; + + DoublesSketchSortedView getSV() { + if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } + if (getN() == 0) { throw new SketchesArgumentException(EMPTY_MSG); } + final double[] srcQuantiles = getDoubleItemsArray(); + final int[] srcLevels = levelsArr; + final int srcNumLevels = getNumLevels(); + + if (!isLevelZeroSorted()) { + Arrays.sort(srcQuantiles, srcLevels[0], srcLevels[1]); + if (!hasMemory()) { setLevelZeroSorted(true); } + } + final int numQuantiles = getNumRetained(); + quantiles = new double[numQuantiles]; + cumWeights = new long[numQuantiles]; + populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles); + return new DoublesSketchSortedView( + quantiles, cumWeights, getN(), getMaxItem(), getMinItem()); + } + + private void populateFromSketch(final double[] srcQuantiles, final int[] srcLevels, + final int srcNumLevels, final int numItems) { + final int[] myLevels = new int[srcNumLevels + 1]; + final int offset = srcLevels[0]; + System.arraycopy(srcQuantiles, offset, quantiles, 0, numItems); + int srcLevel = 0; + int dstLevel = 0; + long weight = 1; + while (srcLevel < srcNumLevels) { + final int fromIndex = srcLevels[srcLevel] - offset; + final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive + if (fromIndex < toIndex) { // if equal, skip empty level + Arrays.fill(cumWeights, fromIndex, toIndex, weight); + myLevels[dstLevel] = fromIndex; + myLevels[dstLevel + 1] = toIndex; + dstLevel++; + } + srcLevel++; + weight *= 2; + } + final int numLevels = dstLevel; + blockyTandemMergeSort(quantiles, cumWeights, myLevels, numLevels); //create unit weights + KllHelper.convertToCumulative(cumWeights); + } + } //End of class CreateSortedView + + private static void blockyTandemMergeSort(final double[] quantiles, final long[] weights, + final int[] levels, final int numLevels) { + if (numLevels == 1) { return; } + + // duplicate the input in preparation for the "ping-pong" copy reduction strategy. + final double[] quantilesTmp = Arrays.copyOf(quantiles, quantiles.length); + final long[] weightsTmp = Arrays.copyOf(weights, quantiles.length); // don't need the extra one + + blockyTandemMergeSortRecursion(quantilesTmp, weightsTmp, quantiles, weights, levels, 0, numLevels); + } + + private static void blockyTandemMergeSortRecursion( + final double[] quantilesSrc, final long[] weightsSrc, + final double[] quantilesDst, final long[] weightsDst, + final int[] levels, final int startingLevel, final int numLevels) { + if (numLevels == 1) { return; } + final int numLevels1 = numLevels / 2; + final int numLevels2 = numLevels - numLevels1; + assert numLevels1 >= 1; + assert numLevels2 >= numLevels1; + final int startingLevel1 = startingLevel; + final int startingLevel2 = startingLevel + numLevels1; + // swap roles of src and dst + blockyTandemMergeSortRecursion( + quantilesDst, weightsDst, + quantilesSrc, weightsSrc, + levels, startingLevel1, numLevels1); + blockyTandemMergeSortRecursion( + quantilesDst, weightsDst, + quantilesSrc, weightsSrc, + levels, startingLevel2, numLevels2); + tandemMerge( + quantilesSrc, weightsSrc, + quantilesDst, weightsDst, + levels, + startingLevel1, numLevels1, + startingLevel2, numLevels2); + } + + private static void tandemMerge( + final double[] quantilesSrc, final long[] weightsSrc, + final double[] quantilesDst, final long[] weightsDst, + final int[] levelStarts, + final int startingLevel1, final int numLevels1, + final int startingLevel2, final int numLevels2) { + final int fromIndex1 = levelStarts[startingLevel1]; + final int toIndex1 = levelStarts[startingLevel1 + numLevels1]; // exclusive + final int fromIndex2 = levelStarts[startingLevel2]; + final int toIndex2 = levelStarts[startingLevel2 + numLevels2]; // exclusive + int iSrc1 = fromIndex1; + int iSrc2 = fromIndex2; + int iDst = fromIndex1; + + while (iSrc1 < toIndex1 && iSrc2 < toIndex2) { + if (quantilesSrc[iSrc1] < quantilesSrc[iSrc2]) { + quantilesDst[iDst] = quantilesSrc[iSrc1]; + weightsDst[iDst] = weightsSrc[iSrc1]; + iSrc1++; + } else { + quantilesDst[iDst] = quantilesSrc[iSrc2]; + weightsDst[iDst] = weightsSrc[iSrc2]; + iSrc2++; + } + iDst++; + } + if (iSrc1 < toIndex1) { + System.arraycopy(quantilesSrc, iSrc1, quantilesDst, iDst, toIndex1 - iSrc1); + System.arraycopy(weightsSrc, iSrc1, weightsDst, iDst, toIndex1 - iSrc1); + } else if (iSrc2 < toIndex2) { + System.arraycopy(quantilesSrc, iSrc2, quantilesDst, iDst, toIndex2 - iSrc2); + System.arraycopy(weightsSrc, iSrc2, weightsDst, iDst, toIndex2 - iSrc2); + } + } + } diff --git a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java index 13f0a9df..a8eaccad 100644 --- a/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java +++ b/src/main/java/org/apache/datasketches/kll/KllDoublesSketchSortedView.java @@ -23,8 +23,6 @@ import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INC import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG; import static org.apache.datasketches.quantilescommon.QuantilesUtil.getNaturalRank; -import java.util.Arrays; - import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.quantilescommon.DoublesSortedView; import org.apache.datasketches.quantilescommon.DoublesSortedViewIterator; @@ -49,6 +47,8 @@ public final class KllDoublesSketchSortedView implements DoublesSortedView { * @param quantiles sorted array of quantiles * @param cumWeights sorted, monotonically increasing cumulative weights. * @param totalN the total number of items presented to the sketch. + * @param maxItem of type double + * @param minItem of type double */ KllDoublesSketchSortedView(final double[] quantiles, final long[] cumWeights, final long totalN, final double maxItem, final double minItem) { @@ -59,30 +59,6 @@ public final class KllDoublesSketchSortedView implements DoublesSortedView { this.minItem = minItem; } - /** - * Constructs this Sorted View given the sketch - * @param sketch the given KllDoublesSketch. - */ - public KllDoublesSketchSortedView(final KllDoublesSketch sketch) { - if (sketch.isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } - this.totalN = sketch.getN(); - this.maxItem = sketch.getMaxItem(); - this.minItem = sketch.getMinItem(); - final double[] srcQuantiles = sketch.getDoubleItemsArray(); - final int[] srcLevels = sketch.levelsArr; - final int srcNumLevels = sketch.getNumLevels(); - - if (!sketch.isLevelZeroSorted()) { - Arrays.sort(srcQuantiles, srcLevels[0], srcLevels[1]); - if (!sketch.hasMemory()) { sketch.setLevelZeroSorted(true); } - } - - final int numQuantiles = srcLevels[srcNumLevels] - srcLevels[0]; //remove free space - quantiles = new double[numQuantiles]; - cumWeights = new long[numQuantiles]; - populateFromSketch(srcQuantiles, srcLevels, srcNumLevels, numQuantiles); - } - @Override public long[] getCumulativeWeights() { return cumWeights.clone(); @@ -144,105 +120,4 @@ public final class KllDoublesSketchSortedView implements DoublesSortedView { return new DoublesSortedViewIterator(quantiles, cumWeights); } - //restricted methods - - private void populateFromSketch(final double[] srcQuantiles, final int[] srcLevels, - final int srcNumLevels, final int numItems) { - final int[] myLevels = new int[srcNumLevels + 1]; - final int offset = srcLevels[0]; - System.arraycopy(srcQuantiles, offset, quantiles, 0, numItems); - int srcLevel = 0; - int dstLevel = 0; - long weight = 1; - while (srcLevel < srcNumLevels) { - final int fromIndex = srcLevels[srcLevel] - offset; - final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive - if (fromIndex < toIndex) { // if equal, skip empty level - Arrays.fill(cumWeights, fromIndex, toIndex, weight); - myLevels[dstLevel] = fromIndex; - myLevels[dstLevel + 1] = toIndex; - dstLevel++; - } - srcLevel++; - weight *= 2; - } - final int numLevels = dstLevel; - blockyTandemMergeSort(quantiles, cumWeights, myLevels, numLevels); //create unit weights - KllHelper.convertToCumulative(cumWeights); - } - - private static void blockyTandemMergeSort(final double[] quantiles, final long[] weights, - final int[] levels, final int numLevels) { - if (numLevels == 1) { return; } - - // duplicate the input in preparation for the "ping-pong" copy reduction strategy. - final double[] quantilesTmp = Arrays.copyOf(quantiles, quantiles.length); - final long[] weightsTmp = Arrays.copyOf(weights, quantiles.length); // don't need the extra one - - blockyTandemMergeSortRecursion(quantilesTmp, weightsTmp, quantiles, weights, levels, 0, numLevels); - } - - private static void blockyTandemMergeSortRecursion( - final double[] quantilesSrc, final long[] weightsSrc, - final double[] quantilesDst, final long[] weightsDst, - final int[] levels, final int startingLevel, final int numLevels) { - if (numLevels == 1) { return; } - final int numLevels1 = numLevels / 2; - final int numLevels2 = numLevels - numLevels1; - assert numLevels1 >= 1; - assert numLevels2 >= numLevels1; - final int startingLevel1 = startingLevel; - final int startingLevel2 = startingLevel + numLevels1; - // swap roles of src and dst - blockyTandemMergeSortRecursion( - quantilesDst, weightsDst, - quantilesSrc, weightsSrc, - levels, startingLevel1, numLevels1); - blockyTandemMergeSortRecursion( - quantilesDst, weightsDst, - quantilesSrc, weightsSrc, - levels, startingLevel2, numLevels2); - tandemMerge( - quantilesSrc, weightsSrc, - quantilesDst, weightsDst, - levels, - startingLevel1, numLevels1, - startingLevel2, numLevels2); - } - - private static void tandemMerge( - final double[] quantilesSrc, final long[] weightsSrc, - final double[] quantilesDst, final long[] weightsDst, - final int[] levelStarts, - final int startingLevel1, final int numLevels1, - final int startingLevel2, final int numLevels2) { - final int fromIndex1 = levelStarts[startingLevel1]; - final int toIndex1 = levelStarts[startingLevel1 + numLevels1]; // exclusive - final int fromIndex2 = levelStarts[startingLevel2]; - final int toIndex2 = levelStarts[startingLevel2 + numLevels2]; // exclusive - int iSrc1 = fromIndex1; - int iSrc2 = fromIndex2; - int iDst = fromIndex1; - - while (iSrc1 < toIndex1 && iSrc2 < toIndex2) { - if (quantilesSrc[iSrc1] < quantilesSrc[iSrc2]) { - quantilesDst[iDst] = quantilesSrc[iSrc1]; - weightsDst[iDst] = weightsSrc[iSrc1]; - iSrc1++; - } else { - quantilesDst[iDst] = quantilesSrc[iSrc2]; - weightsDst[iDst] = weightsSrc[iSrc2]; - iSrc2++; - } - iDst++; - } - if (iSrc1 < toIndex1) { - System.arraycopy(quantilesSrc, iSrc1, quantilesDst, iDst, toIndex1 - iSrc1); - System.arraycopy(weightsSrc, iSrc1, weightsDst, iDst, toIndex1 - iSrc1); - } else if (iSrc2 < toIndex2) { - System.arraycopy(quantilesSrc, iSrc2, quantilesDst, iDst, toIndex2 - iSrc2); - System.arraycopy(weightsSrc, iSrc2, weightsDst, iDst, toIndex2 - iSrc2); - } - } - } diff --git a/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java b/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java index 273a89bc..9f5a5ae7 100644 --- a/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java +++ b/src/main/java/org/apache/datasketches/kll/KllItemsSketch.java @@ -242,7 +242,6 @@ public abstract class KllItemsSketch<T> extends KllSketch implements QuantilesGe public final ItemsSketchSortedView<T> getSortedView() { if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } return refreshSortedView(); - //return itemsSV; //SpotBugs EI_EXPOSE_REP, Suppressed by FindBugsExcludeFilter } @Override @@ -454,7 +453,7 @@ public abstract class KllItemsSketch<T> extends KllSketch implements QuantilesGe blockyTandemMergeSort(quantiles, cumWeights, myLevels, numLevels, comparator); //create unit weights KllHelper.convertToCumulative(cumWeights); } - } + } //End of class CreateSortedView private static <T> void blockyTandemMergeSort(final Object[] quantiles, final long[] weights, final int[] levels, final int numLevels, final Comparator<? super T> comp) { diff --git a/src/main/java/org/apache/datasketches/quantiles/CompactDoublesSketch.java b/src/main/java/org/apache/datasketches/quantiles/CompactDoublesSketch.java index 81c9e6db..f6df9e87 100644 --- a/src/main/java/org/apache/datasketches/quantiles/CompactDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/quantiles/CompactDoublesSketch.java @@ -23,7 +23,7 @@ import org.apache.datasketches.common.SketchesStateException; import org.apache.datasketches.memory.Memory; /** - * Compact sketches are inherently <i>read ony</i>. + * Compact sketches are inherently <i>read only</i>. * @author Jon Malkin */ public abstract class CompactDoublesSketch extends DoublesSketch { diff --git a/src/main/java/org/apache/datasketches/quantiles/DirectDoublesSketchAccessor.java b/src/main/java/org/apache/datasketches/quantiles/DirectDoublesSketchAccessor.java index 172ad14b..b95c9f12 100644 --- a/src/main/java/org/apache/datasketches/quantiles/DirectDoublesSketchAccessor.java +++ b/src/main/java/org/apache/datasketches/quantiles/DirectDoublesSketchAccessor.java @@ -27,6 +27,7 @@ import org.apache.datasketches.memory.WritableMemory; * @author Jon Malkin */ final class DirectDoublesSketchAccessor extends DoublesSketchAccessor { + DirectDoublesSketchAccessor(final DoublesSketch ds, final boolean forceSize, final int level) { diff --git a/src/main/java/org/apache/datasketches/quantiles/DirectUpdateDoublesSketch.java b/src/main/java/org/apache/datasketches/quantiles/DirectUpdateDoublesSketch.java index 384b4266..96c01d93 100644 --- a/src/main/java/org/apache/datasketches/quantiles/DirectUpdateDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/quantiles/DirectUpdateDoublesSketch.java @@ -193,7 +193,7 @@ final class DirectUpdateDoublesSketch extends DirectUpdateDoublesSketchR { //bit pattern on direct is always derived, no need to save it. } putN(newN); - classicQdsSV = null; + doublesSV = null; } @Override diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesArrayAccessor.java b/src/main/java/org/apache/datasketches/quantiles/DoublesArrayAccessor.java index dd740fb7..7fcf38a2 100644 --- a/src/main/java/org/apache/datasketches/quantiles/DoublesArrayAccessor.java +++ b/src/main/java/org/apache/datasketches/quantiles/DoublesArrayAccessor.java @@ -67,8 +67,7 @@ final class DoublesArrayAccessor extends DoublesBufferAccessor { } @Override - void putArray(final double[] srcArray, final int srcIndex, - final int dstIndex, final int numItems) { + void putArray(final double[] srcArray, final int srcIndex, final int dstIndex, final int numItems) { System.arraycopy(srcArray, srcIndex, buffer_, dstIndex, numItems); } diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesBufferAccessor.java b/src/main/java/org/apache/datasketches/quantiles/DoublesBufferAccessor.java index c3b0f9b6..1014a104 100644 --- a/src/main/java/org/apache/datasketches/quantiles/DoublesBufferAccessor.java +++ b/src/main/java/org/apache/datasketches/quantiles/DoublesBufferAccessor.java @@ -23,6 +23,7 @@ package org.apache.datasketches.quantiles; * @author Jon Malkin */ abstract class DoublesBufferAccessor { + abstract double get(final int index); abstract double set(final int index, final double quantile); @@ -31,6 +32,5 @@ abstract class DoublesBufferAccessor { abstract double[] getArray(int fromIdx, int numItems); - abstract void putArray(double[] srcArray, int srcIndex, - int dstIndex, int numItems); + abstract void putArray(double[] srcArray, int srcIndex, int dstIndex, int numItems); } diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java b/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java index 93858c38..11dcc425 100644 --- a/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java +++ b/src/main/java/org/apache/datasketches/quantiles/DoublesSketch.java @@ -21,6 +21,7 @@ package org.apache.datasketches.quantiles; import static java.lang.Math.max; import static java.lang.Math.min; +import static java.lang.System.arraycopy; import static org.apache.datasketches.common.Util.ceilingPowerOf2; import static org.apache.datasketches.quantiles.ClassicUtil.MAX_PRELONGS; import static org.apache.datasketches.quantiles.ClassicUtil.MIN_K; @@ -28,13 +29,16 @@ import static org.apache.datasketches.quantiles.ClassicUtil.checkIsCompactMemory import static org.apache.datasketches.quantiles.ClassicUtil.checkK; import static org.apache.datasketches.quantiles.ClassicUtil.computeNumLevelsNeeded; import static org.apache.datasketches.quantiles.ClassicUtil.computeRetainedItems; +import static org.apache.datasketches.quantiles.DoublesSketchAccessor.BB_LVL_IDX; +import java.util.Arrays; import java.util.Random; import org.apache.datasketches.common.SketchesArgumentException; +import org.apache.datasketches.common.SketchesStateException; import org.apache.datasketches.memory.Memory; import org.apache.datasketches.memory.WritableMemory; -import org.apache.datasketches.quantilescommon.DoublesSortedView; +import org.apache.datasketches.quantilescommon.DoublesSketchSortedView; import org.apache.datasketches.quantilescommon.QuantileSearchCriteria; import org.apache.datasketches.quantilescommon.QuantilesAPI; import org.apache.datasketches.quantilescommon.QuantilesDoublesAPI; @@ -108,7 +112,7 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { */ final int k_; - DoublesSketchSortedView classicQdsSV = null; + DoublesSketchSortedView doublesSV = null; DoublesSketch(final int k) { checkK(k); @@ -160,7 +164,7 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { public double[] getCDF(final double[] splitPoints, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); } refreshSortedView(); - return classicQdsSV.getCDF(splitPoints, searchCrit); + return doublesSV.getCDF(splitPoints, searchCrit); } @Override @@ -173,14 +177,14 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { public double[] getPMF(final double[] splitPoints, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); } refreshSortedView(); - return classicQdsSV.getPMF(splitPoints, searchCrit); + return doublesSV.getPMF(splitPoints, searchCrit); } @Override public double getQuantile(final double rank, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); } refreshSortedView(); - return classicQdsSV.getQuantile(rank, searchCrit); + return doublesSV.getQuantile(rank, searchCrit); } @Override @@ -190,7 +194,7 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { final int len = ranks.length; final double[] quantiles = new double[len]; for (int i = 0; i < len; i++) { - quantiles[i] = classicQdsSV.getQuantile(ranks[i], searchCrit); + quantiles[i] = doublesSV.getQuantile(ranks[i], searchCrit); } return quantiles; } @@ -219,7 +223,7 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { public double getRank(final double quantile, final QuantileSearchCriteria searchCrit) { if (isEmpty()) { throw new IllegalArgumentException(QuantilesAPI.EMPTY_MSG); } refreshSortedView(); - return classicQdsSV.getRank(quantile, searchCrit); + return doublesSV.getRank(quantile, searchCrit); } /** @@ -249,7 +253,7 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { final int len = quantiles.length; final double[] ranks = new double[len]; for (int i = 0; i < len; i++) { - ranks[i] = classicQdsSV.getRank(quantiles[i], searchCrit); + ranks[i] = doublesSV.getRank(quantiles[i], searchCrit); } return ranks; } @@ -508,11 +512,6 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { return new DoublesSketchIterator(this, getBitPattern()); } - @Override - public DoublesSortedView getSortedView() { - return new DoublesSketchSortedView(this); - } - /** * {@inheritDoc} * <p>The parameter <i>k</i> will not change.</p> @@ -538,10 +537,6 @@ public abstract class DoublesSketch implements QuantilesDoublesAPI { return newSketch; } -private final void refreshSortedView() { - classicQdsSV = (classicQdsSV == null) ? new DoublesSketchSortedView(this) : classicQdsSV; -} - //Restricted abstract /** @@ -579,4 +574,225 @@ private final void refreshSortedView() { * @return the Memory if it exists, otherwise returns null. */ abstract WritableMemory getMemory(); + + //************SORTED VIEW**************************** + + @Override + public DoublesSketchSortedView getSortedView() { + return refreshSortedView(); + } + + private final DoublesSketchSortedView refreshSortedView() { + return (doublesSV == null) ? (doublesSV = getSV()) : doublesSV; + } + + private DoublesSketchSortedView getSV() { + final long totalN = getN(); + if (isEmpty() || (totalN == 0)) { throw new SketchesArgumentException(EMPTY_MSG); } + final int numQuantiles = getNumRetained(); + final double[] svQuantiles = new double[numQuantiles]; + final long[] svCumWeights = new long[numQuantiles]; + final DoublesSketchAccessor sketchAccessor = DoublesSketchAccessor.wrap(this); + + // Populate from DoublesSketch: + // copy over the "levels" and then the base buffer, all with appropriate weights + populateFromDoublesSketch(getK(), totalN, getBitPattern(), sketchAccessor, svQuantiles, svCumWeights); + + // Sort the first "numSamples" slots of the two arrays in tandem, + // taking advantage of the already sorted blocks of length k + blockyTandemMergeSort(svQuantiles, svCumWeights, numQuantiles, getK()); + + if (convertToCumulative(svCumWeights) != totalN) { + throw new SketchesStateException("Sorted View is misconfigured. TotalN does not match cumWeights."); + } + return new DoublesSketchSortedView(svQuantiles, svCumWeights, totalN, getMaxItem(), getMinItem()); + } + + private final static void populateFromDoublesSketch( + final int k, final long totalN, final long bitPattern, + final DoublesSketchAccessor sketchAccessor, + final double[] svQuantiles, final long[] svCumWeights) { + long weight = 1; + int index = 0; + long bits = bitPattern; + assert bits == (totalN / (2L * k)); // internal consistency check + for (int lvl = 0; bits != 0L; lvl++, bits >>>= 1) { + weight <<= 1; // X2 + if ((bits & 1L) > 0L) { + sketchAccessor.setLevel(lvl); + for (int i = 0; i < sketchAccessor.numItems(); i++) { + svQuantiles[index] = sketchAccessor.get(i); + svCumWeights[index] = weight; + index++; + } + } + } + + weight = 1; //NOT a mistake! We just copied the highest level; now we need to copy the base buffer + final int startOfBaseBufferBlock = index; + + // Copy BaseBuffer over, along with weight = 1 + sketchAccessor.setLevel(BB_LVL_IDX); + for (int i = 0; i < sketchAccessor.numItems(); i++) { + svQuantiles[index] = sketchAccessor.get(i); + svCumWeights[index] = weight; + index++; + } + assert index == svQuantiles.length; + + // Must sort the items that came from the base buffer. + // Don't need to sort the corresponding weights because they are all the same. + final int numSamples = index; + Arrays.sort(svQuantiles, startOfBaseBufferBlock, numSamples); + } + + /** + * blockyTandemMergeSort() is an implementation of top-down merge sort specialized + * for the case where the input contains successive equal-length blocks + * that have already been sorted, so that only the top part of the + * merge tree remains to be executed. Also, two arrays are sorted in tandem, + * as discussed below. + * @param svQuantiles array of quantiles for sorted view + * @param svCumWts array of cumulative weights for sorted view + * @param arrLen length of quantiles array and cumWts array + * @param blkSize size of internal sorted blocks, equal to k + */ + //used by this and UtilTest + static void blockyTandemMergeSort(final double[] svQuantiles, final long[] svCumWts, final int arrLen, + final int blkSize) { + assert blkSize >= 1; + if (arrLen <= blkSize) { return; } + int numblks = arrLen / blkSize; + if ((numblks * blkSize) < arrLen) { numblks += 1; } + assert ((numblks * blkSize) >= arrLen); + + // duplication of the input arrays is preparation for the "ping-pong" copy reduction strategy. + final double[] qSrc = Arrays.copyOf(svQuantiles, arrLen); + final long[] cwSrc = Arrays.copyOf(svCumWts, arrLen); + + blockyTandemMergeSortRecursion(qSrc, cwSrc, + svQuantiles, svCumWts, + 0, numblks, + blkSize, arrLen); + } + + /** + * blockyTandemMergeSortRecursion() is called by blockyTandemMergeSort(). + * In addition to performing the algorithm's top down recursion, + * it manages the buffer swapping that eliminates most copying. + * It also maps the input's pre-sorted blocks into the subarrays + * that are processed by tandemMerge(). + * @param qSrc source array of quantiles + * @param cwSrc source weights array + * @param qDst destination quantiles array + * @param cwDst destination weights array + * @param grpStart group start, refers to pre-sorted blocks such as block 0, block 1, etc. + * @param grpLen group length, refers to pre-sorted blocks such as block 0, block 1, etc. + * @param blkSize block size + * @param arrLim array limit + */ + private static void blockyTandemMergeSortRecursion(final double[] qSrc, final long[] cwSrc, + final double[] qDst, final long[] cwDst, final int grpStart, final int grpLen, + /* indices of blocks */ final int blkSize, final int arrLim) { + // Important note: grpStart and grpLen do NOT refer to positions in the underlying array. + // Instead, they refer to the pre-sorted blocks, such as block 0, block 1, etc. + + assert (grpLen > 0); + if (grpLen == 1) { return; } + final int grpLen1 = grpLen / 2; + final int grpLen2 = grpLen - grpLen1; + assert (grpLen1 >= 1); + assert (grpLen2 >= grpLen1); + + final int grpStart1 = grpStart; + final int grpStart2 = grpStart + grpLen1; + + //swap roles of src and dst + blockyTandemMergeSortRecursion(qDst, cwDst, + qSrc, cwSrc, + grpStart1, grpLen1, blkSize, arrLim); + + //swap roles of src and dst + blockyTandemMergeSortRecursion(qDst, cwDst, + qSrc, cwSrc, + grpStart2, grpLen2, blkSize, arrLim); + + // here we convert indices of blocks into positions in the underlying array. + final int arrStart1 = grpStart1 * blkSize; + final int arrStart2 = grpStart2 * blkSize; + final int arrLen1 = grpLen1 * blkSize; + int arrLen2 = grpLen2 * blkSize; + + // special case for the final block which might be shorter than blkSize. + if ((arrStart2 + arrLen2) > arrLim) { arrLen2 = arrLim - arrStart2; } + + tandemMerge(qSrc, cwSrc, + arrStart1, arrLen1, + arrStart2, arrLen2, + qDst, cwDst, + arrStart1); // which will be arrStart3 + } + + /** + * Performs two merges in tandem. One of them provides the sort keys + * while the other one passively undergoes the same data motion. + * @param qSrc quantiles source + * @param cwSrc cumulative weights source + * @param arrStart1 Array 1 start offset + * @param arrLen1 Array 1 length + * @param arrStart2 Array 2 start offset + * @param arrLen2 Array 2 length + * @param qDst quantiles destination + * @param cwDst cumulative weights destination + * @param arrStart3 Array 3 start offset + */ + private static void tandemMerge(final double[] qSrc, final long[] cwSrc, + final int arrStart1, final int arrLen1, + final int arrStart2, final int arrLen2, + final double[] qDst, final long[] cwDst, + final int arrStart3) { + final int arrStop1 = arrStart1 + arrLen1; + final int arrStop2 = arrStart2 + arrLen2; + + int i1 = arrStart1; + int i2 = arrStart2; + int i3 = arrStart3; + while ((i1 < arrStop1) && (i2 < arrStop2)) { + if (qSrc[i2] < qSrc[i1]) { + qDst[i3] = qSrc[i2]; + cwDst[i3] = cwSrc[i2]; + i2++; + } else { + qDst[i3] = qSrc[i1]; + cwDst[i3] = cwSrc[i1]; + i1++; + } + i3++; + } + + if (i1 < arrStop1) { + arraycopy(qSrc, i1, qDst, i3, arrStop1 - i1); + arraycopy(cwSrc, i1, cwDst, i3, arrStop1 - i1); + } else { + assert i2 < arrStop2; + arraycopy(qSrc, i2, qDst, i3, arrStop2 - i2); + arraycopy(cwSrc, i2, cwDst, i3, arrStop2 - i2); + } + } + + /** + * Convert the individual weights into cumulative weights. + * An array of {1,1,1,1} becomes {1,2,3,4} + * @param array of actual weights from the sketch, none of the weights may be zero + * @return total weight + */ + private static long convertToCumulative(final long[] array) { + long subtotal = 0; + for (int i = 0; i < array.length; i++) { + final long newSubtotal = subtotal + array[i]; + subtotal = array[i] = newSubtotal; + } + return subtotal; + } + } diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java deleted file mode 100644 index bb68061a..00000000 --- a/src/main/java/org/apache/datasketches/quantiles/DoublesSketchSortedView.java +++ /dev/null @@ -1,354 +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.datasketches.quantiles; - -import static java.lang.System.arraycopy; -import static org.apache.datasketches.quantiles.DoublesSketchAccessor.BB_LVL_IDX; -import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE; -import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG; -import static org.apache.datasketches.quantilescommon.QuantilesUtil.getNaturalRank; - -import java.util.Arrays; - -import org.apache.datasketches.common.SketchesArgumentException; -import org.apache.datasketches.common.SketchesStateException; -import org.apache.datasketches.quantilescommon.DoublesSortedView; -import org.apache.datasketches.quantilescommon.DoublesSortedViewIterator; -import org.apache.datasketches.quantilescommon.InequalitySearch; -import org.apache.datasketches.quantilescommon.QuantileSearchCriteria; -import org.apache.datasketches.quantilescommon.QuantilesUtil; - -/** - * The SortedView of the Classic Quantiles DoublesSketch. - * @author Alexander Saydakov - * @author Lee Rhodes - */ -public final class DoublesSketchSortedView implements DoublesSortedView { - private final double[] quantiles; - private final long[] cumWeights; //comes in as individual weights, converted to cumulative natural weights - private final long totalN; - private final double maxItem; - private final double minItem; - - /** - * Construct from elements, also used in testing. - * @param quantiles sorted array of quantiles - * @param cumWeights sorted, monotonically increasing cumulative weights. - * @param totalN the total number of items presented to the sketch. - * @param maxItem of type double - * @param minItem of type double - */ - DoublesSketchSortedView(final double[] quantiles, final long[] cumWeights, final long totalN, - final double maxItem, final double minItem) { - this.quantiles = quantiles; - this.cumWeights = cumWeights; - this.totalN = totalN; - this.maxItem = maxItem; - this.minItem = minItem; - } - - /** - * Constructs this Sorted View given the sketch - * @param sketch the given Classic Quantiles DoublesSketch - */ - public DoublesSketchSortedView(final DoublesSketch sketch) { - if (sketch.isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } - this.totalN = sketch.getN(); - this.maxItem = sketch.getMaxItem(); - this.minItem = sketch.getMinItem(); - final int k = sketch.getK(); - final int numQuantiles = sketch.getNumRetained(); - quantiles = new double[numQuantiles]; - cumWeights = new long[numQuantiles]; - final DoublesSketchAccessor sketchAccessor = DoublesSketchAccessor.wrap(sketch); - - // Populate from DoublesSketch: - // copy over the "levels" and then the base buffer, all with appropriate weights - populateFromDoublesSketch(k, totalN, sketch.getBitPattern(), sketchAccessor, quantiles, cumWeights); - - // Sort the first "numSamples" slots of the two arrays in tandem, - // taking advantage of the already sorted blocks of length k - blockyTandemMergeSort(quantiles, cumWeights, numQuantiles, k); - if (convertToCumulative(cumWeights) != totalN) { - throw new SketchesStateException("Sorted View is misconfigured. TotalN does not match cumWeights."); - } - } - - @Override - public long[] getCumulativeWeights() { - return cumWeights.clone(); - } - - @Override - public double getMaxItem() { - return maxItem; - } - - @Override - public double getMinItem() { - return minItem; - } - - @Override - public long getN() { - return totalN; - } - - @Override - public double getQuantile(final double rank, final QuantileSearchCriteria searchCrit) { - if (isEmpty()) { throw new IllegalArgumentException(EMPTY_MSG); } - QuantilesUtil.checkNormalizedRankBounds(rank); - final int len = cumWeights.length; - final double naturalRank = getNaturalRank(rank, totalN, searchCrit); - final InequalitySearch crit = (searchCrit == INCLUSIVE) ? InequalitySearch.GE : InequalitySearch.GT; - final int index = InequalitySearch.find(cumWeights, 0, len - 1, naturalRank, crit); - if (index == -1) { - return quantiles[len - 1]; //EXCLUSIVE (GT) case: normRank == 1.0; - } - return quantiles[index]; - } - - @Override - public double getRank(final double quantile, final QuantileSearchCriteria searchCrit) { - if (isEmpty()) { throw new IllegalArgumentException(EMPTY_MSG); } - final int len = quantiles.length; - final InequalitySearch crit = (searchCrit == INCLUSIVE) ? InequalitySearch.LE : InequalitySearch.LT; - final int index = InequalitySearch.find(quantiles, 0, len - 1, quantile, crit); - if (index == -1) { - return 0; //EXCLUSIVE (LT) case: quantile <= minQuantile; INCLUSIVE (LE) case: quantile < minQuantile - } - return (double)cumWeights[index] / totalN; - } - - @Override - public double[] getQuantiles() { - return quantiles.clone(); - } - - @Override - public boolean isEmpty() { - return totalN == 0; - } - - @Override - public DoublesSortedViewIterator iterator() { - return new DoublesSortedViewIterator(quantiles, cumWeights); - } - - //restricted methods - - /** - * Populate the arrays and registers from a DoublesSketch - * @param k K parameter of the sketch - * @param n The current size of the stream - * @param bitPattern the bit pattern for valid log levels - * @param sketchAccessor A DoublesSketchAccessor around the sketch - * @param quantilesArr the consolidated array of all items from the sketch - * @param cumWtsArr populates this array with the raw individual weights from the sketch, - * it will be cumulative later. - */ - private final static void populateFromDoublesSketch( - final int k, final long n, final long bitPattern, - final DoublesSketchAccessor sketchAccessor, - final double[] quantilesArr, final long[] cumWtsArr) { - long weight = 1; - int nxt = 0; - long bits = bitPattern; - assert bits == (n / (2L * k)); // internal consistency check - for (int lvl = 0; bits != 0L; lvl++, bits >>>= 1) { - weight *= 2; - if ((bits & 1L) > 0L) { - sketchAccessor.setLevel(lvl); - for (int i = 0; i < sketchAccessor.numItems(); i++) { - quantilesArr[nxt] = sketchAccessor.get(i); - cumWtsArr[nxt] = weight; - nxt++; - } - } - } - - weight = 1; //NOT a mistake! We just copied the highest level; now we need to copy the base buffer - final int startOfBaseBufferBlock = nxt; - - // Copy BaseBuffer over, along with weight = 1 - sketchAccessor.setLevel(BB_LVL_IDX); - for (int i = 0; i < sketchAccessor.numItems(); i++) { - quantilesArr[nxt] = sketchAccessor.get(i); - cumWtsArr[nxt] = weight; - nxt++; - } - assert nxt == quantilesArr.length; - - // Must sort the items that came from the base buffer. - // Don't need to sort the corresponding weights because they are all the same. - final int numSamples = nxt; - Arrays.sort(quantilesArr, startOfBaseBufferBlock, numSamples); - } - - /** - * blockyTandemMergeSort() is an implementation of top-down merge sort specialized - * for the case where the input contains successive equal-length blocks - * that have already been sorted, so that only the top part of the - * merge tree remains to be executed. Also, two arrays are sorted in tandem, - * as discussed below. - * @param quantiles array of quantiles - * @param cumWts array of cum weights - * @param arrLen length of quantiles array and cumWts array - * @param blkSize size of internal sorted blocks - */ - //used by this and UtilTest - static void blockyTandemMergeSort(final double[] quantiles, final long[] cumWts, final int arrLen, - final int blkSize) { - assert blkSize >= 1; - if (arrLen <= blkSize) { return; } - int numblks = arrLen / blkSize; - if ((numblks * blkSize) < arrLen) { numblks += 1; } - assert ((numblks * blkSize) >= arrLen); - - // duplication of the input arrays is preparation for the "ping-pong" copy reduction strategy. - final double[] qSrc = Arrays.copyOf(quantiles, arrLen); - final long[] cwSrc = Arrays.copyOf(cumWts, arrLen); - - blockyTandemMergeSortRecursion(qSrc, cwSrc, - quantiles, cumWts, - 0, numblks, - blkSize, arrLen); - } - - /** - * blockyTandemMergeSortRecursion() is called by blockyTandemMergeSort(). - * In addition to performing the algorithm's top down recursion, - * it manages the buffer swapping that eliminates most copying. - * It also maps the input's pre-sorted blocks into the subarrays - * that are processed by tandemMerge(). - * @param qSrc source array of quantiles - * @param cwSrc source weights array - * @param qDst destination quantiles array - * @param cwDst destination weights array - * @param grpStart group start, refers to pre-sorted blocks such as block 0, block 1, etc. - * @param grpLen group length, refers to pre-sorted blocks such as block 0, block 1, etc. - * @param blkSize block size - * @param arrLim array limit - */ - private static void blockyTandemMergeSortRecursion(final double[] qSrc, final long[] cwSrc, - final double[] qDst, final long[] cwDst, final int grpStart, final int grpLen, - /* indices of blocks */ final int blkSize, final int arrLim) { - // Important note: grpStart and grpLen do NOT refer to positions in the underlying array. - // Instead, they refer to the pre-sorted blocks, such as block 0, block 1, etc. - - assert (grpLen > 0); - if (grpLen == 1) { return; } - final int grpLen1 = grpLen / 2; - final int grpLen2 = grpLen - grpLen1; - assert (grpLen1 >= 1); - assert (grpLen2 >= grpLen1); - - final int grpStart1 = grpStart; - final int grpStart2 = grpStart + grpLen1; - - //swap roles of src and dst - blockyTandemMergeSortRecursion(qDst, cwDst, - qSrc, cwSrc, - grpStart1, grpLen1, blkSize, arrLim); - - //swap roles of src and dst - blockyTandemMergeSortRecursion(qDst, cwDst, - qSrc, cwSrc, - grpStart2, grpLen2, blkSize, arrLim); - - // here we convert indices of blocks into positions in the underlying array. - final int arrStart1 = grpStart1 * blkSize; - final int arrStart2 = grpStart2 * blkSize; - final int arrLen1 = grpLen1 * blkSize; - int arrLen2 = grpLen2 * blkSize; - - // special case for the final block which might be shorter than blkSize. - if ((arrStart2 + arrLen2) > arrLim) { arrLen2 = arrLim - arrStart2; } - - tandemMerge(qSrc, cwSrc, - arrStart1, arrLen1, - arrStart2, arrLen2, - qDst, cwDst, - arrStart1); // which will be arrStart3 - } - - /** - * Performs two merges in tandem. One of them provides the sort keys - * while the other one passively undergoes the same data motion. - * @param qSrc quantiles source - * @param cwSrc cumulative weights source - * @param arrStart1 Array 1 start offset - * @param arrLen1 Array 1 length - * @param arrStart2 Array 2 start offset - * @param arrLen2 Array 2 length - * @param qDst quantiles destination - * @param cwDst cumulative weights destination - * @param arrStart3 Array 3 start offset - */ - private static void tandemMerge(final double[] qSrc, final long[] cwSrc, - final int arrStart1, final int arrLen1, - final int arrStart2, final int arrLen2, - final double[] qDst, final long[] cwDst, - final int arrStart3) { - final int arrStop1 = arrStart1 + arrLen1; - final int arrStop2 = arrStart2 + arrLen2; - - int i1 = arrStart1; - int i2 = arrStart2; - int i3 = arrStart3; - while ((i1 < arrStop1) && (i2 < arrStop2)) { - if (qSrc[i2] < qSrc[i1]) { - qDst[i3] = qSrc[i2]; - cwDst[i3] = cwSrc[i2]; - i2++; - } else { - qDst[i3] = qSrc[i1]; - cwDst[i3] = cwSrc[i1]; - i1++; - } - i3++; - } - - if (i1 < arrStop1) { - arraycopy(qSrc, i1, qDst, i3, arrStop1 - i1); - arraycopy(cwSrc, i1, cwDst, i3, arrStop1 - i1); - } else { - assert i2 < arrStop2; - arraycopy(qSrc, i2, qDst, i3, arrStop2 - i2); - arraycopy(cwSrc, i2, cwDst, i3, arrStop2 - i2); - } - } - - /** - * Convert the individual weights into cumulative weights. - * An array of {1,1,1,1} becomes {1,2,3,4} - * @param array of actual weights from the sketch, none of the weights may be zero - * @return total weight - */ - private static long convertToCumulative(final long[] array) { - long subtotal = 0; - for (int i = 0; i < array.length; i++) { - final long newSubtotal = subtotal + array[i]; - subtotal = array[i] = newSubtotal; - } - return subtotal; - } - -} diff --git a/src/main/java/org/apache/datasketches/quantiles/DoublesUnionImpl.java b/src/main/java/org/apache/datasketches/quantiles/DoublesUnionImpl.java index b55f0b53..38854d3f 100644 --- a/src/main/java/org/apache/datasketches/quantiles/DoublesUnionImpl.java +++ b/src/main/java/org/apache/datasketches/quantiles/DoublesUnionImpl.java @@ -123,14 +123,14 @@ final class DoublesUnionImpl extends DoublesUnionImplR { public void union(final DoublesSketch sketchIn) { Objects.requireNonNull(sketchIn); gadget_ = updateLogic(maxK_, gadget_, sketchIn); - gadget_.classicQdsSV = null; + gadget_.doublesSV = null; } @Override public void union(final Memory mem) { Objects.requireNonNull(mem); gadget_ = updateLogic(maxK_, gadget_, DoublesSketch.wrap(mem)); - gadget_.classicQdsSV = null; + gadget_.doublesSV = null; } @Override @@ -139,7 +139,7 @@ final class DoublesUnionImpl extends DoublesUnionImplR { gadget_ = HeapUpdateDoublesSketch.newInstance(maxK_); } gadget_.update(quantile); - gadget_.classicQdsSV = null; + gadget_.doublesSV = null; } @Override diff --git a/src/main/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketch.java b/src/main/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketch.java index 8282f00c..2197d8b8 100644 --- a/src/main/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketch.java +++ b/src/main/java/org/apache/datasketches/quantiles/HeapUpdateDoublesSketch.java @@ -270,7 +270,7 @@ final class HeapUpdateDoublesSketch extends UpdateDoublesSketch { baseBufferCount_ = newBBCount; } n_ = newN; - classicQdsSV = null; + doublesSV = null; } /** diff --git a/src/main/java/org/apache/datasketches/quantiles/ItemsSketch.java b/src/main/java/org/apache/datasketches/quantiles/ItemsSketch.java index 54795d7a..13aee81e 100644 --- a/src/main/java/org/apache/datasketches/quantiles/ItemsSketch.java +++ b/src/main/java/org/apache/datasketches/quantiles/ItemsSketch.java @@ -530,12 +530,6 @@ public final class ItemsSketch<T> implements QuantilesGenericAPI<T> { dstMem.putByteArray(0, byteArr, 0, byteArr.length); } - @Override - public ItemsSketchSortedView<T> getSortedView() { - if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } - return refreshSortedView(); - } - @Override public void update(final T item) { // this method only uses the base buffer part of the combined buffer @@ -631,69 +625,84 @@ public final class ItemsSketch<T> implements QuantilesGenericAPI<T> { sketch.combinedBuffer_ = Arrays.copyOf(baseBuffer, newSize); } + //************SORTED VIEW**************************** + + @Override + public ItemsSketchSortedView<T> getSortedView() { + return refreshSortedView(); + } + private final ItemsSketchSortedView<T> refreshSortedView() { - if (classicQisSV == null) { - final CreateSortedView csv = new CreateSortedView(); - classicQisSV = csv.getSV(); - } - return classicQisSV; - } - - @SuppressWarnings({"rawtypes","unchecked"}) - private final class CreateSortedView { - final long n = getN(); - final int numQuantiles = getNumRetained(); - final T[] quantiles = (T[]) Array.newInstance(clazz, numQuantiles); - long[] cumWeights = new long[numQuantiles]; - final int k = getK(); - - final T[] combinedBuffer = (T[]) getCombinedBuffer(); - final int baseBufferCount = getBaseBufferCount(); - final Comparator<? super T> comparator = ItemsSketch.this.comparator_; - - ItemsSketchSortedView<T> getSV() { - long weight = 1; - int index = 0; - long bits = getBitPattern(); - assert bits == (n / (2L * k)); // internal consistency check - for (int lvl = 0; bits != 0L; lvl++, bits >>>= 1) { - weight *= 2; - if ((bits & 1L) > 0L) { - final int offset = (2 + lvl) * k; - for (int i = 0; i < k; i++) { - quantiles[index] = combinedBuffer[i + offset]; - cumWeights[index] = weight; - index++; - } - } - } + return (classicQisSV == null) ? (classicQisSV = getSV(this)) : classicQisSV; + } - weight = 1; //NOT a mistake! We just copied the highest level; now we need to copy the base buffer - final int startOfBaseBufferBlock = index; + @SuppressWarnings({"unchecked"}) + private static <T> ItemsSketchSortedView<T> getSV(final ItemsSketch<T> sk) { + final long totalN = sk.getN(); + if (sk.isEmpty() || (totalN == 0)) { throw new SketchesArgumentException(EMPTY_MSG); } + final int k = sk.getK(); + final int numQuantiles = sk.getNumRetained(); + final T[] svQuantiles = (T[]) Array.newInstance(sk.clazz, numQuantiles); + final long[] svCumWeights = new long[numQuantiles]; + final Comparator<? super T> comparator = sk.comparator_; - // Copy BaseBuffer over, along with weight = 1 - for (int i = 0; i < baseBufferCount; i++) { - quantiles[index] = combinedBuffer[i]; - cumWeights[index] = weight; - index++; - } - assert index == numQuantiles; + final T[] combinedBuffer = (T[]) sk.getCombinedBuffer(); + final int baseBufferCount = sk.getBaseBufferCount(); + + // Populate from ItemsSketch: + // copy over the "levels" and then the base buffer, all with appropriate weights + populateFromItemsSketch(k, totalN, sk.getBitPattern(), combinedBuffer, baseBufferCount, + numQuantiles, svQuantiles, svCumWeights, sk.getComparator()); + + // Sort the first "numSamples" slots of the two arrays in tandem, + // taking advantage of the already sorted blocks of length k + ItemsMergeImpl.blockyTandemMergeSort(svQuantiles, svCumWeights, numQuantiles, k, comparator); + + if (convertToCumulative(svCumWeights) != totalN) { + throw new SketchesStateException("Sorted View is misconfigured. TotalN does not match cumWeights."); + } + + final double normRankErr = getNormalizedRankError(sk.getK(), true); + return new ItemsSketchSortedView<>( + svQuantiles, svCumWeights, sk.getN(), comparator, sk.getMaxItem(), sk.getMinItem(), normRankErr); - // Must sort the items that came from the base buffer. - // Don't need to sort the corresponding weights because they are all the same. - Arrays.sort(quantiles, startOfBaseBufferBlock, numQuantiles, comparator); + } - // Sort the first "numSamples" slots of the two arrays in tandem, - // taking advantage of the already sorted blocks of length k - ItemsMergeImpl.blockyTandemMergeSort(quantiles, cumWeights, numQuantiles, k, comparator); + private final static <T> void populateFromItemsSketch( + final int k, final long totalN, final long bitPattern, final T[] combinedBuffer, + final int baseBufferCount, final int numQuantiles, final T[] svQuantiles, final long[] svCumWeights, + final Comparator<? super T> comparator) { - if (convertToCumulative(cumWeights) != n) { - throw new SketchesStateException("Sorted View is misconfigured. TotalN does not match cumWeights."); + long weight = 1; + int index = 0; + long bits = bitPattern; + assert bits == (totalN / (2L * k)); // internal consistency check + for (int lvl = 0; bits != 0L; lvl++, bits >>>= 1) { + weight <<= 1; // X2 + if ((bits & 1L) > 0L) { + final int offset = (2 + lvl) * k; + for (int i = 0; i < k; i++) { + svQuantiles[index] = combinedBuffer[i + offset]; + svCumWeights[index] = weight; + index++; + } } - final double normRankErr = getNormalizedRankError(getK(), true); - return new ItemsSketchSortedView( - quantiles, cumWeights, getN(), comparator, getMaxItem(), getMinItem(), normRankErr); } + + weight = 1; //NOT a mistake! We just copied the highest level; now we need to copy the base buffer + final int startOfBaseBufferBlock = index; + + // Copy BaseBuffer over, along with weight = 1 + for (int i = 0; i < baseBufferCount; i++) { + svQuantiles[index] = combinedBuffer[i]; + svCumWeights[index] = weight; + index++; + } + assert index == numQuantiles; + + // Must sort the items that came from the base buffer. + // Don't need to sort the corresponding weights because they are all the same. + Arrays.sort(svQuantiles, startOfBaseBufferBlock, numQuantiles, comparator); } /** diff --git a/src/main/java/org/apache/datasketches/quantiles/KolmogorovSmirnov.java b/src/main/java/org/apache/datasketches/quantiles/KolmogorovSmirnov.java index c290b059..6b8079ea 100644 --- a/src/main/java/org/apache/datasketches/quantiles/KolmogorovSmirnov.java +++ b/src/main/java/org/apache/datasketches/quantiles/KolmogorovSmirnov.java @@ -19,6 +19,8 @@ package org.apache.datasketches.quantiles; +import org.apache.datasketches.quantilescommon.DoublesSketchSortedView; + /** * Kolmogorov-Smirnov Test * See <a href="https://en.wikipedia.org/wiki/Kolmogorov-Smirnov_test";>Kolmogorov–Smirnov Test</a> @@ -36,8 +38,8 @@ final class KolmogorovSmirnov { * @return the raw delta area between two quantile sketches */ public static double computeKSDelta(final DoublesSketch sketch1, final DoublesSketch sketch2) { - final DoublesSketchSortedView p = new DoublesSketchSortedView(sketch1); - final DoublesSketchSortedView q = new DoublesSketchSortedView(sketch2); + final DoublesSketchSortedView p = sketch1.getSortedView(); + final DoublesSketchSortedView q = sketch2.getSortedView(); final double[] pSamplesArr = p.getQuantiles(); final double[] qSamplesArr = q.getQuantiles(); diff --git a/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java b/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java new file mode 100644 index 00000000..b0332369 --- /dev/null +++ b/src/main/java/org/apache/datasketches/quantilescommon/DoublesSketchSortedView.java @@ -0,0 +1,118 @@ +/* + * 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.datasketches.quantilescommon; + +import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE; +import static org.apache.datasketches.quantilescommon.QuantilesAPI.EMPTY_MSG; +import static org.apache.datasketches.quantilescommon.QuantilesUtil.getNaturalRank; + +import org.apache.datasketches.common.SketchesArgumentException; + +/** + * The SortedView of the Quantiles Classic DoublesSketch and the KllDoublesSketch. + * @author Alexander Saydakov + * @author Lee Rhodes + */ +public final class DoublesSketchSortedView implements DoublesSortedView { + private final double[] quantiles; + private final long[] cumWeights; //comes in as individual weights, converted to cumulative natural weights + private final long totalN; + private final double maxItem; + private final double minItem; + + /** + * Construct from elements, also used in testing. + * @param quantiles sorted array of quantiles + * @param cumWeights sorted, monotonically increasing cumulative weights. + * @param totalN the total number of items presented to the sketch. + * @param maxItem of type double + * @param minItem of type double + */ + public DoublesSketchSortedView(final double[] quantiles, final long[] cumWeights, final long totalN, + final double maxItem, final double minItem) { + this.quantiles = quantiles; + this.cumWeights = cumWeights; + this.totalN = totalN; + this.maxItem = maxItem; + this.minItem = minItem; + } + + @Override + public long[] getCumulativeWeights() { + return cumWeights.clone(); + } + + @Override + public double getMaxItem() { + return maxItem; + } + + @Override + public double getMinItem() { + return minItem; + } + + @Override + public long getN() { + return totalN; + } + + @Override + public double getQuantile(final double rank, final QuantileSearchCriteria searchCrit) { + if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } + QuantilesUtil.checkNormalizedRankBounds(rank); + final int len = cumWeights.length; + final double naturalRank = getNaturalRank(rank, totalN, searchCrit); + final InequalitySearch crit = (searchCrit == INCLUSIVE) ? InequalitySearch.GE : InequalitySearch.GT; + final int index = InequalitySearch.find(cumWeights, 0, len - 1, naturalRank, crit); + if (index == -1) { + return quantiles[len - 1]; //EXCLUSIVE (GT) case: normRank == 1.0; + } + return quantiles[index]; + } + + @Override + public double[] getQuantiles() { + return quantiles.clone(); + } + + @Override + public double getRank(final double quantile, final QuantileSearchCriteria searchCrit) { + if (isEmpty()) { throw new SketchesArgumentException(EMPTY_MSG); } + final int len = quantiles.length; + final InequalitySearch crit = (searchCrit == INCLUSIVE) ? InequalitySearch.LE : InequalitySearch.LT; + final int index = InequalitySearch.find(quantiles, 0, len - 1, quantile, crit); + if (index == -1) { + return 0; //EXCLUSIVE (LT) case: quantile <= minQuantile; INCLUSIVE (LE) case: quantile < minQuantile + } + return (double)cumWeights[index] / totalN; + } + + @Override + public boolean isEmpty() { + return totalN == 0; + } + + @Override + public DoublesSortedViewIterator iterator() { + return new DoublesSortedViewIterator(quantiles, cumWeights); + } + +} diff --git a/src/test/java/org/apache/datasketches/quantiles/CustomQuantilesTest.java b/src/test/java/org/apache/datasketches/quantiles/CustomQuantilesTest.java index d3193883..101c26cd 100644 --- a/src/test/java/org/apache/datasketches/quantiles/CustomQuantilesTest.java +++ b/src/test/java/org/apache/datasketches/quantiles/CustomQuantilesTest.java @@ -26,6 +26,7 @@ import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INC import static org.apache.datasketches.quantilescommon.QuantilesUtil.getNaturalRank; import static org.testng.Assert.assertEquals; +import org.apache.datasketches.quantilescommon.DoublesSketchSortedView; import org.testng.annotations.Test; public class CustomQuantilesTest { @@ -55,7 +56,7 @@ public class CustomQuantilesTest { } } long N = sk.getN(); - DoublesSketchSortedView sv = new DoublesSketchSortedView(sk); + DoublesSketchSortedView sv = sk.getSortedView(); double[] quantilesArr = sv.getQuantiles(); long[] cumWtsArr = sv.getCumulativeWeights(); int lenQ = quantilesArr.length; diff --git a/src/test/java/org/apache/datasketches/quantiles/UtilTest.java b/src/test/java/org/apache/datasketches/quantiles/UtilTest.java index 0ca3ea42..49546df5 100644 --- a/src/test/java/org/apache/datasketches/quantiles/UtilTest.java +++ b/src/test/java/org/apache/datasketches/quantiles/UtilTest.java @@ -165,7 +165,6 @@ public class UtilTest { } /** - * * @param numTries number of tries * @param maxArrLen maximum length of array size */ @@ -178,7 +177,7 @@ public class UtilTest { arr = makeMergeTestInput(arrLen, blkSize); long [] brr = makeTheTandemArray(arr); assertMergeTestPrecondition(arr, brr, arrLen, blkSize); - DoublesSketchSortedView.blockyTandemMergeSort(arr, brr, arrLen, blkSize); + DoublesSketch.blockyTandemMergeSort(arr, brr, arrLen, blkSize); /* verify sorted order */ for (int i = 0; i < (arrLen-1); i++) { assert arr[i] <= arr[i+1]; diff --git a/src/test/java/org/apache/datasketches/quantilescommon/CrossCheckQuantilesTest.java b/src/test/java/org/apache/datasketches/quantilescommon/CrossCheckQuantilesTest.java index dbbbb656..6049f2f3 100644 --- a/src/test/java/org/apache/datasketches/quantilescommon/CrossCheckQuantilesTest.java +++ b/src/test/java/org/apache/datasketches/quantilescommon/CrossCheckQuantilesTest.java @@ -29,8 +29,7 @@ import static org.apache.datasketches.quantilescommon.LinearRanksAndQuantiles.ge import static org.apache.datasketches.quantilescommon.LinearRanksAndQuantiles.getTrueItemRank; import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.EXCLUSIVE; import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE; -import static org.apache.datasketches.quantilescommon.ReflectUtilityTest.CLASSIC_DOUBLES_SV_CTOR; -import static org.apache.datasketches.quantilescommon.ReflectUtilityTest.KLL_DOUBLES_SV_CTOR; +import static org.apache.datasketches.quantilescommon.ReflectUtilityTest.DOUBLES_SV_CTOR; import static org.apache.datasketches.quantilescommon.ReflectUtilityTest.KLL_FLOATS_SV_CTOR; import static org.apache.datasketches.quantilescommon.ReflectUtilityTest.REQ_SV_CTOR; import static org.testng.Assert.assertEquals; @@ -40,13 +39,11 @@ import java.util.Comparator; import org.apache.datasketches.common.ArrayOfStringsSerDe; import org.apache.datasketches.common.SketchesArgumentException; import org.apache.datasketches.kll.KllDoublesSketch; -import org.apache.datasketches.kll.KllDoublesSketchSortedView; import org.apache.datasketches.kll.KllFloatsSketch; import org.apache.datasketches.kll.KllFloatsSketchSortedView; import org.apache.datasketches.kll.KllItemsSketch; import org.apache.datasketches.kll.KllSketch; import org.apache.datasketches.quantiles.DoublesSketch; -import org.apache.datasketches.quantiles.DoublesSketchSortedView; import org.apache.datasketches.quantiles.ItemsSketch; import org.apache.datasketches.quantiles.UpdateDoublesSketch; import org.apache.datasketches.req.ReqSketch; @@ -146,10 +143,10 @@ public class CrossCheckQuantilesTest { ReqSketchSortedView reqFloatsSV = null; KllFloatsSketchSortedView kllFloatsSV = null; - KllDoublesSketchSortedView kllDoublesSV = null; + DoublesSketchSortedView kllDoublesSV = null; DoublesSketchSortedView classicDoublesSV = null; ItemsSketchSortedView<String> kllItemsSV = null; - ItemsSketchSortedView<String> itemsSV = null; + ItemsSketchSortedView<String> classicItemsSV = null; public CrossCheckQuantilesTest() {} @@ -221,7 +218,7 @@ public class CrossCheckQuantilesTest { testRank = kllItemsSk.getRank(s, crit); assertEquals(testRank, trueRank); - testRank = itemsSV.getRank(s, crit); + testRank = classicItemsSV.getRank(s, crit); assertEquals(testRank, trueRank); testRank = itemsSk.getRank(s, crit); assertEquals(testRank, trueRank); @@ -286,7 +283,7 @@ public class CrossCheckQuantilesTest { testIQ = kllItemsSk.getQuantile(normRank, crit); assertEquals(testIQ, trueIQ); - testIQ = itemsSV.getQuantile(normRank, crit); + testIQ = classicItemsSV.getQuantile(normRank, crit); assertEquals(testIQ, trueIQ); testIQ = itemsSk.getQuantile(normRank, crit); assertEquals(testIQ, trueIQ); @@ -339,9 +336,9 @@ public class CrossCheckQuantilesTest { svMaxFValues[set], svMinFValues[set]); kllFloatsSV = getRawKllFloatsSV(svFValues[set], svCumWeights[set], totalN[set], svMaxFValues[set], svMinFValues[set]); - kllDoublesSV = getRawKllDoublesSV(svDValues[set], svCumWeights[set], totalN[set], + kllDoublesSV = getRawDoublesSV(svDValues[set], svCumWeights[set], totalN[set], svMaxDValues[set], svMinDValues[set]); - classicDoublesSV = getRawClassicDoublesSV(svDValues[set], svCumWeights[set], totalN[set], + classicDoublesSV = getRawDoublesSV(svDValues[set], svCumWeights[set], totalN[set], svMaxDValues[set], svMinDValues[set]); String svImax = svIValues[set][svIValues[set].length - 1]; String svImin = svIValues[set][0]; @@ -349,7 +346,7 @@ public class CrossCheckQuantilesTest { kllItemsSV = new ItemsSketchSortedView<>(svIValues[set], svCumWeights[set], totalN[set], comparator, svImax, svImin, normRankErr); normRankErr = ItemsSketch.getNormalizedRankError(k, true); - itemsSV = new ItemsSketchSortedView<>(svIValues[set], svCumWeights[set], totalN[set], + classicItemsSV = new ItemsSketchSortedView<>(svIValues[set], svCumWeights[set], totalN[set], comparator, svImax, svImin, normRankErr); } @@ -365,16 +362,10 @@ public class CrossCheckQuantilesTest { return (KllFloatsSketchSortedView) KLL_FLOATS_SV_CTOR.newInstance(values, cumWeights, totalN, maxItem, minItem); } - private final static KllDoublesSketchSortedView getRawKllDoublesSV( + private final static DoublesSketchSortedView getRawDoublesSV( final double[] values, final long[] cumWeights, final long totalN, final double maxItem, final double minItem) throws Exception { - return (KllDoublesSketchSortedView) KLL_DOUBLES_SV_CTOR.newInstance(values, cumWeights, totalN, maxItem, minItem); - } - - private final static DoublesSketchSortedView getRawClassicDoublesSV( - final double[] values, final long[] cumWeights, final long totalN, final double maxItem, final double minItem) - throws Exception { - return (DoublesSketchSortedView) CLASSIC_DOUBLES_SV_CTOR.newInstance(values, cumWeights, totalN, maxItem, minItem); + return (DoublesSketchSortedView) DOUBLES_SV_CTOR.newInstance(values, cumWeights, totalN, maxItem, minItem); } /********BUILD DATA SETS**********/ diff --git a/src/test/java/org/apache/datasketches/quantilescommon/ReflectUtilityTest.java b/src/test/java/org/apache/datasketches/quantilescommon/ReflectUtilityTest.java index 191629fb..6dbcac2d 100644 --- a/src/test/java/org/apache/datasketches/quantilescommon/ReflectUtilityTest.java +++ b/src/test/java/org/apache/datasketches/quantilescommon/ReflectUtilityTest.java @@ -36,28 +36,23 @@ public final class ReflectUtilityTest { static final Class<?> REQ_SV; static final Class<?> KLL_FLOATS_SV; - static final Class<?> KLL_DOUBLES_SV; - static final Class<?> CLASSIC_DOUBLES_SV; + static final Class<?> DOUBLES_SV; static final Constructor<?> REQ_SV_CTOR; static final Constructor<?> KLL_FLOATS_SV_CTOR; - static final Constructor<?> KLL_DOUBLES_SV_CTOR; - static final Constructor<?> CLASSIC_DOUBLES_SV_CTOR; + static final Constructor<?> DOUBLES_SV_CTOR; static { REQ_SV = getClass("org.apache.datasketches.req.ReqSketchSortedView"); KLL_FLOATS_SV = getClass("org.apache.datasketches.kll.KllFloatsSketchSortedView"); - KLL_DOUBLES_SV = getClass("org.apache.datasketches.kll.KllDoublesSketchSortedView"); - CLASSIC_DOUBLES_SV = getClass("org.apache.datasketches.quantiles.DoublesSketchSortedView"); + DOUBLES_SV = getClass("org.apache.datasketches.quantilescommon.DoublesSketchSortedView"); REQ_SV_CTOR = getConstructor(REQ_SV, float[].class, long[].class, long.class, float.class, float.class); KLL_FLOATS_SV_CTOR = getConstructor(KLL_FLOATS_SV, float[].class, long[].class, long.class, float.class, float.class); - KLL_DOUBLES_SV_CTOR = - getConstructor(KLL_DOUBLES_SV, double[].class, long[].class, long.class, double.class, double.class); - CLASSIC_DOUBLES_SV_CTOR = - getConstructor(CLASSIC_DOUBLES_SV, double[].class, long[].class, long.class, double.class, double.class); + DOUBLES_SV_CTOR = + getConstructor(DOUBLES_SV, double[].class, long[].class, long.class, double.class, double.class); } @Test //Example --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
