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]

Reply via email to