11
\$\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\$
2
  • \$\begingroup\$ Are there limits on the number of people male/female can marry? \$\endgroup\$ Commented Oct 8, 2014 at 7:18
  • \$\begingroup\$ Assuming there is an (identical) finite number of men and women, or an infinite supply thereof? \$\endgroup\$ Commented Oct 8, 2014 at 13:59

5 Answers 5

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\$
5
  • 2
    \$\begingroup\$ You mean camelCase right? //( ͡° ͜ʖ ͡°) Thank you. \$\endgroup\$ Commented Oct 8, 2014 at 17:28
  • \$\begingroup\$ Ooops, my bad :P \$\endgroup\$
    – glampert
    Commented Oct 8, 2014 at 17:29
  • \$\begingroup\$ @EngieOP, here is the link with the funny drawing, BTW: en.wikipedia.org/wiki/CamelCase \$\endgroup\$
    – glampert
    Commented Oct 8, 2014 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\$ Commented Oct 8, 2014 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\$ Commented Oct 9, 2014 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\$
4
  • \$\begingroup\$ I used std::random_shuffle() \$\endgroup\$ Commented Oct 8, 2014 at 6:41
  • 1
    \$\begingroup\$ @EngieOP: I know. std::shuffle() is different (the link shows both of those functions). \$\endgroup\$
    – Jamal
    Commented Oct 8, 2014 at 6:47
  • \$\begingroup\$ Okay. Had to look closely to see the difference. \$\endgroup\$ Commented Oct 8, 2014 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
    Commented Oct 8, 2014 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\$
0
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\$
2
  • \$\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
    Commented Oct 8, 2014 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
    Commented Oct 8, 2014 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 and acknowledge you have read our privacy policy.

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