1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
#include "distributions.hpp"
#include <algorithm>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <random>
#include <string>
#include <vector>
#if defined(_MSC_VER)
#pragma warning(push)
#pragma warning(disable : 4189) // Disable some compiler warnings that come from fmt
#endif
#include <fmt/std.h>
#if defined(_MSC_VER)
#pragma warning(pop)
#endif
/*
@param bins: std::vector<DistributionPair>&, reference to vector of bins
@param element: std::uint32_t, the number to insert - fractional values
should be `floored` as to meet the fractional requirements of the
program
@param start: std::uint8_t, the beginning of the current window
@param end: std::uint8_t, the end of the current window
@return DistributionPair*: pointer to the bin element fits in
*/
DistributionPair* binarySearchBins(std::vector<DistributionPair>& bins,
std::uint32_t element, std::uint8_t start,
std::uint8_t end);
/*
@param min: uint32_t, the minvalue value of the first bin
@param max: uint32_t, the maxvalue of the last bin
@param howMany: uint32_t, the number of bins to create
@return std::vector<DistributionPair>: a vector of bins initialized
with count = 0
*/
std::vector<DistributionPair>
initializeBins(std::uint32_t min, std::uint32_t max, std::uint8_t howMany);
DistributionPair* binarySearchBins(std::vector<DistributionPair>& bins,
std::uint32_t element, std::uint8_t start,
std::uint8_t end)
{
std::uint8_t mid = (end + start) / 2;
DistributionPair* dP = &bins.at(mid);
// Base cases:
// 1. Our element is less than the minimum in the bins
// 2. Our element is greater than maximum in the bins
// 3. Our element belongs in the current bin
if (end <= start || mid == bins.size() - 1 ||
(dP->minValue <= element && dP->maxValue >= element))
return dP;
// RESCURSION!!!
if (dP->maxValue < element)
return binarySearchBins(bins, element, mid, end);
return binarySearchBins(bins, element, start, mid);
}
std::vector<DistributionPair>
initializeBins(std::uint32_t min, std::uint32_t max, std::uint8_t howMany)
{
std::vector<DistributionPair> bins;
// The difference between each minValue and maxValue of each bin can be zero
// if numBins = num. of elements
std::uint32_t delta = static_cast<uint32_t>(
std::ceil((static_cast<float>(max - min) / howMany) - 1));
for (std::uint32_t i = 0; i < howMany; i++)
{
std::uint32_t newMin = min;
if (i)
newMin = bins.at(i - 1).maxValue + 1;
DistributionPair newBin(newMin, newMin + delta);
bins.push_back(newBin);
}
return bins;
}
void plotDistribution(std::string title,
const std::vector<DistributionPair>& distribution,
const std::uint8_t maxPlotLineSize)
{
std::cout << fmt::format("{}", title) << std::endl;
std::uint32_t maxCount =
std::max_element(
std::begin(distribution), std::end(distribution),
[](const DistributionPair bin1, const DistributionPair bin2)
{ return bin1.count < bin2.count; })
->count;
std::uint32_t maxBinElementWidth = static_cast<uint32_t>(ceil(log10(distribution.back().maxValue)) + 1);
std::uint32_t binThreshold = maxCount / maxPlotLineSize;
for (const DistributionPair bin : distribution)
{
std::cout << fmt::format("[{0:>{1}}, {2:>{3}}] {4:<{5}}", bin.minValue,
maxBinElementWidth, bin.maxValue,
maxBinElementWidth, std::string(bin.count / binThreshold, '*'), maxPlotLineSize)
<< std::endl;
}
}
std::vector<DistributionPair>
generateUniformDistribution(std::uint32_t howMany, std::uint32_t min,
std::uint32_t max, std::uint8_t numberBins)
{
std::vector<DistributionPair> bins = initializeBins(min, max, numberBins);
std::default_random_engine generator;
std::uniform_int_distribution<int> distribution(min, max);
for (std::uint32_t i = 0; i < howMany; i++)
{
uint32_t randomElement = distribution(generator);
binarySearchBins(bins, randomElement, 0, numberBins)->count++;
}
return bins;
}
std::vector<DistributionPair>
generateNormalDistribution(std::uint32_t howMany, float mean, float stdev,
std::uint8_t numberBins)
{
std::uint32_t min = static_cast<std::uint32_t>(mean - 4 * stdev);
std::uint32_t max = static_cast<std::uint32_t>(mean + 4 * stdev);
// Get the right number of bins
if (((max - min) % numberBins > 0) && (((max - 1) - min) % numberBins == 0))
max -= 1;
std::vector<DistributionPair> bins = initializeBins(min, max, numberBins);
std::default_random_engine generator;
std::normal_distribution<float> distribution(mean, stdev);
for (std::uint32_t i = 0; i < howMany; i++)
{
uint32_t randomElement = static_cast<uint32_t>(distribution(generator));
binarySearchBins(bins, randomElement, 0, numberBins)->count++;
}
return bins;
}
std::vector<DistributionPair>
generatePoissonDistribution(std::uint32_t howMany, std::uint8_t howOften,
std::uint8_t numberBins)
{
std::vector<DistributionPair> bins =
initializeBins(0, numberBins - 1, numberBins);
std::default_random_engine generator;
std::poisson_distribution<std::uint32_t> distribution(howOften);
for (std::uint32_t i = 0; i < howMany; i++)
{
uint32_t randomElement = distribution(generator);
binarySearchBins(bins, randomElement, 0, numberBins)->count++;
}
return bins;
}
|
