You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datasketches.apache.org by le...@apache.org on 2024/01/23 05:46:24 UTC
(datasketches-characterization) branch master updated: New utility class that creates power-law distributions where the sum of the entire distribution is a power of 2.
This is an automated email from the ASF dual-hosted git repository.
leerho pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/datasketches-characterization.git
The following commit(s) were added to refs/heads/master by this push:
new aa33d5d New utility class that creates power-law distributions where the sum of the entire distribution is a power of 2.
aa33d5d is described below
commit aa33d5d6a9d7f6d5fe5e2e4be249b1101253b468
Author: Lee Rhodes <le...@users.noreply.github.com>
AuthorDate: Mon Jan 22 21:46:05 2024 -0800
New utility class that creates power-law distributions where the sum of
the entire distribution is a power of 2.
---
.../org/apache/datasketches/PowersOf2PowerLaw.java | 143 +++++++++++++++++++++
.../apache/datasketches/PowersOf2PowerLawTest.java | 104 +++++++++++++++
2 files changed, 247 insertions(+)
diff --git a/src/main/java/org/apache/datasketches/PowersOf2PowerLaw.java b/src/main/java/org/apache/datasketches/PowersOf2PowerLaw.java
new file mode 100644
index 0000000..903bec9
--- /dev/null
+++ b/src/main/java/org/apache/datasketches/PowersOf2PowerLaw.java
@@ -0,0 +1,143 @@
+/*
+ * 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;
+
+/**
+ * This is a special power law updating scheme that has the following properties:
+ * <ul><li>The grand total weight of all updates is a power of 2.</li>
+ * <li>The total weight of each row of updates at a specific weight is a power of 2.</li>
+ * <li>Each specific weighted update has a weight that is a power of 2.</li>
+ * <li>The number of update rows is a power of 2.</li>
+ *</ul>
+ *
+ * <p>There are 5 schemes and you implement only one of these schemes:</p>
+ * <table>
+ * <caption><big><b>Scheme Details</b></big></caption>
+ * <tbody>
+ * <tr>
+ * <td> <b>Scheme</b></td>
+ * <td><b>WeightPerRow</b> </td>
+ * <td><b>NumRows</b> </td>
+ * <td><b>TotalSchemeWeight</b> </td>
+ * </tr>
+ * <tr>
+ * <td> 1</td>
+ * <td> 2</td>
+ * <td> 2</td>
+ * <td> 4</td>
+ * </tr>
+ * <tr>
+ * <td> 2</td>
+ * <td> 8</td>
+ * <td> 4</td>
+ * <td> 32</td>
+ * </tr>
+ * <tr>
+ * <td> 3</td>
+ * <td> 128</td>
+ * <td> 8</td>
+ * <td> 1,024</td>
+ * </tr>
+ * <tr>
+ * <td> 4</td>
+ * <td> 32,768</td>
+ * <td> 16</td>
+ * <td> 524,288</td>
+ * </tr>
+ * <tr>
+ * <td> 5</td>
+ * <td> 2,147,483,648</td>
+ * <td> 32</td>
+ * <td> 68,719,476,736</td>
+ * </tr>
+ * </tbody>
+ * </table>
+ *
+ * @author Lee Rhodes
+ */
+public final class PowersOf2PowerLaw {
+ //s or scheme is Scheme number
+ //m is Log2(Row Weight) = 2^s -1
+ //w is Row Weight = 2^m
+ //r is Num Rows = 2^s
+ //sw is Scheme Weight = 2^(m + s)
+
+ /**
+ * Gets the total weight of each row.
+ * @param scheme the given scheme, 1 to 5.
+ * @return the total weight of each row.
+ */
+ public static long getTotalRowWeight(final int scheme) {
+ checkScheme(scheme);
+ final long m = (1L << scheme) - 1L;
+ return 1L << m;
+ }
+
+ /**
+ * Gets the total Scheme Weight for all rows with their weights and repetitions.
+ * @param scheme the given scheme, 1 to 5.
+ * @return the total Scheme Weight for all rows with their weights and repetitions.
+ */
+ public static long getTotalSchemeWeight(final int scheme) {
+ checkScheme(scheme);
+ final long m = (1L << scheme) - 1L;
+ return 1L << (m + scheme);
+ }
+
+ /**
+ * Gets the number of rows for a given scheme.
+ * @param scheme the given scheme, 1 to 5.
+ * @return the number of rows for a given scheme.
+ */
+ public static int getNumRows(final int scheme) {
+ checkScheme(scheme);
+ return 1 << scheme;
+ }
+
+ /**
+ * Gets the weight of each update for the given row.
+ * @param row starting with zero, which has a weight of 1, row 1 has a weight of 2,
+ * row n has a weight of 2^n.
+ * @return the weight of updates for the given row.
+ */
+ public static long getRowWeight(final int row) {
+ return 1L << row;
+ }
+
+ /**
+ * Gets the number of repetitions for a given scheme and row.
+ * @param scheme the given scheme, 1 to 5.
+ * @param row starting with zero, which has a weight of 1, row 1 has a weight of 2,
+ * row n has a weight of 2^n.
+ * @return the number of repetitions for a given scheme and row.
+ */
+ public static long getRowReps(final int scheme, final int row) {
+ checkScheme(scheme);
+ final long rw = getTotalRowWeight(scheme);
+ return rw >>> row;
+ }
+
+ private static void checkScheme(final int scheme) {
+ if (scheme < 1 || scheme > 5) {
+ throw new IllegalArgumentException("Scheme must be >= 1 and <= 5.");
+ }
+ }
+
+}
diff --git a/src/test/java/org/apache/datasketches/PowersOf2PowerLawTest.java b/src/test/java/org/apache/datasketches/PowersOf2PowerLawTest.java
new file mode 100644
index 0000000..1e6eed4
--- /dev/null
+++ b/src/test/java/org/apache/datasketches/PowersOf2PowerLawTest.java
@@ -0,0 +1,104 @@
+/*
+ * 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;
+
+import static org.testng.Assert.assertEquals;
+
+import org.testng.annotations.Test;
+
+/**
+ * @author Lee Rhodes
+ */
+@SuppressWarnings({"static-access", "unused"})
+public class PowersOf2PowerLawTest {
+ private static final PowersOf2PowerLaw PL = new PowersOf2PowerLaw();
+
+ @Test
+ public void checkTotalRowWeight() {
+ for (int i = 1; i <= 5; i++) {
+ long m = (1L << i) - 1L;
+ long trw = 1L << m;
+ println(i + ", " + trw);
+ assertEquals(PL.getTotalRowWeight(i), trw);
+ }
+ }
+
+ @Test
+ public void checkTotalSchemeWeight() {
+ for (int i = 1; i <= 5; i++) {
+ long m = (1L << i) - 1L;
+ long tsw = 1L << (m + i);
+ println(i + ", " + tsw);
+ assertEquals(PL.getTotalSchemeWeight(i), tsw);
+ }
+ }
+
+ @Test
+ public void checkNumRows() {
+ for (int i = 1; i <= 5; i++) {
+ int rows = 1 << i;
+ println(i + ", " + rows);
+ assertEquals(PL.getNumRows(i), rows);
+ }
+ }
+
+ @Test
+ public void checkRowWeight() {
+ for (int i = 0; i <= 31; i++) {
+ long rw = 1L << i;
+ println(i + ", " + rw);
+ assertEquals(PL.getRowWeight(i), rw);
+ }
+ }
+
+ @Test
+ public void checkRowReps() {
+ for (int s = 1; s <= 5; s++) {
+ println("scheme = " + s);
+ int numRows = 1 << s;
+ for (int row = 0; row < numRows; row++) {
+ long m = (1L << s) - 1L;
+ long trw = 1L << m;
+ long reps = trw >>> row;
+ println(row + ", " + reps);
+ assertEquals(PL.getRowReps(s, row), reps);
+ }
+ println("");
+ }
+ }
+
+ private final static boolean enablePrinting = false;
+
+ /**
+ * @param format the format
+ * @param args the args
+ */
+ private static final void printf(final String format, final Object ... args) {
+ if (enablePrinting) { System.out.printf(format, args); }
+ }
+
+ /**
+ * @param o the Object to println
+ */
+ private static final void println(final Object o) {
+ if (enablePrinting) { System.out.println(o.toString()); }
+ }
+
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datasketches.apache.org
For additional commands, e-mail: commits-help@datasketches.apache.org