# 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. – Jamal Jan 9 '14 at 17:47
@Jamal I used those letter to count the number of values within that range. – aries0152 Jan 9 '14 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. – Jamal Jan 9 '14 at 17:57
@Jamal A little more explanation would be lovely. :) – aries0152 Jan 9 '14 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. – Jamal Jan 9 '14 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.

-
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. :) – Michael Urman Jan 10 '14 at 3:23
@MichaelUrman: Yes, the code operates on the assumption stated above :). In real life you certainly need input checking. – ChrisWue Jan 10 '14 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? – aries0152 Jan 10 '14 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"; } – ChrisWue Jan 10 '14 at 17:56
@ChrisWue Thanks a lot. It really helps :) – aries0152 Jan 11 '14 at 2:53

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.

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 Jan 9 '14 at 19:00
@amon: True. I'm showing this as an example using these loops. Feel free to add an answer about that. – Jamal Jan 9 '14 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. – Michael Urman Jan 10 '14 at 3:37
@MichaelUrman: I see. Should I make any corrections here, or just remove the parts about the map? – Jamal Jan 10 '14 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. – Michael Urman Jan 10 '14 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 – Malachi Jan 10 '14 at 15:43