C++ - Secretary Problem using dynamic programming

Question

I tried using dynamic programming to get a solution to the Secretary Problem. It seems to me it's working with with expected result. I really didn't want to use std::vector and things like that, because I wanted to learn about C-style arrays. Things I want to know:

• if there is any problem with the code
• commenting
• readability
• use of C-style array
• constants
• splitting code into functions
• performance

---

#include <iostream>
#include <cstdlib>

const unsigned int SEED = 42;              // seed for srand()
const unsigned int SEQUENCE_LENGTH = 100;  // participants count
const unsigned int CYCLES_COUNT = 1000000; // simulation cycles

void prime_sequence(unsigned int *data)
{
    // fill data with values 0 to SEQUENCE_LENGTH-1 in
    for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
    {
        data[i] = i;
    }
}

void generate_sequence(unsigned int *data)
{
    // generate random sequence using Fisher–Yates shuffle
    for (unsigned int i = SEQUENCE_LENGTH; i > 0; i--)
    {
        unsigned int position = rand() % i;
        if ((i - 1) != position)
        {
            unsigned int temp = data[i - 1];
            data[i - 1] = data[position];
            data[position] = temp;
        }
    }
}

void simulate(unsigned int *data, unsigned int *max_history, unsigned int *cum_history)
{
    unsigned int rejected_max = 0;
    for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
    {
        // reject choices up to i
        if (data[i] > rejected_max)
        {
            // maximum of rejected choices
            rejected_max = data[i];
        }
        for (unsigned int j = i + 1; j < SEQUENCE_LENGTH; j++)
        {
            // continue evaluvating choices and choosing first one that higher than rejected max
            if (data[j] > rejected_max)
            {
                if (data[j] == SEQUENCE_LENGTH - 1)
                {
                    // record only if chosen is best option
                    max_history[i] += 1;
                }
                // record chosen with its own weight
                cum_history[i] += data[j];
                break;
            }
        }
    }
}

int main()
{
    srand(SEED);
    unsigned int data[SEQUENCE_LENGTH] = {0};
    unsigned int max_history[SEQUENCE_LENGTH] = {0};
    unsigned int cum_history[SEQUENCE_LENGTH] = {0};
    prime_sequence(data);

    for (unsigned int i = 0; i < CYCLES_COUNT; i++)
    {
        // simulation
        generate_sequence(data);
        simulate(data, max_history, cum_history);
    }

    unsigned int cum_sum = 0;
    unsigned int max_sum = 0;
    for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
    {
        // sum history enteries
        cum_sum += cum_history[i];
        max_sum += max_history[i];
    }

    for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
    {
        printf("at [%i] max: %.4f cum: %.4f\n", i, max_history[i] / (double)max_sum * 100, cum_history[i] / (double)cum_sum * 100);
    }
    std::cout << "max_sum: " << max_sum << " cum_sum: " << cum_sum << std::endl;
    return 0;
}

Answer 1

Overview

About your use of C-arrays: you need to justify this. Sure using them to learn is fine, but here you are not really using them in that way.

In C++ we tend to write algorithms in terms of iterators. This allows us abstract away the actual storage that is used. You can use C-arrays, std::vector or anything else when you use iterators.

You should learn the standard library a bit more. Several of your functions can be replaced with an algorithm from the standard library.

Code Review

Don't use ALL_CAPS for variables. This is (by tradition) reserved for macros. You definitely don't want to clash with macros as they don't follow any scoping rules.

const unsigned int SEED = 42;              // seed for srand()

I would also use constexpr rather than const.

Don't write comments that are explained by the code. The code explains what, comments should explain why.

If you fall into the trap of explaining what in comments the your code will eventually suffer from comment rot. This is where the comments and the code are different (as the comments are not checked by the compiler). Then the engineer that maintains your code will have to work out which is correct. Is it the comments or the code? You don't want that to happen. You want the code to prove it is correct (via tests).

---

Here in C++ I would have used iterators:

void prime_sequence(unsigned int *data)

// --

template<typename I>
void prime_sequence(I begin, I end)

If you are not sure what iterators are then think of pointers (they don't have to be pointers but that is an easy way to visualize them for a beginner). The begin points at the first element in the container, and the end points one past the end of the container.

So you can loop like this:

 for (I loop = begin; loop != end; ++loop) {
      // Do Stuff
      auto const& val = *loop; // read the value.
      (*loop)         = XXX;   // write the value.
 }

Also this function can be replaced by a one line expression by using std::generate() or std::iota

void prime_sequence(unsigned int *data)
{
    // fill data with values 0 to SEQUENCE_LENGTH-1 in
    for (unsigned int i = 0; i < SEQUENCE_LENGTH; i++)
    {
        data[i] = i;
    }
}

// ----

std::generate(begin, end, [t = 0]() mutable {return t++;}); // requires C++14 or up
// or a better solution suggested by @Rish
std::iota(begin, end, 0);

---

Same again. But this is replaceable with std::shuffle():

void generate_sequence(unsigned int *data)
{
    // generate random sequence using Fisher–Yates shuffle
    for (unsigned int i = SEQUENCE_LENGTH; i > 0; i--)
    {
        unsigned int position = rand() % i;
        if ((i - 1) != position)
        {
            unsigned int temp = data[i - 1];
            data[i - 1] = data[position];
            data[position] = temp;
        }
    }
}

---

Here I would use three pairs of iterators:

void simulate(unsigned int *data, unsigned int *max_history, unsigned int *cum_history)


// ---

template<typename ID, typename IM, typename IC>
void simulate(ID beginData, ID endData, 
              IM beginMax,  IM endMax,
              IC beginCum,  IC endCum)

---

int main()
{

    // OK so you don't want random numbers.
    // Which is fine. But basically this means
    // you get exactly the same results from rand()
    // everytime you run this application.
    srand(SEED);



    // Sure arrays in C.
    // When you talk about arrays in C most people think about
    // dynamically allocated arrays. But these are fine.
    unsigned int data[SEQUENCE_LENGTH] = {0};


    // What I would note is that there is a limit to
    // SEQUENCE_LENGTH before it becomes to large.
    // So in this situation `std::vector` is superior as this
    // limit is much larger.
    // https://stackoverflow.com/a/216731/14065
    unsigned int max_history[SEQUENCE_LENGTH] = {0};





    // Fine:
    prime_sequence(data);
    // using the template version would be:
    prime_sequence(data, data + SEQUENCE_LENGTH);
    // Though I would use:
    prime_sequence(std::begin(data), std::end(data));



    // Don't use `std::endl`.
    // It forces a flush when it is not needed.
    // Simply use `"\n"`.
    std::cout << "max_sum: " << max_sum << " cum_sum: " << cum_sum << std::endl;


    // No point.
    // If your application can only return `0` then
    // not having a value is an indication that your application will
    // never fail.
    return 0;
}

Answer 2

Minus the call to std::cout, you have a program that is all C. So why not use C and a C compiler instead of running almost C code under a C++ compiler?

---

Martin suggests using constexpr instead of const. Note that you can also do that in C2X. (constexpr can not - yet - be used for functions in C.)

---

As you're already including <cstdlib>, return EXIT_SUCCESS instead of 0. Or elide it altogether in C++.

---

In simulate, data is not modified anywhere. So it should be declared with the const qualifier. In C, the compiler might be able to do more optimizations if you use restrict for the parameters.

---

std::endl flushes the underlying buffer after printing a newline. You do not require that. Replace it with a \n.

---

In main(), "enteries" should be "entries".