1 /* 2 * ContinuousSample.h 3 * 4 * This source file is part of the FoundationDB open source project 5 * 6 * Copyright 2013-2018 Apple Inc. and the FoundationDB project authors 7 * 8 * Licensed under the Apache License, Version 2.0 (the "License"); 9 * you may not use this file except in compliance with the License. 10 * You may obtain a copy of the License at 11 * 12 * http://www.apache.org/licenses/LICENSE-2.0 13 * 14 * Unless required by applicable law or agreed to in writing, software 15 * distributed under the License is distributed on an "AS IS" BASIS, 16 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 17 * See the License for the specific language governing permissions and 18 * limitations under the License. 19 */ 20 21 #ifndef CONTINUOUSSAMPLE_H 22 #define CONTINUOUSSAMPLE_H 23 #pragma once 24 25 #include "flow/Platform.h" 26 #include "flow/IRandom.h" 27 #include <vector> 28 #include <algorithm> 29 #include <cmath> 30 31 template <class T> 32 class ContinuousSample { 33 public: ContinuousSample(int sampleSize)34 explicit ContinuousSample( int sampleSize ) : sampleSize( sampleSize ), populationSize( 0 ), sorted( true ), _min(T()), _max(T()) {} 35 addSample(T sample)36 ContinuousSample<T>& addSample(T sample) { 37 if( !populationSize ) 38 _min = _max = sample; 39 populationSize++; 40 sorted = false; 41 42 if( populationSize <= sampleSize ) { 43 samples.push_back( sample ); 44 } else if( g_random->random01() < ( (double)sampleSize / populationSize ) ) { 45 samples[ g_random->randomInt( 0, sampleSize ) ] = sample; 46 } 47 48 _max = std::max( _max, sample ); 49 _min = std::min( _min, sample ); 50 return *this; 51 } 52 mean()53 double mean() { 54 if (!samples.size()) return 0; 55 T sum = 0; 56 for( int c = 0; c < samples.size(); c++ ) 57 sum += samples[ c ]; 58 return (double)sum / samples.size(); 59 } 60 median()61 T median() { 62 return percentile( 0.5 ); 63 } 64 percentile(double percentile)65 T percentile( double percentile ) { 66 if( !samples.size() || percentile < 0.0 || percentile > 1.0 ) 67 return T(); 68 sort(); 69 int idx = std::floor( ( samples.size() - 1 ) * percentile ); 70 return samples[ idx ]; 71 } 72 min()73 T min() { return _min; } max()74 T max() { return _max; } 75 clear()76 void clear() { 77 samples.clear(); 78 populationSize = 0; 79 sorted = true; 80 _min = _max = 0; // Doesn't work for all T 81 } 82 83 private: 84 int sampleSize; 85 uint64_t populationSize; 86 bool sorted; 87 std::vector<T> samples; 88 T _min, _max; 89 sort()90 void sort() { 91 if( !sorted && samples.size() > 1 ) 92 std::sort( samples.begin(), samples.end() ); 93 sorted = true; 94 } 95 }; 96 97 #endif 98