This is an automated email from the ASF dual-hosted git repository. leerho pushed a commit to branch count-min-v2 in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
commit 93908aed8ba3a1171b2ac8b211377a00e7e37b26 Author: Lee Rhodes <[email protected]> AuthorDate: Tue Nov 10 16:56:36 2026 -0800 Count-Min: public constructors and version 2 cross-language files - CountMinSketch had no public way to create a sketch; only deserialize was public. Add public constructors (numHashes, numBuckets) with the default seed 9001, and (numHashes, numBuckets, seed). - Add CountMinSketchCrossLanguageTest, which generates and checks the version 2 CL files defined in section 8 of the TCK spec: count_min_v2_<case>_<language>.sk, for cases n0, n1, n10, n100, n1000, n10000 and seed42_n1000. Files from another language must also be byte-identical to Java's. The C++ version 1 files are checked to load as version 1 sketches. Co-Authored-By: Claude Opus 5.5 <[email protected]> --- .../apache/datasketches/count/CountMinSketch.java | 33 +++++- .../count/CountMinSketchCrossLanguageTest.java | 131 +++++++++++++++++++++ .../datasketches/count/CountMinSketchTest.java | 16 +++ 3 files changed, 175 insertions(+), 5 deletions(-) diff --git a/src/main/java/org/apache/datasketches/count/CountMinSketch.java b/src/main/java/org/apache/datasketches/count/CountMinSketch.java index f5840673e..c576b0b89 100644 --- a/src/main/java/org/apache/datasketches/count/CountMinSketch.java +++ b/src/main/java/org/apache/datasketches/count/CountMinSketch.java @@ -77,14 +77,37 @@ public class CountMinSketch { } /** - * Creates a CountMin sketch with given number of hash functions and buckets, - * and a user-specified seed. The sketch uses serialization version 2. + * Creates an empty CountMin sketch with the given number of hash functions and buckets, + * and the default seed, {@link Util#DEFAULT_UPDATE_SEED}. + * The sketch uses serialization version 2. * - * @param numHashes The number of hash functions to apply to items - * @param numBuckets Array size for each of the hashing function + * <p>{@link #suggestNumHashes(double)} and {@link #suggestNumBuckets(double)} give suitable values + * for a desired confidence and relative error.</p> + * + * @param numHashes The number of hash functions (rows), from 1 to 127 + * @param numBuckets The number of buckets per hash function, at least 3. + * The product of numHashes and numBuckets must be less than 2<sup>30</sup>. + * @throws SketchesArgumentException if a parameter is out of range + */ + public CountMinSketch(final byte numHashes, final int numBuckets) { + this(numHashes, numBuckets, Util.DEFAULT_UPDATE_SEED); + } + + /** + * Creates an empty CountMin sketch with the given number of hash functions and buckets, + * and the given seed. The sketch uses serialization version 2. + * + * <p>{@link #suggestNumHashes(double)} and {@link #suggestNumBuckets(double)} give suitable values + * for a desired confidence and relative error. Sketches can be merged only if they use the same + * seed, and an image must be read back with the seed it was created with.</p> + * + * @param numHashes The number of hash functions (rows), from 1 to 127 + * @param numBuckets The number of buckets per hash function, at least 3. + * The product of numHashes and numBuckets must be less than 2<sup>30</sup>. * @param seed The base hash seed + * @throws SketchesArgumentException if a parameter is out of range */ - CountMinSketch(final byte numHashes, final int numBuckets, final long seed) { + public CountMinSketch(final byte numHashes, final int numBuckets, final long seed) { this(numHashes, numBuckets, seed, SERIAL_VERSION_2); } diff --git a/src/test/java/org/apache/datasketches/count/CountMinSketchCrossLanguageTest.java b/src/test/java/org/apache/datasketches/count/CountMinSketchCrossLanguageTest.java new file mode 100644 index 000000000..432e1d327 --- /dev/null +++ b/src/test/java/org/apache/datasketches/count/CountMinSketchCrossLanguageTest.java @@ -0,0 +1,131 @@ +/* + * 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.count; + +import static org.apache.datasketches.common.UtilityIO.CHECK_CPP_FILES; +import static org.apache.datasketches.common.UtilityIO.CHECK_GO_FILES; +import static org.apache.datasketches.common.UtilityIO.CHECK_JAVA_FILES; +import static org.apache.datasketches.common.UtilityIO.CHECK_RUST_FILES; +import static org.apache.datasketches.common.UtilityIO.GENERATE_JAVA_FILES; +import static org.apache.datasketches.common.UtilityIO.getFileBytes; +import static org.apache.datasketches.common.UtilityIO.putBytesToJavaPath; +import static org.testng.Assert.assertEquals; +import static org.testng.Assert.assertTrue; + +import org.apache.datasketches.common.UtilityIO.GroupLanguage; +import org.testng.annotations.Test; + +/** + * Generates and checks the Count-Min version 2 cross-language files defined in section 8 of the + * TCK spec docs/count-min-format.md. + */ +public class CountMinSketchCrossLanguageTest { + private static final byte NUM_HASHES = 3; + private static final int NUM_BUCKETS = 1000; + + private static final String[] CASES = { "n0", "n1", "n10", "n100", "n1000", "n10000", "seed42_n1000" }; + + private static long seedOf(final String testCase) { + return testCase.startsWith("seed42_") ? 42L : 9001L; + } + + private static int nOf(final String testCase) { + return Integer.parseInt(testCase.substring(testCase.lastIndexOf('n') + 1)); + } + + private static String fileName(final String testCase, final GroupLanguage lang) { + return "count_min_v2_" + testCase + lang.sfx + ".sk"; + } + + static CountMinSketch build(final String testCase) { + final int n = nOf(testCase); + final CountMinSketch cms = new CountMinSketch(NUM_HASHES, NUM_BUCKETS, seedOf(testCase)); + for (int i = 0; i < n; i++) { + cms.update(i, i + 1L); + cms.update(Integer.toString(i), 1); + } + return cms; + } + + @Test(groups = {GENERATE_JAVA_FILES}, priority = 0) + public void generateCountMinBinaries() { + for (final String testCase : CASES) { + putBytesToJavaPath(fileName(testCase, GroupLanguage.JAVA), build(testCase).toByteArray()); + } + } + + @Test(groups = {CHECK_JAVA_FILES}, priority = 1) + public void checkJava() { + checkCountMinBinaries(GroupLanguage.JAVA); + } + + @Test(groups = {CHECK_CPP_FILES}) + public void checkCpp() { + checkCountMinBinaries(GroupLanguage.CPP); + checkCppVersion1Binaries(); + } + + @Test(groups = {CHECK_GO_FILES}) + public void checkGo() { + checkCountMinBinaries(GroupLanguage.GO); + } + + @Test(groups = {CHECK_RUST_FILES}) + public void checkRust() { + checkCountMinBinaries(GroupLanguage.RUST); + } + + private static void checkCountMinBinaries(final GroupLanguage lang) { + for (final String testCase : CASES) { + final byte[] bytes = getFileBytes(lang.pth, fileName(testCase, lang)); + if (bytes.length == 0) { continue; } + final long seed = seedOf(testCase); + final int n = nOf(testCase); + final CountMinSketch cms = CountMinSketch.deserialize(bytes, seed); + + assertEquals(cms.getSerialVersion(), CountMinSketch.SERIAL_VERSION_2, testCase); + assertEquals(cms.getNumHashes_(), NUM_HASHES, testCase); + assertEquals(cms.getNumBuckets_(), NUM_BUCKETS, testCase); + assertEquals(cms.isEmpty(), n == 0, testCase); + assertEquals(cms.getTotalWeight_(), ((long) n * (n + 1)) / 2 + n, testCase); + for (int i = 0; i < n; i++) { + final String s = Integer.toString(i); + assertTrue(cms.getEstimate(i) >= (i + 1L), testCase + " integer " + i); + assertTrue(cms.getEstimate(i) <= cms.getUpperBound(i), testCase + " integer " + i); + assertTrue(cms.getEstimate(s) >= 1, testCase + " string " + s); + assertTrue(cms.getEstimate(s) <= cms.getUpperBound(s), testCase + " string " + s); + } + // Version 2 is deterministic, so the image must equal the one Java builds for the same case + assertEquals(bytes, build(testCase).toByteArray(), testCase); + } + } + + // Section 8.3: the C++ version 1 files deserialize as version 1. Their estimates aren't checked, + // because version 1 hashing differs between languages. + private static void checkCppVersion1Binaries() { + for (final String name : new String[] { "count_min_empty_cpp.sk", "count_min_non_empty_cpp.sk" }) { + final byte[] bytes = getFileBytes(GroupLanguage.CPP.pth, name); + if (bytes.length == 0) { continue; } + final CountMinSketch cms = CountMinSketch.deserialize(bytes, org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED); + assertEquals(cms.getSerialVersion(), CountMinSketch.SERIAL_VERSION_1, name); + assertEquals(cms.isEmpty(), name.startsWith("count_min_empty"), name); + } + } +} diff --git a/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java b/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java index e5adb8ddd..c54c2516d 100644 --- a/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java +++ b/src/test/java/org/apache/datasketches/count/CountMinSketchTest.java @@ -428,6 +428,22 @@ public class CountMinSketchTest { assertEquals(cms.getUpperBound((byte[]) null), 0); } + @Test + public void publicConstructorsUseDefaultSeedAndVersion2() { + final CountMinSketch dflt = new CountMinSketch((byte) 2, 9); + assertEquals(dflt.getSeed_(), org.apache.datasketches.common.Util.DEFAULT_UPDATE_SEED); + assertEquals(dflt.getSerialVersion(), CountMinSketch.SERIAL_VERSION_2); + assertEquals(dflt.toByteArray(), new CountMinSketch((byte) 2, 9, SPEC_SEED).toByteArray()); + + final byte numHashes = CountMinSketch.suggestNumHashes(0.95); + final int numBuckets = CountMinSketch.suggestNumBuckets(0.01); + final CountMinSketch cms = new CountMinSketch(numHashes, numBuckets, 42L); + cms.update("x", 3); + assertEquals(cms.getEstimate("x"), 3); + assertThrows(SketchesArgumentException.class, () -> new CountMinSketch((byte) 0, 9)); + assertThrows(SketchesArgumentException.class, () -> new CountMinSketch((byte) 2, 2)); + } + private static void assertBuckets(final long seed, final long item, final int... buckets) { final CountMinSketch cms = new CountMinSketch((byte) 3, 1000, seed); cms.update(item, 1); --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
