10
\$\begingroup\$

The following is a problem I found on this wiki. What can I do to optimize my algorithm, and make this code more C++11?

Write a program to discover the answer to this puzzle:"Let's say men and women are paid equally (from the same uniform distribution). If women date randomly and marry the first man with a higher salary, what fraction of the population will get married?"

#include <iostream>
#include <algorithm>
#include <vector>
#include <ctime>
//#include <cstdlib>

using std::cin;
using std::cout;
using std::endl;
using std::random_shuffle;


const int MIN = 1;
const int MAX = 1000000;
const int MALES = 100;
const int FEMALES = 100;

class Female{
public:
    Female(){isMarried = false;}

    bool isMarried;
    int salary;
};

class Male{
public:
    Male(){isMarried = false;}

    bool isMarried;
    int salary;
};

void marriageTest(std::vector<double> &results){

    double count = 0;
    bool done = false;

    Male male[MALES];
    Female female[FEMALES];

    //Fill array of Females and Males with random salaries ranging from 1 to 10
    for(int i=0; i<100; i++){
        int output = MIN + (rand() % (int)(MAX - MIN + 1));
        i[male].salary = output; //( ͡° ͜ʖ ͡°)
    }
    for(int i=0; i<100; i++){
        int output = MIN + (rand() % (int)(MAX - MIN + 1));
        i[female].salary = output;
    }


    //Start dating
    //Keep dating until the maximum salary of males is lower than minimum salary of females

    do{
        random_shuffle(&male[0], &male[MALES]);               //Shuffle array of males
        random_shuffle(&female[0], &female[FEMALES]);           //Shuffle array of females


        for(int i=0; i<100; i++){                              //Compare a female and male from both arrays
            if(female[i].salary < male[i].salary)
                if(!female[i].isMarried && !male[i].isMarried){
                    count++;
                    female[i].isMarried = true;
                    male[i].isMarried = true;
                }
        }

        //Check for Maximum Male Salary
        int maxMen = MIN;
        for(int i=0; i<100; i++){
            if(male[i].salary > maxMen && !male[i].isMarried)
                maxMen = male[i].salary;
        }

        //Check for Minimum Female Salary
        int minWomen = MAX;
        for(int i=0; i<100; i++){
            if(female[i].salary < minWomen && !female[i].isMarried)
                minWomen = female[i].salary;
        }

        if(maxMen <= minWomen)
            done = true;


    }while(!done);

    results.push_back(count/100);
}

void runTrials(int num_trials, std::vector<double> &results){

    for(int i=0; i<num_trials;i++)
        marriageTest(results);
}

double Percentage(std::vector<double> &results){

    double final = 0;
    int trials = 0;
    for(auto i : results){
        final += i;
        ++trials;
    }

    return final/trials;
}


int main()
{
    int num_trials;
    std::vector<double> results;

    srand(time(NULL));

    cout << "Number of trials: ";
    cin >> num_trials;

    runTrials(num_trials,results);

    double final = Percentage(results);

    cout << "Percentage: " << final << endl;

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ Are there limits on the number of people male/female can marry? \$\endgroup\$ – Martin York Oct 8 '14 at 7:18
  • \$\begingroup\$ Assuming there is an (identical) finite number of men and women, or an infinite supply thereof? \$\endgroup\$ – Laurent LA RIZZA Oct 8 '14 at 13:59
5
\$\begingroup\$

There are several changes you can apply to add more C++11 features and practices to your code. To name a few:

  1. Use constexpr for constants.

  2. Use std::shuffle instead of std::random_shuffle. The random_shuffle overload that uses a default RNG is considered deprecated.

  3. Use std::array instead of C arrays (for male[] and female[]).

  4. Use the new <random> library instead of std::rand().

  5. Don't use C-style casts: (int)(MAX - MIN + 1). static_cast is the correct in way here.

Other things:

  1. Initialize data in constructors the proper way: Female() : isMarried(false) { }

  2. i[male] reversed indexing, seriously? Save that for the code obfuscation competitions.

  3. Replace magic constants (100) with a named constant that describes its meaning.

  4. //( ͡° ͜ʖ ͡°) I too like ASCII-art, but that adds nothing to the documentation of the code.

  5. You have one or two inconsistencies with naming. Most of the code used camelCase for variables and functions, but you have a num_trials variable and a Percentage() function that break that pattern.

\$\endgroup\$
  • 2
    \$\begingroup\$ You mean camelCase right? //( ͡° ͜ʖ ͡°) Thank you. \$\endgroup\$ – Quaxton Hale Oct 8 '14 at 17:28
  • \$\begingroup\$ Ooops, my bad :P \$\endgroup\$ – glampert Oct 8 '14 at 17:29
  • \$\begingroup\$ @EngieOP, here is the link with the funny drawing, BTW: en.wikipedia.org/wiki/CamelCase \$\endgroup\$ – glampert Oct 8 '14 at 17:30
  • \$\begingroup\$ I know what CamelCase is :). I just didn't care when I was coding this, because I didn't think I was going to show anyone. :P \$\endgroup\$ – Quaxton Hale Oct 8 '14 at 17:36
  • 1
    \$\begingroup\$ If you use std::array, use .size() for the iteration limits. If you use <random>, especially a uniform_int distribution, you won't need the casts anymore. \$\endgroup\$ – Laurent LA RIZZA Oct 9 '14 at 6:35
8
\$\begingroup\$
  • There doesn't seem to be a need for separate Male and Female structures as they hold the same exact data. Instead, just have one named Person and create male and female instances of it.

    You also don't need classes if you're not going to have any private data; just use structs.

    struct Person
    {
        bool isMarried;
        int salary;
    
        Person() : isMarried(false) {}
    };
    

    Person males[MALES];
    Person females[FEMALES];
    
  • Regarding the use of C++11, you can start by removing both std::srand() and std::rand() and replacing them with functionality from the <random> library, particularly std::shuffle().

\$\endgroup\$
  • \$\begingroup\$ I used std::random_shuffle() \$\endgroup\$ – Quaxton Hale Oct 8 '14 at 6:41
  • 1
    \$\begingroup\$ @EngieOP: I know. std::shuffle() is different (the link shows both of those functions). \$\endgroup\$ – Jamal Oct 8 '14 at 6:47
  • \$\begingroup\$ Okay. Had to look closely to see the difference. \$\endgroup\$ – Quaxton Hale Oct 8 '14 at 6:51
  • 1
    \$\begingroup\$ @EngieOP The difference will be more clear in a near future when your compiler will excplicitly tell "this function is deprecated, use std::shuffle instead" :) \$\endgroup\$ – Morwenn Oct 8 '14 at 8:55
7
\$\begingroup\$

When you fill male[] and female[]:

//Fill array of Females and Males with random salaries ranging from 1 to 10
for(int i=0; i<100; i++){
    int output = MIN + (rand() % (int)(MAX - MIN + 1));
    i[male].salary = output; //( ͡° ͜ʖ ͡°)
}
for(int i=0; i<100; i++){
    int output = MIN + (rand() % (int)(MAX - MIN + 1));
    i[female].salary = output;
}

Some issues / strangeness:

  • The comment is misleading, should be salaries ranging from MIN to MAX
  • Replace the hardcoded 100 in the loop condition with the MALES and FEMALES you defined
  • Why i[male] instead of male[i] ?
  • Why the poorly named output variable? Just assign directly

marriageTest is doing a bit too much, it would be better to split the initialization and the dating parts to different functions.

The program outputs "Percentage" that's not actually percentage:

Percentage: 0.6828

I think you want to multiply this by 100 (and maybe stick a % at the end)

\$\endgroup\$
2
\$\begingroup\$
  • A No Raw Loops mantra: calculating maxMan and minWomen should be factored out in a (possibly templated) function. Same goes for initialization of salaries. The match-finding loop is really std::find.

  • Shuffling both arrays seems like doing extra work. I don't see how shuffling just men and inspecting women sequentially would change the result.

  • There's no reason for an isMarried property: std::erase a couple once they are matched (yes you'd need std::vectors instead of arrays).

\$\endgroup\$
  • \$\begingroup\$ Actually, since the arrays were randomly generated in the first place, you don't need to shuffle any of them, do you? \$\endgroup\$ – CompuChip Oct 8 '14 at 8:56
  • \$\begingroup\$ @CompuChip: That I am not sure. Not shuffling at all imposes some correlation. Should you prove me wrong I'd be glad to accept. \$\endgroup\$ – vnp Oct 8 '14 at 9:01
0
\$\begingroup\$

Your Percentage function could be improved. The first observation is that it is unnecessary to accumulate the number of trials, since this is already stored in the std::vector (the postcondition guarantees trials == results.size()). Moreover, I would avoid the raw loop here like so:

double percentage(const std::vector<double>& results)
{
    return std::accumulate(results.cbegin(), results.cend(), 0.0) / results.size();
}

Readability is improved a lot as well. In marriageTest, you might as well do emplace_back instead of push_back. In general, I think it's a good idea not to use push_back unless you have a specific reason. For more on the topic, see e.g. here.

\$\endgroup\$

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.