# More efficient way of counting the number of values within an interval?

Suppose I have a text file which contains 10,000 random values between 0 and 1, and I want to count the number of values within a specific interval. An example may explain it more clearly.

Suppose my Datefile.txt contains data like:

0.0102244
0.028072
0.0144578
0.064578
0.08148
0.012749
0.12749.....and 10,000 more values


And I want to count the number of values within the interval 0.05 (i.e. it searches for the values within the range 0.0 to 0.05, then 0.05 to 0.1 and so on). For the example above, the output will be:

In range 0 to 0.05, total values 4
In range 0.05 to 0.1, total values 2
In range 0.1 to 0.15, total values 1...etc.


Here is my code:

int main(){

double area;
double a=0,b=0,c=0,d=0,e=0,f=0,g=0,h=0,i=0,k=0,l=0,m=0,n=0,o=0,p=0,q=0,r=0,s=0,t=0,u=0;

ifstream theFile ("Datafile.txt");

while(theFile >>area){

if (area<=0.05){
a++;
}

else if (area<=0.1){
b++;
}
else if (area<=0.15){
c++;
}
else if (area<=0.2){
d++;
}
else if (area<=0.25){
e++;
}
else if (area<=0.3){
f++;
}
else if (area<=0.35){
g++;
}
else if (area<=0.4){
h++;
}
else if (area<=0.45){
i++;
}
else if (area<=0.5){
k++;
}

else if (area<=0.55){
l++;
}
else if (area<=0.6){
m++;
}
else if (area<=0.65){
n++;
}
else if (area<=0.7){
o++;
}
else if (area<=0.75){
p++;
}
else if (area<=0.8){
q++;
}
else if (area<=0.85){
r++;
}
else if (area<=0.9){
s++;
}
else if (area<=0.95){
t++;
}
else if (area<=1.0){
u++;
}

}


Though my code is working fine, it might not be the most efficient way. So I put my code here for review. Can anyone suggest a better way of doing this?

Updated (based on the answer of ChrisWue)

#include <iostream>
#include <cmath>
#include <vector>
#include <fstream>

using namespace std;

int main() {

const double bucket_size = 0.05;
double area=0;
int number_of_buckets = (int)ceil(1 / bucket_size);
std::vector<int> histogram(number_of_buckets);
ifstream theFile("Datafile.txt");

while (theFile >> area) {
int bucket = (int)floor(area / bucket_size);
histogram[bucket] += 1;
}
for (auto loop = histogram.begin(); loop != histogram.end();++loop) {
cout<<bucket_size<<"\t"<<number_of_buckets<<endl;
}

return 0;
}


For the data-

0.0102244
0.028072
0.0144578
0.064578
0.08148
0.012749
0.12749.....


it gives the output like this-

0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20
0.05    20


What am I doing wrong?

• What are your single-letter variables for? It looks like they should be in an array. You also shouldn't use a single letter for any variable, unless it's a loop counter. Commented Jan 9, 2014 at 17:47
• @Jamal I used those letter to count the number of values within that range. Commented Jan 9, 2014 at 17:54
• Like I said, consider an array to hold those values. Since there are 20 variables, your array will be of that size. You could call it something like ranges. If you need more explanation, I can put this into an answer. Commented Jan 9, 2014 at 17:57
• @Jamal A little more explanation would be lovely. :) Commented Jan 9, 2014 at 18:00
• Done. I've also added an example with std::map (which may be preferred), and I'll check it in case I've made any mistakes. Commented Jan 9, 2014 at 18:24

What you want is a histogram of your values. If you want it to be flexible in the future with different bucket sizes, then you can use a std::vector and calculate how many buckets you need.

If the values are in range [0, 1] and 0 < bucket_size < 1, then the number of buckets you need obviously is ceil(1 / bucket_size).

So what I'd do would probably look something like this:

const float bucket_size = 0.05;
int number_of_buckets = (int)ceil(1 / bucket_size); // requires <cmath>
std::vector<int> histogram(number_of_buckets);

...

while (theFile >> area) {
int bucket = (int)floor(area / bucket_size);
histogram[bucket] += 1;
}


No big if-else cascade and easy to adjust for different bucket sizes.

Update:

It's been pointed out in the comments that you can get an out-of-bounds error when the value is 1.0 since it would result in bucket index 20 which is larger than the allocated vector (which goes from 0 to 19). A simple fix would be to include the upper bound into the last bucket:

int bucket = min((int)floor(area / bucket_size), number_of_buckets - 1);

• I love how this transforms the problem to something much more manageable. However as it involves reading input, I would strongly suggest putting some sort of range checks either on area or on bucket before using it to subscript histogram. I presume this was omitted for clarity of answer. :) Commented Jan 10, 2014 at 3:23
• @MichaelUrman: Yes, the code operates on the assumption stated above :). In real life you certainly need input checking. Commented Jan 10, 2014 at 3:25
• @ChrisWue This is what I was looking for. But I am having trouble using it (may be some noobie mistakes). I have updated my post and added the new code (based on your answer). Please check. Could you please help me? Commented Jan 10, 2014 at 12:56
• @aries0152: Well, that would be an off-topic question here (we only review working code) but you print out the bucket_size and the number_of_buckets which are fixed. What you need to print is: for (std::vector<int>::size_type i = 0; i < histogram.size(); ++i) { cout << (i + 1) * bucket_size << "\t" << histogram[i] << "\n"; } Commented Jan 10, 2014 at 17:56
• A small note: it's always tricky with histograms on a closed interval like [0 1] - where the upper bound will get mapped beyond the number of available buckets. In the example above, an area value of 1.0 will get mapped to bucket index 20 (1.0/.05), but you've only allocated 20 buckets (indexes 0 to 19). A common thing is just to include the upper end of the range into the last bucket... Commented Nov 20, 2020 at 1:25

Given that this is C++, you should try for a more object-oriented design. My recommendation is to create a Histogram class. The interface might look like:

class Histogram {
public:
// Pick whichever constructor feels more natural to you
Histogram(double min, double max, int numberOfBins);
Histogram(double min, double max, double binWidth);

void record(double datum);
int bins() const;                    // Get the number of bins
int count(int bin) const;            // Get the number of data points in some bin
int countLowerOutliers() const;      // Get count of values below the minimum
int countUpperOutliers() const;      // Get count of values at or above the maximum
double lowerBound(int bin) const;    // Get the inclusive lower bound of a bin
double upperBound(int bin) const;    // Get the exclusive upper bound of a bin

virtual ~Histogram();

private:
double binWidth;
int binCount;
int lowerOutlierCount, upperOutlierCount;
int counts[];
};


It should be implemented using an array.

void Histogram::record(double datum) {
int bin = (int)((datum - min) / binWidth);
if (bin < 0) {
lowerOutlierCount++;
} else if (bin >= binCount) {
upperOutlierCount++;
} else {
count[bin]++;
}
}


Then, your main() looks clean.

int main() {
Histogram histogram(0.0, 1.0, 0.05);
double area;

ifstream theFile("Datafile.txt");
while (theFile >> area) {
histogram.record(area);
}

for (int i = 0; i < histogram.bins(); ++i) {
std::cout << "In range " << histogram.lowerBound(i)
<< " to " << histogram.upperBound(i)
<< ", total values " << histogram.count(i)
<< std::endl;
}
}


In general, do not to use single letters as variable names, unless they're simple loop counters. This reveals nothing about them and will just make your code harder to understand.

In your example, it looks like you're holding the number of values at different ranges. Not only do your variables reveal nothing about this, but it's harder to read and to maintain.

Instead of this, you could use an array, if you still want to stay simple. Since there are twenty variables, your array can be of that size.

Consider something like this:

int ranges[20] = {};


Note that, in C++ (not C), this initializes each element to 0.

So, for your code, you would have this:

while (theFile >> area) {

if (area <= 0.05) {
ranges[0]++;
}

else if (area <= 0.1) {
ranges[1]++;
}

// remaining conditions...
}


Now, if you wanted to really utilize the STL, you could instead consider an std::map. This would allow you to set the different ranges as key values, along with the held quantity as mapped values.

Something like this:

std::map<float, int> ranges;


You can initialize all of the values at once (which requires C++11):

std::map<float, int> ranges = { {0.05, 0}, {0.1, 0} /* ... */ };


If you don't have C++11:

std::map<float, int> ranges;

ranges[0.05] = 0;
ranges[0.1] = 0;
// ...


Then in the loop, increment at each range as needed:

while (theFile >> area) {

if (area <= 0.05) {
ranges[0.05]++;
}

else if (area <= 0.1) {
ranges[0.1]++;
}

// remaining conditions...
}


This may look similar to the first example with the array, but it's actually different. This will create a new key value (a range) and increment its mapped value (its quantity). This does not correspond to indices associated with arrays. Although key values must be unique, the map is designed to only create new key values. If it tries to add another one, it'll ignore it. In this case, it'll just increment its count.

• The next step would then be to create a vector of upper limits for each bin and iterate over that instead of manually unrolling the loop into this endless if...else if cascade.
– amon
Commented Jan 9, 2014 at 19:00
• @amon: True. I'm showing this as an example using these loops. Feel free to add an answer about that. Commented Jan 9, 2014 at 19:06
• std::map<float, int> is setting off all sorts of alarms. Floats are not well-suited to typical equality comparisons. I think the use you show (always literals) is relatively safe, but it's not far from one that calculates the bound through some sort of rounding, and falls prey to floating point inaccuracy. Consider whether 0.1 * 3 == 0.3. Commented Jan 10, 2014 at 3:37
• @MichaelUrman: I see. Should I make any corrections here, or just remove the parts about the map? Commented Jan 10, 2014 at 3:39
• I'm not 100% sure. It's nice to get logarithmic time. Perhaps using map::lower_bound would be enough to not set off alarms, as that will at least avoid creating extra buckets. The advantage over the elegant mathematical approach is you can more easily specify non-uniform ranges. Commented Jan 10, 2014 at 4:00

#include <iostream>
#include <fstream>
main (){
ifstream file("datafile.txt");
double area;
int histogram[10][10]={};
while (file>>area){
histogram [(int)(area*10)] [((int)(area*100))%10] ++;
}
}


Much faster to write, it stores your histogram in a 2-dimensional array, you can easily edit this code to store it in whatever structure you need.

• I think this answer could be expanded, but still +1 Commented Jan 10, 2014 at 15:43
• Just check you code for area == 1.0f; the result will be wrong. Commented Aug 15 at 18:50