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