bundles/org.simantics.history/src/org/simantics/history/util/ClassDistribution.java

   1 /*******************************************************************************
   2  * Copyright (c) 2007 VTT Technical Research Centre of Finland and others.
   3  * All rights reserved. This program and the accompanying materials
   4  * are made available under the terms of the Eclipse Public License v1.0
   5  * which accompanies this distribution, and is available at
   6  * http://www.eclipse.org/legal/epl-v10.html
   7  *
   8  * Contributors:
   9  *     VTT Technical Research Centre of Finland - initial API and implementation
  10  *******************************************************************************/
  11 package org.simantics.history.util;
  12
  13 import java.util.Formatter;
  14 import java.util.Map;
  15 import java.util.Map.Entry;
  16 import java.util.TreeMap;
  17
  18 import org.simantics.databoard.primitives.MutableInteger;
  19
  20 /**
  21  * This class gives a rough distribution classification for double values.
  22  *
  23  * It calculates the frequency of values in each class. All values are
  24  * accounted. There is a value between two samples.
  25  *    n(sample intervals) = n(samples) - 1 <p>
  26  *
  27  * Classes are derieved using logarithmic scale.
  28  * Each class accounts all values within a range [ base ^ class .. base ^ (class-1) ).
  29  *
  30  * Example for classes of base number 2.0
  31  *
  32  * Class Ranges
  33  *   -10   [ 0,98ms .. 1,95ms )
  34  *    -9   [ 1,95ms .. 3,91ms )
  35  *    -8   [ 3,91ms .. 7,81ms )
  36  *    -7   [ 7,81ms .. 15,63ms )
  37  *    -6   [ 15,63ms .. 31,25ms )
  38  *    -5   [ 31,25ms .. 62,50ms )
  39  *    -4   [ 62,50ms .. 125,00ms )
  40  *    -3   [ 125,00ms .. 250,00ms )
  41  *    -2   [ 250,00ms .. 500,00ms )
  42  *    -1   [ 500,00ms .. 1 000,00ms )
  43  *     0   [ 1 000,00ms .. 2 000,00ms )
  44  *    +1   [ 2 000,00ms .. 4 000,00ms )
  45  *    +2   [ 4 000,00ms .. 8 000,00ms )
  46  *    +3   [ 8 000,00ms .. 16 000,00ms )
  47  *    +4   [ 16 000,00ms .. 32 000,00ms )
  48  *    +5   [ 32 000,00ms .. 64 000,00ms )
  49  *    +6   [ 64 000,00ms .. 128 000,00ms )
  50  *    +7   [ 128 000,00ms .. 256 000,00ms )
  51  *    +8   [ 256 000,00ms .. 512 000,00ms )
  52  *    +9   [ 512 000,00ms .. 1 024 000,00ms )
  53  *   +10   [ 1 024 000,00ms .. 2 048 000,00ms )
  54  *
  55  * @author Toni Kalajainen <toni.kalajainen@vtt.fi>
  56  */
  57 public class ClassDistribution {
  58
  59         // Optimization that tries to cirumvent slow Math.log
  60         // previously entered value and its class is remembered
  61         private transient double lastEnteredValue;
  62         private transient int lastClass;
  63
  64         double base;
  65         private transient double log_base;
  66
  67         /** Distribution */
  68         TreeMap<Integer, MutableInteger> distribution;
  69
  70         public ClassDistribution() {
  71                 this( 2.0 );
  72         }
  73
  74         public ClassDistribution(double base) {
  75                 this.base = base;
  76                 log_base = Math.log( base );
  77                 lastEnteredValue = 0.001;
  78                 lastClass = (int) Math.floor( Math.log( 0.001 ) / log_base );
  79                 distribution = new TreeMap<Integer, MutableInteger>();
  80         }
  81
  82         public ClassDistribution(double base, TreeMap<Integer, MutableInteger> initialBreakdown) {
  83                 this.base = base;
  84                 log_base = Math.log( base );
  85                 lastEnteredValue = 0.001;
  86                 lastClass = (int) Math.floor( Math.log( 0.001 ) / log_base );
  87                 distribution = new TreeMap<Integer, MutableInteger>( initialBreakdown );
  88         }
  89
  90         public double getBase() {
  91                 return base;
  92         }
  93
  94         public void setBase(double base) {
  95                 this.base = base;
  96                 log_base = Math.log( base );
  97         }
  98
  99         public double getSmallest() {
 100                 if (distribution.isEmpty()) return 1.0;
 101                 int clazz = distribution.firstKey();
 102                 return getClassAvg(clazz);
 103         }
 104
 105         /**
 106          * Get median value
 107          *
 108          * @return
 109          */
 110         public double getMedian() {
 111                 // Count total
 112                 int n = 0;
 113                 for (MutableInteger v : distribution.values()) n += v.value;
 114
 115                 double median = (double) n/2;
 116                 double sum = 0;
 117                 for (Entry<Integer, MutableInteger> e : distribution.entrySet()) {
 118                         sum += e.getValue().value;
 119                         if (sum==median) {
 120                                 int c = e.getKey();
 121                                 Integer nextC = distribution.higherKey( c );
 122                                 if (nextC == null)
 123                                         return getClassMax( c );
 124
 125                                 return ( getClassMax( c ) + getClassMin( nextC ) ) /2;
 126                         }
 127                         if (sum>median) {
 128                                 int c = e.getKey();
 129                                 return getClassAvg( c );
 130                         }
 131                 }
 132                 return 0;
 133         }
 134
 135         /**
 136          * Get an index to the class with highest frequency.
 137          *
 138          * @return interval class or 0 if there are no samples
 139          */
 140         public int getLargestClassIndex() {
 141                 int result = 0;
 142                 int nResult = -1;
 143                 for (Entry<Integer, MutableInteger> e : distribution.entrySet()) {
 144                         if (e.getValue().value > nResult) {
 145                                 nResult = e.getValue().value;
 146                                 result = e.getKey();
 147                         }
 148                 }
 149                 return result;
 150         }
 151
 152         /**
 153          * Write distribution with user given map.
 154          *
 155          * @param result map where breakdown is written to
 156          */
 157         public void getDistribution(Map<Integer, Integer> result) {
 158                 result.clear();
 159                 for (Entry<Integer, MutableInteger> e : distribution.entrySet()) {
 160                         result.put( e.getKey(), Integer.valueOf(e.getValue().value));
 161                 }
 162         }
 163
 164         public void setDistribution(Map<Integer, Integer> map) {
 165                 this.distribution.clear();
 166                 for (Entry<Integer, Integer> e : map.entrySet()) {
 167                         distribution.put( e.getKey(), new MutableInteger(e.getValue()) );
 168                 }
 169         }
 170
 171         /**
 172          * Create a snapshot copy of the distribution.
 173          *
 174          * @return a histogram
 175          */
 176         public TreeMap<Integer, Integer> getDistribution() {
 177                 TreeMap<Integer, Integer> result = new TreeMap<Integer, Integer>();
 178                 getDistribution(result);
 179                 return result;
 180         }
 181
 182
 183         /**
 184          * Add new value to the distribution.
 185          *
 186          * @param value
 187          */
 188         public void addValue(double value) {
 189                 Integer k = Integer.valueOf( getClassIndex(value) );
 190                 MutableInteger r = distribution.get(k);
 191                 if ( r == null ) {
 192                         r = new MutableInteger();
 193                         distribution.put(k, r);
 194                 }
 195                 r.value ++;
 196         }
 197
 198         /**
 199          * Get lowest value of a class
 200          *
 201          * @param intervalClass
 202          * @return min value
 203          */
 204         public double getClassMin(int intervalClass) {
 205                 return Math.pow(base, intervalClass);
 206         }
 207
 208         /**
 209          * Get highest value of a class
 210          *
 211          * @param intervalClass
 212          * @return max value
 213          */
 214         public double getClassMax(int intervalClass) {
 215                 return Math.pow(base, intervalClass+1);
 216         }
 217
 218         /**
 219          * Get average value of a class
 220          *
 221          * @param intervalClass
 222          * @return average interval
 223          */
 224         public double getClassAvg(int intervalClass) {
 225                 double min = getClassMin(intervalClass);
 226                 double max = getClassMax(intervalClass);
 227                 return (max-min)/2+min;
 228         }
 229
 230         /**
 231          * Get class index for a value
 232          * @param interval
 233          * @return class index
 234          */
 235         public int getClassIndex(double interval) {
 236                 if (interval == lastEnteredValue) return lastClass;
 237                 lastClass = (int) Math.floor( Math.log(interval) / log_base );
 238                 lastEnteredValue = interval;
 239                 return lastClass;
 240         }
 241
 242         @Override
 243         public String toString() {
 244                 StringBuilder sb = new StringBuilder();
 245                 Formatter f = new Formatter(sb);
 246                 sb.append("Index Range Count\n");
 247                 for (Entry<Integer, MutableInteger> e : distribution.entrySet()) {
 248                         int ic = e.getKey();
 249                         double start = getClassMin(ic);
 250                         double end = getClassMax(ic);
 251                         double avg = getClassAvg(ic);
 252                         int count = e.getValue().value;
 253                         String format;
 254                         if (start<0.001) {
 255                                 start *= 1000.0;
 256                                 end *= 1000.0;
 257                                 avg *= 1000.0;
 258                                 format = "  %+3d   [ %(,8fm .. %(,8fm ) = %d, avg = %(,8fm\n";
 259                         } else
 260                         if (start<1) {
 261                                 start *= 1000.0;
 262                                 end *= 1000.0;
 263                                 avg *= 1000.0;
 264                                 format = "  %+3d   [ %(,8.2fm .. %(,8.2fm ) = %d, avg = %(,8.2fm\n";
 265                         } else {
 266                                 format = "  %+3d   [ %(9.0f .. %(9.0f ) = %d, avg = %(8.1f\n";
 267                         }
 268                         f.format(format , ic, start, end, count, avg);
 269                 }
 270                 return sb.toString();
 271         }
 272
 273 }
 274