#165

Build # #165

Build Type

push

Committed by

Commit Message

<a href="https://github.com/apache/datasketches-java/commit/<a class=hub.com/apache/datasketches-java/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/datasketches-java/commit/<a class="double-link" href="https://git"><a class=hub.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f74028cbb7e1">6daba81d9<a href="https://github.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f74028cbb7e1">&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/apache/datasketches-java/commit/&lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/&amp;lt;a class=&amp;quot;double-link&amp;quot; href=&amp;quot;https://git&quot;&gt;&amp;lt;a class=&lt;/a&gt;hub.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f74028cbb7e1&quot;&gt;6daba81d9&lt;/a&gt;&lt;a href=&quot;https://github.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f74028cbb7e1&quot;&gt;&amp;lt;a href=&amp;quot;https://github.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f740&lt;/a&gt;28cbb7e1&quot;>&quot;&gt;Merge &lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/<a class="double-link" href="https://github.com/apache/datasketches-java/commit/719fb6ab93edd45277f47f77eb7b1f50b896f594">719fb6ab9</a><a href="https://github.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f74028cbb7e1">&amp;quot;&amp;gt;719fb6ab9&amp;lt;/a&amp;gt;&amp;quot;&amp;gt;719fb6ab9&amp;lt;/a&amp;gt;&amp;lt;a href=&amp;quot;https://github.com/apache/datasketches-java/commit/6daba81d90cbe1458581bb61e3b8f74028cbb&lt;/a&gt;7e1&quot;&gt; into &lt;/a&gt;&lt;a class=&quot;double-link&quot; href=&quot;https://github.com/apache/datasketches-java/commit/<a class="double-link" href="https://github.com/apache/datasketches-java/commit/3ef667872">3ef667872">3ef667872</a>

Run Details

714 of 714 new or added lines in 10 files covered. (100.0%)

18523 of 18850 relevant lines covered (98.27%)

0.98 hits per line

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

91.46

/src/main/java/org/apache/datasketches/kll/KllDoublesQuantileCalculator.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.kll;

import java.util.Arrays;

import org.apache.datasketches.QuantilesHelper;

/**
 * Data structure for answering quantile queries based on the samples from KllSketch
 * @author Kevin Lang
 * @author Alexander Saydakov
 */
final class KllDoublesQuantileCalculator {

  private final long n_;
  private final double[] items_;
  private final long[] weights_; //comes in as weights, converted to cumulative weights
  private final int[] levels_;
  private int numLevels_;

  // assumes that all levels are sorted including level 0
  KllDoublesQuantileCalculator(final double[] items, final int[] levels, final int numLevels,
      final long n) {
    n_ = n;
    final int numItems = levels[numLevels] - levels[0];
    items_ = new double[numItems];
    weights_ = new long[numItems + 1]; // one more is intentional
    levels_ = new int[numLevels + 1];
    populateFromSketch(items, levels, numLevels, numItems);
    blockyTandemMergeSort(items_, weights_, levels_, numLevels_);
    QuantilesHelper.convertToPrecedingCummulative(weights_);
  }

  //For testing only. Allows testing of getQuantile without a sketch.
  KllDoublesQuantileCalculator(final double[] items, final long[] weights, final long n) {
    n_ = n;
    items_ = items;
    weights_ = weights; //must be size of items + 1
    levels_ = null;  //not used by test
    numLevels_ = 0;  //not used by test
  }

  double getQuantile(final double phi) { //phi is normalized rank [0,1].
    final long pos = QuantilesHelper.posOfPhi(phi, n_);
    return approximatelyAnswerPositonalQuery(pos);
  }

  private double approximatelyAnswerPositonalQuery(final long pos) {
    assert pos >= 0;
    assert pos < n_;
    final int index = QuantilesHelper.chunkContainingPos(weights_, pos);
    return items_[index];
  }

  private void populateFromSketch(final double[] srcItems, final int[] srcLevels,
      final int numLevels, final int numItems) {
    final int offset = srcLevels[0];
    System.arraycopy(srcItems, offset, items_, 0, numItems);
    int srcLevel = 0;
    int dstLevel = 0;
    long weight = 1;
    while (srcLevel < numLevels) {
      final int fromIndex = srcLevels[srcLevel] - offset;
      final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive
      if (fromIndex < toIndex) { // if equal, skip empty level
        Arrays.fill(weights_, fromIndex, toIndex, weight);
        levels_[dstLevel] = fromIndex;
        levels_[dstLevel + 1] = toIndex;
        dstLevel++;
      }
      srcLevel++;
      weight *= 2;
    }
    weights_[numItems] = 0;
    numLevels_ = dstLevel;
  }

  private static void blockyTandemMergeSort(final double[] items, final long[] weights,
      final int[] levels, final int numLevels) {
    if (numLevels == 1) { return; }

    // duplicate the input in preparation for the "ping-pong" copy reduction strategy.
    final double[] itemsTmp = Arrays.copyOf(items, items.length);
    final long[] weightsTmp = Arrays.copyOf(weights, items.length); // don't need the extra one here

    blockyTandemMergeSortRecursion(itemsTmp, weightsTmp, items, weights, levels, 0, numLevels);
  }

  private static void blockyTandemMergeSortRecursion(
      final double[] itemsSrc, final long[] weightsSrc,
      final double[] itemsDst, final long[] weightsDst,
      final int[] levels, final int startingLevel, final int numLevels) {
    if (numLevels == 1) { return; }
    final int numLevels1 = numLevels / 2;
    final int numLevels2 = numLevels - numLevels1;
    assert numLevels1 >= 1;
    assert numLevels2 >= numLevels1;
    final int startingLevel1 = startingLevel;
    final int startingLevel2 = startingLevel + numLevels1;
    // swap roles of src and dst
    blockyTandemMergeSortRecursion(
        itemsDst, weightsDst,
        itemsSrc, weightsSrc,
        levels, startingLevel1, numLevels1);
    blockyTandemMergeSortRecursion(
        itemsDst, weightsDst,
        itemsSrc, weightsSrc,
        levels, startingLevel2, numLevels2);
    tandemMerge(
        itemsSrc, weightsSrc,
        itemsDst, weightsDst,
        levels,
        startingLevel1, numLevels1,
        startingLevel2, numLevels2);
  }

  private static void tandemMerge(
      final double[] itemsSrc, final long[] weightsSrc,
      final double[] itemsDst, final long[] weightsDst,
      final int[] levelStarts,
      final int startingLevel1, final int numLevels1,
      final int startingLevel2, final int numLevels2) {
    final int fromIndex1 = levelStarts[startingLevel1];
    final int toIndex1 = levelStarts[startingLevel1 + numLevels1]; // exclusive
    final int fromIndex2 = levelStarts[startingLevel2];
    final int toIndex2 = levelStarts[startingLevel2 + numLevels2]; // exclusive
    int iSrc1 = fromIndex1;
    int iSrc2 = fromIndex2;
    int iDst = fromIndex1;

    while (iSrc1 < toIndex1 && iSrc2 < toIndex2) {
      if (itemsSrc[iSrc1] < itemsSrc[iSrc2]) {
        itemsDst[iDst] = itemsSrc[iSrc1];
        weightsDst[iDst] = weightsSrc[iSrc1];
        iSrc1++;
      } else {
        itemsDst[iDst] = itemsSrc[iSrc2];
        weightsDst[iDst] = weightsSrc[iSrc2];
        iSrc2++;
      }
      iDst++;
    }
    if (iSrc1 < toIndex1) {
      System.arraycopy(itemsSrc, iSrc1, itemsDst, iDst, toIndex1 - iSrc1);
      System.arraycopy(weightsSrc, iSrc1, weightsDst, iDst, toIndex1 - iSrc1);
    } else if (iSrc2 < toIndex2) {
      System.arraycopy(itemsSrc, iSrc2, itemsDst, iDst, toIndex2 - iSrc2);
      System.arraycopy(weightsSrc, iSrc2, weightsDst, iDst, toIndex2 - iSrc2);
    }
  }

}


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.kll;
21
22	import java.util.Arrays;
23
24	import org.apache.datasketches.QuantilesHelper;
25
26	/**
27	* Data structure for answering quantile queries based on the samples from KllSketch
28	* @author Kevin Lang
29	* @author Alexander Saydakov
30	*/
31	final class KllDoublesQuantileCalculator {	1✔
32
33	private final long n_;
34	private final double[] items_;
35	private final long[] weights_; //comes in as weights, converted to cumulative weights
36	private final int[] levels_;
37	private int numLevels_;
38
39	// assumes that all levels are sorted including level 0
40	KllDoublesQuantileCalculator(final double[] items, final int[] levels, final int numLevels,
41	final long n) {	1✔
42	n_ = n;	1✔
43	final int numItems = levels[numLevels] - levels[0];	1✔
44	items_ = new double[numItems];	1✔
45	weights_ = new long[numItems + 1]; // one more is intentional	1✔
46	levels_ = new int[numLevels + 1];	1✔
47	populateFromSketch(items, levels, numLevels, numItems);	1✔
48	blockyTandemMergeSort(items_, weights_, levels_, numLevels_);	1✔
49	QuantilesHelper.convertToPrecedingCummulative(weights_);	1✔
50	}	1✔
51
52	//For testing only. Allows testing of getQuantile without a sketch.
53	KllDoublesQuantileCalculator(final double[] items, final long[] weights, final long n) {	×
54	n_ = n;	×
55	items_ = items;	×
56	weights_ = weights; //must be size of items + 1	×
57	levels_ = null; //not used by test	×
58	numLevels_ = 0; //not used by test	×
59	}	×
60
61	double getQuantile(final double phi) { //phi is normalized rank [0,1].
62	final long pos = QuantilesHelper.posOfPhi(phi, n_);	1✔
63	return approximatelyAnswerPositonalQuery(pos);	1✔
64	}
65
66	private double approximatelyAnswerPositonalQuery(final long pos) {
67	assert pos >= 0;	1✔
68	assert pos < n_;	1✔
69	final int index = QuantilesHelper.chunkContainingPos(weights_, pos);	1✔
70	return items_[index];	1✔
71	}
72
73	private void populateFromSketch(final double[] srcItems, final int[] srcLevels,
74	final int numLevels, final int numItems) {
75	final int offset = srcLevels[0];	1✔
76	System.arraycopy(srcItems, offset, items_, 0, numItems);	1✔
77	int srcLevel = 0;	1✔
78	int dstLevel = 0;	1✔
79	long weight = 1;	1✔
80	while (srcLevel < numLevels) {	1✔
81	final int fromIndex = srcLevels[srcLevel] - offset;	1✔
82	final int toIndex = srcLevels[srcLevel + 1] - offset; // exclusive	1✔
83	if (fromIndex < toIndex) { // if equal, skip empty level	1✔
84	Arrays.fill(weights_, fromIndex, toIndex, weight);	1✔
85	levels_[dstLevel] = fromIndex;	1✔
86	levels_[dstLevel + 1] = toIndex;	1✔
87	dstLevel++;	1✔
88	}
89	srcLevel++;	1✔
90	weight *= 2;	1✔
91	}	1✔
92	weights_[numItems] = 0;	1✔
93	numLevels_ = dstLevel;	1✔
94	}	1✔
95
96	private static void blockyTandemMergeSort(final double[] items, final long[] weights,
97	final int[] levels, final int numLevels) {
98	if (numLevels == 1) { return; }	1✔
99
100	// duplicate the input in preparation for the "ping-pong" copy reduction strategy.
101	final double[] itemsTmp = Arrays.copyOf(items, items.length);	1✔
102	final long[] weightsTmp = Arrays.copyOf(weights, items.length); // don't need the extra one here	1✔
103
104	blockyTandemMergeSortRecursion(itemsTmp, weightsTmp, items, weights, levels, 0, numLevels);	1✔
105	}	1✔
106
107	private static void blockyTandemMergeSortRecursion(
108	final double[] itemsSrc, final long[] weightsSrc,
109	final double[] itemsDst, final long[] weightsDst,
110	final int[] levels, final int startingLevel, final int numLevels) {
111	if (numLevels == 1) { return; }	1✔
112	final int numLevels1 = numLevels / 2;	1✔
113	final int numLevels2 = numLevels - numLevels1;	1✔
114	assert numLevels1 >= 1;	1✔
115	assert numLevels2 >= numLevels1;	1✔
116	final int startingLevel1 = startingLevel;	1✔
117	final int startingLevel2 = startingLevel + numLevels1;	1✔
118	// swap roles of src and dst
119	blockyTandemMergeSortRecursion(	1✔
120	itemsDst, weightsDst,
121	itemsSrc, weightsSrc,
122	levels, startingLevel1, numLevels1);
123	blockyTandemMergeSortRecursion(	1✔
124	itemsDst, weightsDst,
125	itemsSrc, weightsSrc,
126	levels, startingLevel2, numLevels2);
127	tandemMerge(	1✔
128	itemsSrc, weightsSrc,
129	itemsDst, weightsDst,
130	levels,
131	startingLevel1, numLevels1,
132	startingLevel2, numLevels2);
133	}	1✔
134
135	private static void tandemMerge(
136	final double[] itemsSrc, final long[] weightsSrc,
137	final double[] itemsDst, final long[] weightsDst,
138	final int[] levelStarts,
139	final int startingLevel1, final int numLevels1,
140	final int startingLevel2, final int numLevels2) {
141	final int fromIndex1 = levelStarts[startingLevel1];	1✔
142	final int toIndex1 = levelStarts[startingLevel1 + numLevels1]; // exclusive	1✔
143	final int fromIndex2 = levelStarts[startingLevel2];	1✔
144	final int toIndex2 = levelStarts[startingLevel2 + numLevels2]; // exclusive	1✔
145	int iSrc1 = fromIndex1;	1✔
146	int iSrc2 = fromIndex2;	1✔
147	int iDst = fromIndex1;	1✔
148
149	while (iSrc1 < toIndex1 && iSrc2 < toIndex2) {	1✔
150	if (itemsSrc[iSrc1] < itemsSrc[iSrc2]) {	1✔
151	itemsDst[iDst] = itemsSrc[iSrc1];	1✔
152	weightsDst[iDst] = weightsSrc[iSrc1];	1✔
153	iSrc1++;	1✔
154	} else {
155	itemsDst[iDst] = itemsSrc[iSrc2];	1✔
156	weightsDst[iDst] = weightsSrc[iSrc2];	1✔
157	iSrc2++;	1✔
158	}
159	iDst++;	1✔
160	}
161	if (iSrc1 < toIndex1) {	1✔
162	System.arraycopy(itemsSrc, iSrc1, itemsDst, iDst, toIndex1 - iSrc1);	1✔
163	System.arraycopy(weightsSrc, iSrc1, weightsDst, iDst, toIndex1 - iSrc1);	1✔
164	} else if (iSrc2 < toIndex2) {	1✔
165	System.arraycopy(itemsSrc, iSrc2, itemsDst, iDst, toIndex2 - iSrc2);	1✔
166	System.arraycopy(weightsSrc, iSrc2, weightsDst, iDst, toIndex2 - iSrc2);	1✔
167	}
168	}	1✔
169
170	}
171

apache / datasketches-java / #165

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