#306

Committed 30 Apr 2024 10:01PM UTC coverage: 97.645% (-0.5%) from 98.139%

Build # #306

Build Type

push

Committed by

Commit Message

Merge pull request #555 from apache/fix_pom_xml_header

Fix pom xml header

Run Details

26865 of 27513 relevant lines covered (97.64%)

0.98 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

97.96

/src/main/java/org/apache/datasketches/cpc/CpcConfidence.java

/*
 * 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.cpc;

import static java.lang.Math.ceil;
import static java.lang.Math.log;
import static java.lang.Math.sqrt;
import static org.apache.datasketches.cpc.IconEstimator.getIconEstimate;

/**
 * Tables and methods for estimating upper and lower bounds.
 *
 * <p>Tables were generated from empirical measurements at N = 1000 * K using millions of trials.
 *
 * @author Lee Rhodes
 */
final class CpcConfidence {
  private static final double iconErrorConstant = log(2.0); //0.693147180559945286
  private static final double hipErrorConstant = sqrt(log(2.0) / 2.0); //0.588705011257737332

  static short[] iconLowSideData = {
    //1,    2,    3,   kappa
    //                 lgK numtrials
    6037, 5720, 5328, // 4 1000000
    6411, 6262, 5682, // 5 1000000
    6724, 6403, 6127, // 6 1000000
    6665, 6411, 6208, // 7 1000000
    6959, 6525, 6427, // 8 1000000
    6892, 6665, 6619, // 9 1000000
    6792, 6752, 6690, // 10 1000000
    6899, 6818, 6708, // 11 1000000
    6871, 6845, 6812, // 12 1046369
    6909, 6861, 6828, // 13 1043411
    6919, 6897, 6842, // 14 1000297
  };

  static short[] iconHighSideData = {
    //1,    2,    3,   kappa
    //                 lgK numtrials
    8031, 8559, 9309, // 4 1000000
    7084, 7959, 8660, // 5 1000000
    7141, 7514, 7876, // 6 1000000
    7458, 7430, 7572, // 7 1000000
    6892, 7141, 7497, // 8 1000000
    6889, 7132, 7290, // 9 1000000
    7075, 7118, 7185, // 10 1000000
    7040, 7047, 7085, // 11 1000000
    6993, 7019, 7053, // 12 1046369
    6953, 7001, 6983, // 13 1043411
    6944, 6966, 7004, // 14 1000297
  };

  static short[] hipLowSideData = {
    //1,    2,    3,   kappa
    //                 lgK numtrials
    5871, 5247, 4826, // 4 1000000
    5877, 5403, 5070, // 5 1000000
    5873, 5533, 5304, // 6 1000000
    5878, 5632, 5464, // 7 1000000
    5874, 5690, 5564, // 8 1000000
    5880, 5745, 5619, // 9 1000000
    5875, 5784, 5701, // 10 1000000
    5866, 5789, 5742, // 11 1000000
    5869, 5827, 5784, // 12 1046369
    5876, 5860, 5827, // 13 1043411
    5881, 5853, 5842, // 14 1000297
  };

  static short[] hipHighSideData = {
    //1,    2,    3,   kappa
    //                 lgK numtrials
    5855, 6688, 7391, // 4 1000000
    5886, 6444, 6923, // 5 1000000
    5885, 6254, 6594, // 6 1000000
    5889, 6134, 6326, // 7 1000000
    5900, 6072, 6203, // 8 1000000
    5875, 6005, 6089, // 9 1000000
    5871, 5980, 6040, // 10 1000000
    5889, 5941, 6015, // 11 1000000
    5871, 5926, 5973, // 12 1046369
    5866, 5901, 5915, // 13 1043411
    5880, 5914, 5953, // 14 1000297
  };

  static double getIconConfidenceLB(final int lgK, final long numCoupons, final int kappa) {
    if (numCoupons == 0) { return 0.0; }
    assert lgK >= 4;
    assert (kappa >= 1) && (kappa <= 3);
    double x = iconErrorConstant;
    if (lgK <= 14) { x = (iconHighSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }
    final double rel = x / sqrt(1 << lgK);
    final double eps = kappa * rel;
    final double est = getIconEstimate(lgK, numCoupons);
    double result = est / (1.0 + eps);
    if (result < numCoupons) { result = numCoupons; }
    return result;
  }

  static double getIconConfidenceUB(final int lgK, final long numCoupons, final int kappa) {
    if (numCoupons == 0) { return 0.0; }
    assert lgK >= 4;
    assert (kappa >= 1) && (kappa <= 3);
    double x = iconErrorConstant;
    if (lgK <= 14) { x = (iconLowSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }
    final double rel = x / sqrt(1 << lgK);
    final double eps = kappa * rel;
    final double est = getIconEstimate(lgK, numCoupons);
    final double result = est / (1.0 - eps);
    return ceil(result);  // slight widening of interval to be conservative
  }

  //mergeFlag must already be checked as false
  static double getHipConfidenceLB(final int lgK, final long numCoupons, final double hipEstAccum,
      final int kappa) {
    if (numCoupons == 0) { return 0.0; }
    assert lgK >= 4;
    assert (kappa >= 1) && (kappa <= 3);
    double x = hipErrorConstant;
    if (lgK <= 14) { x = (hipHighSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }
    final double rel = x / sqrt(1 << lgK);
    final double eps = kappa * rel;
    final double est = hipEstAccum;
    double result = est / (1.0 + eps);
    if (result < numCoupons) { result = numCoupons; }
    return result;
  }

  //mergeFlag must already be checked as false
  static double getHipConfidenceUB(final int lgK, final long numCoupons, final double hipEstAccum,
      final int kappa) {
    if (numCoupons == 0) { return 0.0; }
    assert lgK >= 4;
    assert (kappa >= 1) && (kappa <= 3);
    double x = hipErrorConstant;
    if (lgK <= 14) { x = (hipLowSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }
    final double rel = x / sqrt(1 << lgK);
    final double eps = kappa * rel;
    final double est = hipEstAccum;
    final double result = est / (1.0 - eps);
    return ceil(result); // widening for coverage
  }

}

1	/*
2	* Licensed to the Apache Software Foundation (ASF) under one
3	* or more contributor license agreements. See the NOTICE file
4	* distributed with this work for additional information
5	* regarding copyright ownership. The ASF licenses this file
6	* to you under the Apache License, Version 2.0 (the
7	* "License"); you may not use this file except in compliance
8	* with the License. You may obtain a copy of the License at
9	*
10	* http://www.apache.org/licenses/LICENSE-2.0
11	*
12	* Unless required by applicable law or agreed to in writing,
13	* software distributed under the License is distributed on an
14	* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15	* KIND, either express or implied. See the License for the
16	* specific language governing permissions and limitations
17	* under the License.
18	*/
19
20	package org.apache.datasketches.cpc;
21
22	import static java.lang.Math.ceil;
23	import static java.lang.Math.log;
24	import static java.lang.Math.sqrt;
25	import static org.apache.datasketches.cpc.IconEstimator.getIconEstimate;
26
27	/**
28	* Tables and methods for estimating upper and lower bounds.
29	*
30	* <p>Tables were generated from empirical measurements at N = 1000 * K using millions of trials.
31	*
32	* @author Lee Rhodes
33	*/
34	final class CpcConfidence {	×
35	private static final double iconErrorConstant = log(2.0); //0.693147180559945286	1✔
36	private static final double hipErrorConstant = sqrt(log(2.0) / 2.0); //0.588705011257737332	1✔
37
38	static short[] iconLowSideData = {	1✔
39	//1, 2, 3, kappa
40	// lgK numtrials
41	6037, 5720, 5328, // 4 1000000
42	6411, 6262, 5682, // 5 1000000
43	6724, 6403, 6127, // 6 1000000
44	6665, 6411, 6208, // 7 1000000
45	6959, 6525, 6427, // 8 1000000
46	6892, 6665, 6619, // 9 1000000
47	6792, 6752, 6690, // 10 1000000
48	6899, 6818, 6708, // 11 1000000
49	6871, 6845, 6812, // 12 1046369
50	6909, 6861, 6828, // 13 1043411
51	6919, 6897, 6842, // 14 1000297
52	};
53
54	static short[] iconHighSideData = {	1✔
55	//1, 2, 3, kappa
56	// lgK numtrials
57	8031, 8559, 9309, // 4 1000000
58	7084, 7959, 8660, // 5 1000000
59	7141, 7514, 7876, // 6 1000000
60	7458, 7430, 7572, // 7 1000000
61	6892, 7141, 7497, // 8 1000000
62	6889, 7132, 7290, // 9 1000000
63	7075, 7118, 7185, // 10 1000000
64	7040, 7047, 7085, // 11 1000000
65	6993, 7019, 7053, // 12 1046369
66	6953, 7001, 6983, // 13 1043411
67	6944, 6966, 7004, // 14 1000297
68	};
69
70	static short[] hipLowSideData = {	1✔
71	//1, 2, 3, kappa
72	// lgK numtrials
73	5871, 5247, 4826, // 4 1000000
74	5877, 5403, 5070, // 5 1000000
75	5873, 5533, 5304, // 6 1000000
76	5878, 5632, 5464, // 7 1000000
77	5874, 5690, 5564, // 8 1000000
78	5880, 5745, 5619, // 9 1000000
79	5875, 5784, 5701, // 10 1000000
80	5866, 5789, 5742, // 11 1000000
81	5869, 5827, 5784, // 12 1046369
82	5876, 5860, 5827, // 13 1043411
83	5881, 5853, 5842, // 14 1000297
84	};
85
86	static short[] hipHighSideData = {	1✔
87	//1, 2, 3, kappa
88	// lgK numtrials
89	5855, 6688, 7391, // 4 1000000
90	5886, 6444, 6923, // 5 1000000
91	5885, 6254, 6594, // 6 1000000
92	5889, 6134, 6326, // 7 1000000
93	5900, 6072, 6203, // 8 1000000
94	5875, 6005, 6089, // 9 1000000
95	5871, 5980, 6040, // 10 1000000
96	5889, 5941, 6015, // 11 1000000
97	5871, 5926, 5973, // 12 1046369
98	5866, 5901, 5915, // 13 1043411
99	5880, 5914, 5953, // 14 1000297
100	};
101
102	static double getIconConfidenceLB(final int lgK, final long numCoupons, final int kappa) {
103	if (numCoupons == 0) { return 0.0; }	1✔
104	assert lgK >= 4;	1✔
105	assert (kappa >= 1) && (kappa <= 3);	1✔
106	double x = iconErrorConstant;	1✔
107	if (lgK <= 14) { x = (iconHighSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }	1✔
108	final double rel = x / sqrt(1 << lgK);	1✔
109	final double eps = kappa * rel;	1✔
110	final double est = getIconEstimate(lgK, numCoupons);	1✔
111	double result = est / (1.0 + eps);	1✔
112	if (result < numCoupons) { result = numCoupons; }	1✔
113	return result;	1✔
114	}
115
116	static double getIconConfidenceUB(final int lgK, final long numCoupons, final int kappa) {
117	if (numCoupons == 0) { return 0.0; }	1✔
118	assert lgK >= 4;	1✔
119	assert (kappa >= 1) && (kappa <= 3);	1✔
120	double x = iconErrorConstant;	1✔
121	if (lgK <= 14) { x = (iconLowSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }	1✔
122	final double rel = x / sqrt(1 << lgK);	1✔
123	final double eps = kappa * rel;	1✔
124	final double est = getIconEstimate(lgK, numCoupons);	1✔
125	final double result = est / (1.0 - eps);	1✔
126	return ceil(result); // slight widening of interval to be conservative	1✔
127	}
128
129	//mergeFlag must already be checked as false
130	static double getHipConfidenceLB(final int lgK, final long numCoupons, final double hipEstAccum,
131	final int kappa) {
132	if (numCoupons == 0) { return 0.0; }	1✔
133	assert lgK >= 4;	1✔
134	assert (kappa >= 1) && (kappa <= 3);	1✔
135	double x = hipErrorConstant;	1✔
136	if (lgK <= 14) { x = (hipHighSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }	1✔
137	final double rel = x / sqrt(1 << lgK);	1✔
138	final double eps = kappa * rel;	1✔
139	final double est = hipEstAccum;	1✔
140	double result = est / (1.0 + eps);	1✔
141	if (result < numCoupons) { result = numCoupons; }	1✔
142	return result;	1✔
143	}
144
145	//mergeFlag must already be checked as false
146	static double getHipConfidenceUB(final int lgK, final long numCoupons, final double hipEstAccum,
147	final int kappa) {
148	if (numCoupons == 0) { return 0.0; }	1✔
149	assert lgK >= 4;	1✔
150	assert (kappa >= 1) && (kappa <= 3);	1✔
151	double x = hipErrorConstant;	1✔
152	if (lgK <= 14) { x = (hipLowSideData[(3 * (lgK - 4)) + (kappa - 1)]) / 10000.0; }	1✔
153	final double rel = x / sqrt(1 << lgK);	1✔
154	final double eps = kappa * rel;	1✔
155	final double est = hipEstAccum;	1✔
156	final double result = est / (1.0 - eps);	1✔
157	return ceil(result); // widening for coverage	1✔
158	}
159
160	}

apache / datasketches-java / #306

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous