This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-java.git
The following commit(s) were added to refs/heads/main by this push:
new 62c2308f4 REQ: use a long shift for compactor weights in the sorted
view (#787)
62c2308f4 is described below
commit 62c2308f4fa6ace7347ae0c0e387c8d8f1eb61f2
Author: Lee Rhodes <[email protected]>
AuthorDate: Fri Oct 30 19:30:43 2026 -0700
REQ: use a long shift for compactor weights in the sorted view (#787)
The sorted view weighted each compactor's items by 1 << lgWeight, an int
shift. From level 31 up the weight was wrong (level 31 gave a negative
weight, level 32 a weight of 1), so ranks and quantiles of very large
sketches were wrong. The shift is now 1L << lgWeight, as in C++.
Co-authored-by: Claude Opus 5.5 <[email protected]>
---
.../org/apache/datasketches/req/ReqSketch.java | 2 +-
.../datasketches/req/ReqSketchSortedViewTest.java | 28 ++++++++++++++++++++++
2 files changed, 29 insertions(+), 1 deletion(-)
diff --git a/src/main/java/org/apache/datasketches/req/ReqSketch.java
b/src/main/java/org/apache/datasketches/req/ReqSketch.java
index 7de815750..eda33acd2 100644
--- a/src/main/java/org/apache/datasketches/req/ReqSketch.java
+++ b/src/main/java/org/apache/datasketches/req/ReqSketch.java
@@ -588,7 +588,7 @@ public final class ReqSketch extends BaseReqSketch {
for (int i = 0; i < numComp; i++) {
final ReqCompactor c = compactors.get(i);
final FloatBuffer fbufIn = c.getBuffer();
- final long fbufWeight = 1 << c.getLgWeight();
+ final long fbufWeight = 1L << c.getLgWeight();
final int fbufInLen = fbufIn.getCount();
mergeSortIn(fbufIn, fbufWeight, count, getHighRankAccuracyMode());
count += fbufInLen;
diff --git
a/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
b/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
index 09c4724e3..e3e4f7992 100644
--- a/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
+++ b/src/test/java/org/apache/datasketches/req/ReqSketchSortedViewTest.java
@@ -24,6 +24,9 @@ import static
org.apache.datasketches.quantilescommon.QuantileSearchCriteria.INC
import static org.testng.Assert.assertEquals;
import static org.testng.Assert.assertTrue;
+import java.util.ArrayList;
+import java.util.List;
+
import org.apache.datasketches.quantilescommon.FloatsSortedView;
import org.apache.datasketches.quantilescommon.FloatsSortedViewIterator;
import org.testng.annotations.Test;
@@ -94,6 +97,31 @@ public class ReqSketchSortedViewTest {
printIterator(itr);
}
+ @Test
+ public void highLevelWeights() {
+ //One item per compactor, levels 0 to 32. The item at level h has the
value h and weight 2^h.
+ final int numLevels = 33;
+ for (final boolean hraMode : new boolean[] {false, true}) {
+ final List<ReqCompactor> compactors = new ArrayList<>();
+ long totalN = 0;
+ for (int h = 0; h < numLevels; h++) {
+ final FloatBuffer buf = FloatBuffer.reconstruct(new float[] {h}, 1, 1,
0, true, hraMode);
+ compactors.add(new ReqCompactor((byte) h, hraMode, 0, 12f, (byte) 3,
buf));
+ totalN += 1L << h;
+ }
+ final ReqSketch sketch = new ReqSketch(12, hraMode, totalN, 0f,
numLevels - 1, compactors);
+ sketch.setRetainedItems(sketch.computeTotalRetainedItems());
+ final FloatsSortedViewIterator itr = sketch.getSortedView().iterator();
+ for (int h = 0; h < numLevels; h++) {
+ assertTrue(itr.next());
+ assertEquals(itr.getQuantile(), (float) h);
+ assertEquals(itr.getWeight(), 1L << h);
+ assertEquals(itr.getNaturalRank(INCLUSIVE), (1L << (h + 1)) - 1);
+ }
+ assertEquals(sketch.getSortedView().getN(), totalN);
+ }
+ }
+
private static void printIterator(final FloatsSortedViewIterator itr) {
println("");
String[] header = {"Value", "Wt", "CumWtNotInc", "NormRankNotInc",
"CumWtInc", "NormRankInc"};
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]