View Javadoc

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, software
13   * distributed under the License is distributed on an "AS IS" BASIS,
14   * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15   * See the License for the specific language governing permissions and
16   * limitations under the License.
17   */
18  package org.apache.hadoop.hbase.util;
19  
20  import java.util.Arrays;
21  import java.util.Random;
22  
23  import org.apache.hadoop.hbase.testclassification.SmallTests;
24  import org.junit.Assert;
25  import org.junit.Test;
26  import org.junit.experimental.categories.Category;
27  
28  import static org.junit.Assert.assertEquals;
29  
30  /**
31   * Testcases for FastLongHistogram.
32   */
33  @Category(SmallTests.class)
34  public class TestFastLongHistogram {
35  
36    private static void doTestUniform(FastLongHistogram hist) {
37      long[] VALUES = { 0, 10, 20, 30, 40, 50 };
38      double[] qs = new double[VALUES.length];
39      for (int i = 0; i < qs.length; i++) {
40        qs[i] = (double) VALUES[i] / VALUES[VALUES.length - 1];
41      }
42  
43      for (int i = 0; i < 10; i++) {
44        for (long v : VALUES) {
45          hist.add(v, 1);
46        }
47        long[] vals = hist.getQuantiles(qs);
48        System.out.println(Arrays.toString(vals));
49        for (int j = 0; j < qs.length; j++) {
50          Assert.assertTrue(j + "-th element org: " + VALUES[j] + ", act: " + vals[j],
51            Math.abs(vals[j] - VALUES[j]) <= 10);
52        }
53        hist.reset();
54      }
55    }
56  
57    @Test
58    public void testUniform() {
59      FastLongHistogram hist = new FastLongHistogram(100, 0, 50);
60      doTestUniform(hist);
61    }
62  
63    @Test
64    public void testAdaptionOfChange() {
65      // assumes the uniform distribution
66      FastLongHistogram hist = new FastLongHistogram(100, 0, 100);
67  
68      Random rand = new Random();
69  
70      for (int n = 0; n < 10; n++) {
71        for (int i = 0; i < 900; i++) {
72          hist.add(rand.nextInt(100), 1);
73        }
74  
75        // add 10% outliers, this breaks the assumption, hope bin10xMax works
76        for (int i = 0; i < 100; i++) {
77          hist.add(1000 + rand.nextInt(100), 1);
78        }
79  
80        long[] vals = hist.getQuantiles(new double[] { 0.25, 0.75, 0.95 });
81        System.out.println(Arrays.toString(vals));
82        if (n == 0) {
83          Assert.assertTrue("Out of possible value", vals[0] >= 0 && vals[0] <= 50);
84          Assert.assertTrue("Out of possible value", vals[1] >= 50 && vals[1] <= 100);
85          Assert.assertTrue("Out of possible value", vals[2] >= 900 && vals[2] <= 1100);
86        }
87  
88        hist.reset();
89      }
90    }
91  
92  
93    @Test
94    public void testGetNumAtOrBelow() {
95      long[] VALUES = { 1, 10, 20, 30, 40, 50 };
96  
97      FastLongHistogram h = new FastLongHistogram();
98      for (long v : VALUES) {
99        for (int i = 0; i < 100; i++) {
100         h.add(v, 1);
101       }
102     }
103 
104     h.add(Integer.MAX_VALUE, 1);
105 
106     h.reset();
107 
108     for (long v : VALUES) {
109       for (int i = 0; i < 100; i++) {
110         h.add(v, 1);
111       }
112     }
113     // Add something way out there to make sure it doesn't throw off the counts.
114     h.add(Integer.MAX_VALUE, 1);
115 
116     assertEquals(100, h.getNumAtOrBelow(1));
117     assertEquals(200, h.getNumAtOrBelow(11));
118     assertEquals(601, h.getNumAtOrBelow(Long.MAX_VALUE));
119   }
120 
121 
122   @Test
123   public void testSameValues() {
124     FastLongHistogram hist = new FastLongHistogram(100);
125 
126     hist.add(50, 100);
127 
128     hist.reset();
129     doTestUniform(hist);
130   }
131 }