This is an automated email from the ASF dual-hosted git repository. jmalkin pushed a commit to branch 5.0.X-patch in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 806bd4b1655478af192f1c15be858f9715f09ca9 Author: jmalkin <[email protected]> AuthorDate: Wed Mar 13 23:16:11 2024 -0700 prep for 5.0.2, fix KllItemsSketch level 0 soring issue --- pom.xml | 4 +-- .../apache/datasketches/kll/KllItemsHelper.java | 3 +-- .../datasketches/kll/KllItemsSketchTest.java | 31 ++++++++++++++++++++++ 3 files changed, 34 insertions(+), 4 deletions(-) diff --git a/pom.xml b/pom.xml index d5ae0037..20f6fd8a 100644 --- a/pom.xml +++ b/pom.xml @@ -33,7 +33,7 @@ under the License. <groupId>org.apache.datasketches</groupId> <artifactId>datasketches-java</artifactId> - <version>5.0.1</version> + <version>5.0.2</version> <packaging>jar</packaging> <name>${project.artifactId}</name> @@ -734,7 +734,7 @@ under the License. </pluginManagement> </build> </profile> - + <profile> <id>check-cpp-historical-files</id> <build> diff --git a/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java b/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java index 502d4327..27fdb303 100644 --- a/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java +++ b/src/main/java/org/apache/datasketches/kll/KllItemsHelper.java @@ -409,7 +409,7 @@ final class KllItemsHelper<T> { // level zero might not be sorted, so we must sort it if we wish to compact it if ((curLevel == 0) && !isLevelZeroSorted) { - Arrays.sort(inBuf, adjBeg, adjBeg + adjPop); + Arrays.sort((T[])inBuf, adjBeg, adjBeg + adjPop, comp); } if (popAbove == 0) { // Level above is empty, so halve up @@ -486,4 +486,3 @@ final class KllItemsHelper<T> { // } } - diff --git a/src/test/java/org/apache/datasketches/kll/KllItemsSketchTest.java b/src/test/java/org/apache/datasketches/kll/KllItemsSketchTest.java index deb3cb9c..7957ce01 100644 --- a/src/test/java/org/apache/datasketches/kll/KllItemsSketchTest.java +++ b/src/test/java/org/apache/datasketches/kll/KllItemsSketchTest.java @@ -22,6 +22,7 @@ package org.apache.datasketches.kll; import static java.lang.Math.ceil; import static org.apache.datasketches.kll.KllSketch.SketchStructure.*; import static org.apache.datasketches.kll.KllSketch.SketchType.*; +import static org.apache.datasketches.quantilescommon.LongsAsOrderableStrings.getString; import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.EXCLUSIVE; import static org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INCLUSIVE; import static org.testng.Assert.assertEquals; @@ -31,6 +32,7 @@ import static org.testng.Assert.assertTrue; import static org.testng.Assert.fail; import java.util.Comparator; +import java.util.Random; import org.apache.datasketches.common.ArrayOfStringsSerDe; import org.apache.datasketches.common.SketchesArgumentException; @@ -42,6 +44,7 @@ import org.apache.datasketches.memory.WritableMemory; import org.apache.datasketches.quantilescommon.DoublesSortedView; import org.apache.datasketches.quantilescommon.GenericSortedView; import org.apache.datasketches.quantilescommon.GenericSortedViewIterator; +import org.apache.datasketches.quantilescommon.QuantilesGenericSketchIterator; import org.testng.annotations.Test; @SuppressWarnings("unused") @@ -751,6 +754,34 @@ public class KllItemsSketchTest { try { sk.getSortedView(); fail(); } catch (SketchesArgumentException e) { } } + @Test + //There is no guarantee that L0 is sorted after a merge. + //The issue is, during a merge, L0 must be sorted prior to a compaction to a higher level. + //Otherwise the higher levels would not be sorted properly. + public void checkL0SortDuringMerge() throws NumberFormatException { + final Random rand = new Random(); + final KllItemsSketch<String> sk1 = KllItemsSketch.newHeapInstance(8, Comparator.reverseOrder(), serDe); + final KllItemsSketch<String> sk2 = KllItemsSketch.newHeapInstance(8, Comparator.reverseOrder(), serDe); + final int n = 26; //don't change this + for (int i = 1; i <= n; i++ ) { + final int j = rand.nextInt(n) + 1; + sk1.update(getString(j, 3)); + sk2.update(getString(j +100, 3)); + } + sk1.merge(sk2); + println(sk1.toString(true, true)); //L1 and above should be sorted in reverse. Ignore L0. + final int lvl1size = sk1.levelsArr[2] - sk1.levelsArr[1]; + final QuantilesGenericSketchIterator<String> itr = sk1.iterator(); + itr.next(); + int prev = Integer.parseInt(itr.getQuantile().trim()); + for (int i = 1; i < lvl1size; i++) { + if (itr.next()) { + int v = Integer.parseInt(itr.getQuantile().trim()); + assertTrue(v <= prev); + prev = v; + } + } + } private final static boolean enablePrinting = false; --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
