for looping index of arrays?

Question

I want to output my histogram using the fewest amount of for loops possible

int* histogram(int size, int* arr)
{
    int bin[10] = {};

    for (int i = 0; i < size; i++)
    {

        if (arr[i] >= 0 && arr[i] < 10)
        {
            bin[0]++;       
        }
        else if (arr[i] >= 10 && arr[i] < 20)
        {
            bin[1]++;
        }

    return bin;
}

Currently I am outputting the histogram like this:

cout << "0|";
    for (int j = 0; j < bin[0]; j++)
        cout << "*";
    cout << endl;

But this is long and annoying. Is there a way to achieve the same output in fewer for loops?

Your `histogram` function has a BUG, since it returns the address of a local variable; any access through the pointer will have UB. — Angew is no longer proud of SO, Jun 29 '17 at 07:46
@HamHat Actually you cannot do that. [See here](https://stackoverflow.com/questions/8745260/c-return-array-from-function). It is preferred to use types such as `std::array` in c++ anyways. Look at my answer. — Aldarrion, Jun 29 '17 at 09:11

score 1 · Accepted Answer · answered Jun 29 '17 at 08:44

I am going to ignore the bugs in your histogram code, as it isn't really relevant to the question of optimising histogram output. For information on the bug (returning a local variable), check out this Stack Overflow question. Also, you are missing a curly brace. Always check that your code compiles and runs in its most minimalist form before posting it.

You state that the problem is that the method you use is "long and annoying", but it isn't clear if you are referring to the design of your code or the speed at which it performs.

Performance

The fastest you can possibly read the histogram is with O(n), where n is the number of bins in the histogram. In this sense your code is about as fast as it can get without micro-optimising it.

If you include the printing out of your histogram, then you have O(n*m), where m is the average number of entries per bin.

Writing a histogram is also O(n*k), where k is the number of entries in your array, because you have to figure out which bin each value belongs in.

Design

If the problem you have is that the code is bloated and unwieldy, then use less magic numbers and add more arguments to the function, like this:

#include <iostream>

void histogram(int const size, int const * const arr, unsigned int const number_of_bins, float const bin_min, float const bin_max, int * output)
{
  float const binsize = (bin_max - bin_min)/number_of_bins;
  for (int i = 0; i < size; i++)
  {
    for(int j = 0; j < number_of_bins; ++j)
    {
      if (arr[i] >= bin_min + binsize*j && arr[i] < bin_min + binsize*(j+1))
      {
        output[j]++;
      }
    }
  }
}

int main(){
  int const number_of_bins = 10;
  float const bin_min = 0;
  float const bin_max = 100;
  int const size = 20;
  int const array[size] = {5,6,20,40,44,50,110,6,-1,51,55,56,20,50,60,80,81,0,32,3};
  int bin[number_of_bins] = {};
  histogram(size, array, number_of_bins, bin_min, bin_max, bin);
  for(int i = 0; i < number_of_bins; ++i)
  {
    std::cout << i << "|";
    for (int j = 0; j < bin[i]; j++)
    {
      std::cout << "*";
    }
    std::cout << std::endl;
  }
}

Compiled with:

g++ main.cc -o Output

Output:

0|*****
1|
2|**
3|*
4|**
5|*****
6|*
7|
8|**
9|

(Bonus, your bugs are fixed)

I will just add that my answer is more aimed at C code than C++. I didn't notice the tag in the question and the code was written as if it was for C. For C++ better look at Aldarrion's answer. — Phillip Hamnett, Jun 29 '17 at 09:25

Aldarrion · Answer 2 · 2017-06-29T10:12:10.850

First of all your program is incorrect since, as pointed out, you return a pointer to a local variable form a function. To correct this you should use either std::array<Type, Size> or std::vector<Type>.

Regarding your question if you want short and compact code try this:

#include <string>
#include <algorithm>
#include <iostream>
#include <array>

std::array<int, 10> bin;

// Fill your array here

int i = 0;
std::for_each(bin.begin(), bin.end(), [&i](auto x) 
{ 
    std::cout << i++ << "|" << std::string(x, '*') << std::endl;
});

This code takes advantage of fill constructor of std::string which avoids your for cycle. But since you want to iterate through the array you need to do it in one way or the other. Either by an explicit for or by calling another function.

Note: this code is less efficient than a standard for loop but your question is how to avoid these.

for looping index of arrays?

2 Answers2

Performance

Design