8
\$\begingroup\$

I recently reviewed a question here on Code Review. The problem statement is

Write a program that prompts the user to input ten values between 80 and 85 and stores them in an array. Your program must be able to count the frequency of each value appears in the array.

I coded my own solution for the problem statement. My questions are
- Can this be optimized more?
- Did I miss anything in C++14 or C++17 that might improve the code?
- Is the code readable?
- Are the variable and function names good or can they be improved?

My goals were to write the best C++ I could, remove any magic numbers and allow the solution to scale for different sets of numbers.

#include "pch.h"
#include <iostream>
#include <array>

const size_t INPUTSIZE = 10;
const size_t FREQUENCYSIZE = 6;
const int MINLEGALVALUE = 80;
const int MAXLEGALVALUE = 85;

std::array<int, INPUTSIZE> getUserInput()
{
    std::array<int, INPUTSIZE> inputValues;

    size_t i = 0;
    do
    {
        int inputValue = 0;
        std::cout << "Please enter a number between " << MINLEGALVALUE << " and " << MAXLEGALVALUE  << ":" ;
        std::cin >> inputValue;

        if (inputValue >= MINLEGALVALUE && inputValue <= MAXLEGALVALUE)
        {
            inputValues[i] = inputValue;
            i++;
        }
        else
        {
            std::cout << "The number must be between" << MINLEGALVALUE << " and " << MAXLEGALVALUE << "\n";
        }

    } while (i < INPUTSIZE);

    return inputValues;
}

std::array<unsigned, FREQUENCYSIZE> getFrequencyCounts(std::array<int, INPUTSIZE> inputValues)
{
    std::array<unsigned, FREQUENCYSIZE> freqs = { 0 };

    for (auto inputs : inputValues)
    {
        freqs[inputs - MINLEGALVALUE]++;
    }

    return freqs;
}

void printFrequencies(std::array<unsigned, FREQUENCYSIZE> freqs)
{
    unsigned rowLabel = MINLEGALVALUE;
    for (auto frequency : freqs)
    {
        std::cout << rowLabel << "      " << frequency << "\n";
        rowLabel++;
    }
}

int main()
{
    std::array<int, INPUTSIZE> inputValues = getUserInput();
    std::array<unsigned, FREQUENCYSIZE> freqs = getFrequencyCounts(inputValues);

    std::cout << "\n";

    printFrequencies(freqs);
}
\$\endgroup\$
  • 2
    \$\begingroup\$ You've asked for optimizations, but the input size is too small for the usual histogramming optimizations to matter, and anyway the program spends all of its time doing IO. Do you want to know about them anyway? \$\endgroup\$ – harold Aug 19 at 19:56
  • 1
    \$\begingroup\$ Can this be optimized more? The answer is basically always "yes". :P The real questions are "how", "how much", and go on from there into what speed vs. machine-code size footprint tradeoff you want to hit, and details about which inputs to optimize for (worst case vs. best case vs. average). (And of course for which ISA). Also optimizing for latency vs. throughput on an out-of-order execution CPU if the problem is small enough. \$\endgroup\$ – Peter Cordes Aug 20 at 11:13
  • \$\begingroup\$ @PeterCordes You're right, I should have specified speed vs. size. I generally look for speed optimizations and accept the memory size trade off. \$\endgroup\$ – pacmaninbw Aug 20 at 11:19
  • \$\begingroup\$ Sometimes you can shrink code-size without hurting speed. And for performance as a small part of a large program, smaller L1i cache footprint is an advantage. So sometimes the best thing for overall speed is to put some effort into code-size. (Often not, though, if there's anything you can usefully do with SIMD. But for histograms there isn't much until AVX512 scatter/gather + conflict-detection on x86, and even then it's not always worth it, and certainly not for a small problem size like 10 elements, not even one full vector of 32-bit counters.) \$\endgroup\$ – Peter Cordes Aug 20 at 14:22
9
\$\begingroup\$

Names

All-caps names are typically reserved for macros. They don't seem to me to make much sense for const variables. In fact, they only make minimal sense for object-like macros--they were originally used for function-like macros as kind of a warning that you should be cautious about passing an argument with side-effects, because they might happen more than once.

Minimize Magic

I'd typically try to keep the magic numbers to a minimum. For example, instead of defining FREQUENCYSIZE by itself, I'd probably do something like this:

const int lower_bound = 80;
count int upper_bound = 85;
const int frequency_size = upper_bound - lower_bound + 1;

Separation of Concerns

I'd at least consider separating validating data from reading the data. I'd prefer to have a function on the general order of:

bool valid(int val) { 
    return val >= lower_bound && val < upper_bound;
}

Class Usage

We have a number of different things related to reading and working with numbers in a specified range. It might be worth considering wrapping those bits and pieces into a coherent class for dealing with a value in a range, and let the outside world create and use objects of that class.

template <class T, T lower_bound, T upper_bound>
class bounded {
public:
    static bool valid(T val) { return val >= lower_bound && val < upper_bound; }

    friend std::istream &operator>>(std::istream &is, bounded &b) { 
        T val;
        is >> val;
        if (valid(val)) 
            b.val = val;
        else
            is.setstate(std::ios_base::failbit);
        return is;
    }

    friend std::ostream &operator<<(std::ostream &os, bounded const &b) {
        return os << b.val;
    }

    size_t index() { return size_t(val - lower_bound); }

    static constexpr size_t range() { return upper_bound - lower_bound + 1; }

private:
    T val;
};

That let's us simplify the rest of the code a bit, something on this general order:

int main() {
    using integer = bounded<int, 80, 85>;

    std::array<integer, 10> inputs;
    std::array<size_t, integer::range()> freqs {};

    for (integer &i : inputs) {
        std::cin >> i;
        ++freqs[i.index()];
    }

    for (auto freq : freqs)
        std::cout << freq << "\n";
}

Technically, this doesn't meet the requirements as-is (e.g., it doesn't print out a prompt to tell the user to enter data), but I think it gives at least some idea of a direction things could go.

\$\endgroup\$
4
\$\begingroup\$

If you go for modern C++ the static variables should be marked as constexpr instead of plain old const.

As was said in the other question, it should be beneficial to create an array of length MAXLEGALVALUE - MINLEGALVALUE and directly index into that array. That way there is probably less memory consumed and we count automatically.

Personally I would use std::size_t or a well specified integer type like std::uint32_t rather than unsigned, which depends on the implementation.

In range based for loops where the type is unambiguous I am not really a fan of auto.

for (auto inputs : inputValues)

How do you know that copying it is cheap here? You have to check the type of the container. Also you should consider const correctness so rather use const int or const auto if you prefere that.

for (const int inputs : inputValues)

Note that you have a truncation warning here as MINLEGALVALUE is of type int:

unsigned rowLabel = MINLEGALVALUE;
\$\endgroup\$
  • \$\begingroup\$ unsigned is actually a reasonable choice: the max count you might need to hold depends on how big your input array is. int / unsigned int are normally one of the fastest integer types that the machine can handle efficiently, unless it's an 8-bit implementation where unsigned char would be even faster. Obviously with a huge array of the same value repeated, with more than UINT_MAX entries, you could wrap around, but the OP is aiming for portable performance. Apparently even if that means a tradeoff in wrapping around in weird edge-case inputs (huge and unevenly distributed). \$\endgroup\$ – Peter Cordes Aug 20 at 11:22
1
\$\begingroup\$

One idea for simplification is to count frequencies directly instead of putting all the values in an array that you only use for counting frequencies. You can then remove the getFrequencyCounts function and the whole thing gets a little more efficient. This works well when you have a set of values in a dense range like [80,85]. If you have a lot of values far between eachother, using a set or unordered_set is probably a better choice. I found the code easy enough to read. Here are some ideas with comments in the code:

#include <array>
#include <iostream>

constexpr size_t INPUTSIZE = 10;
constexpr int MINLEGALVALUE = 80;
constexpr int MAXLEGALVALUE = 85;
constexpr size_t FREQUENCYSIZE = MAXLEGALVALUE - MINLEGALVALUE + 1;

std::array<unsigned, FREQUENCYSIZE> getUserInputFreq() {
    std::array<unsigned, FREQUENCYSIZE> inputValues{0}; // initialize with 0

    size_t i = 0;
    do {
        int inputValue = 0;
        std::cout << "Please enter a number between " << MINLEGALVALUE << " and "
                  << MAXLEGALVALUE << ":";

        // make sure the istream you read from succeeded in extracting
        if(std::cin >> inputValue) {
            if(inputValue >= MINLEGALVALUE && inputValue <= MAXLEGALVALUE) {
                // count frequencies directly if you don't actually need the
                // input values
                ++inputValues[static_cast<size_t>(inputValue - MINLEGALVALUE)];
                ++i; // prefer prefix operator++
            } else {
                std::cout << "The number must be between" << MINLEGALVALUE << " and "
                          << MAXLEGALVALUE << "\n";
            }
        } else     
            break; // erroneous input or EOF

    } while(i < INPUTSIZE);

    return inputValues;
}

void printFrequencies(std::array<unsigned, FREQUENCYSIZE> freqs) {
    int rowLabel = MINLEGALVALUE;
    for(auto frequency : freqs) {
        std::cout << rowLabel << "      " << frequency << "\n";
        ++rowLabel; // prefer prefix operator++
    }
}

int main() {
    std::array<unsigned, FREQUENCYSIZE> freqs = getUserInputFreq();

    std::cout << "\n";

    printFrequencies(freqs);
}
\$\endgroup\$
  • \$\begingroup\$ Yes counting on the fly as you read data can be good (hiding store-forwarding latency for a run of the same number), but now you're hard-coding reading it from std::cin. That's even less generic. Plus, I think the OP was just using GetInput as part of the caller for the histogram function to make a complete example. Anyway, you could take an InputIterator as a function arg or something like that to let the caller specify where the input comes from. \$\endgroup\$ – Peter Cordes Aug 20 at 11:29
  • \$\begingroup\$ @PeterCordes "now you're hard-coding reading it from std::cin" - That part was actually not changed from OP's implementation. I only changed the function name from getUserInput to getUserInputFreq and continued to use std::cin since the whole thing looked pretty focused on user interaction. \$\endgroup\$ – Ted Lyngmo Aug 20 at 12:06
  • \$\begingroup\$ The original had one function that reads input, and a separate function that histogrammed a container (with an unfortunate hard-coding of the type). You're making it worse, not better, for separability / reusability. After inlining + optimization of an iterator, you can still have basically the same machine code you could get from your function, but with clean source. \$\endgroup\$ – Peter Cordes Aug 20 at 13:05
  • \$\begingroup\$ @PeterCordes "The original had one function that reads input" - yes, from std::cin, with a prompt-like text. What I did was to reduce the number of steps and also to add status checking where appropriate. The only thing not saved is the order in which the numbers were entered. The original post didn't show any demand for it. if I were to make a generic input function, I'd make it read from a std::istream& but that didn't seem worth the effort since the whole getUserInput function has focus on input from a user. \$\endgroup\$ – Ted Lyngmo Aug 20 at 13:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.