7
\$\begingroup\$

I have written a simulation in order to solve the 280th problem in Project Euler, and the simulation basically repeat the given experiment 5m times, and for each experiment, writes the ExpNo - #ofSteps - ThePath to a *.txt files, and as you can guess, the process take lots of time and resources.

Ants and seeds

Problem 280

A laborious ant walks randomly on a 5x5 grid. The walk starts from the central square. At each step, the ant moves to an adjacent square at random, without leaving the grid; thus there are 2, 3 or 4 possible moves at each step depending on the ant's position.

At the start of the walk, a seed is placed on each square of the lower row. When the ant isn't carying a seed and reaches a square of the lower row containing a seed, it will start to carry the seed. The ant will drop the seed on the first empty square of the upper row it eventually reaches.

What's the expected number of steps until all seeds have been dropped in the top row?

Give your answer rounded to 6 decimal places.

My question is that how can we improve the performance of the following simulation, and save memory and maybe handle the data in a more efficient way.

I should probably point out that the reason why I also save the path that the ant takes in each experiment is that we don't want to count the same path as twice, so to check this, we output the paths, and then by using octave, we compare those path with the other paths, and if any matching occurs, we delete the output of that experiment.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <chrono>
#include <vector>
#include <iostream>
#include <sys/time.h>
#define RAND_MAX 5

/*
    1
2       3
    4
*/

int grid[5][5] = {
    {0, 0, 0, 0, 2},
    {0, 0, 0, 0, 2},
    {0, 0, 0, 0, 2},
    {0, 0, 0, 0, 2},
    {0, 0, 0, 0, 2}
};

int InitPos[2] = {2, 2};

int MaxExp = 5000000;

bool Success = false;
int StepCount = 0;
int ExpNumber = 1;
int AntsBag = 0;
void Init();
void CarryFood(int * pos);
void LeftFood(int * pos);
bool checkMovability(int * pos, int direction);
bool moveToDirection(int pos[2], int direction);
bool checkSuccess();
void ShowResult(std::vector <int> &l_path);


FILE * file = fopen("FinalDataUnsig.txt", "a+");

int main(int argc, char const *argv[])
{       
    time_t t;
    srand((unsigned)time(&t));
    fprintf(file, "%%Total Experiment Number : %d.  Exp Number-Step Count-Path\n", MaxExp);
    while(ExpNumber <= MaxExp)
    {
        Init();
        std::vector <int> path;
        int pos[2];
        pos[0] = InitPos[0];
        pos[1] = InitPos[1];
        do{
            int direction = (rand() % 4) + 1;
            if (moveToDirection(pos, direction))
            {
                StepCount++;
                path.push_back(direction);  
            }
            if (pos[1] == 4&&grid[pos[0]][4]==2&&AntsBag==0)
            {
                CarryFood(pos);
            }
            if (pos[1] == 0&&grid[pos[0]][0]==0&&AntsBag==2)
            {
                LeftFood(pos);
            }
            checkSuccess();
        }
        while(!Success);

        ShowResult(path);
        ExpNumber++;
    }   
    fclose(file);
    return 0;
}

void Init()
{
    Success = false;
    StepCount = 0;
    AntsBag = 0;
    int gridInit[5][5] = {
        {0, 0, 0, 0, 2},
        {0, 0, 0, 0, 2},
        {0, 0, 0, 0, 2},
        {0, 0, 0, 0, 2},
        {0, 0, 0, 0, 2}
    };
    for (int i = 0; i < 5; ++i)
    {
        for (int j = 0; j < 5; ++j)
        {
            grid[i][j] = gridInit[i][j];
        }
    }
}

void ShowResult(std::vector <int> &l_path)
{   
    fprintf(file, "%d %d ", ExpNumber, StepCount);
    if (file != NULL)
    {
        for (std::vector<int>::iterator it = l_path.begin(); it != l_path.end(); it++)
        {
            fprintf(file, "%d", *it);
        }
    }
    fprintf(file, "\n");
}

void CarryFood(int * pos)
{
    if (pos[1] == 4&&grid[pos[0]][4]==2&&AntsBag==0)
    {
        AntsBag = 2;
        grid[pos[0]][4] = 0;
    }
}

void LeftFood(int * pos)
{
    if (pos[1] == 0&&grid[pos[0]][0]==0&&AntsBag==2)
    {
        AntsBag = 0;
        grid[pos[0]][0] = 2;
    }
}

bool checkMovability(int * pos, int direction)
{
    switch(direction)
    {
        case 1:
        {
            if(pos[1]==0){
                return false;
            }
            break;
        }
        case 2:
        {
            if (pos[0]==0)
            {
                return false;
            }
            break;
        }
        case 3:
        {
            if (pos[0]==4)
            {
                return false;
            }
            break;
        }
        case 4:
        {
            if (pos[1]==4)
            {
                return false;
            }
            break;
        }
        default:
        {
            printf("Wrong direction input is given!!\n");
            return false;
            break;
        }
    }
    return true;

}

bool moveToDirection(int * pos, int direction)
{
    if ( !checkMovability(pos, direction) )
    {
        return false;
    }

    switch(direction){
        case 1:
        {
            pos[1] -= 1;
            break;
        }
        case 2:
        {
            pos[0] -= 1;
            break;
        }
        case 3:
        {
            pos[0] += 1;
            break;
        }
        case 4:
        {
            pos[1] += 1;
            break;
        }
        default:
        {
            printf("I'm stunned!\n");
            return false;
            break;
        }
    }
    return true;
}

bool checkSuccess()
{
    for (int i = 0; i < 5; ++i)
    {
        if (grid[i][0] != 2)
        {
            return false;
        }
    }
    Success = true;
    return true;
}

Note: And suggestion about the code quality is appreciated.

As for the curious readers, we process the output data with octave.

\$\endgroup\$
5
\$\begingroup\$

I see a number of things that can help you improve your code. I'll start with the more superficial items and end with the items that specifically address performance.

Avoid redefining standard macros

The RAND_MAX that is defined in this code actually redefines the standard RAND_MAX that's defined in <stdlib.h>. There's no reason this code should redefine that and very good reason to avoid doing so.

Write idiomatic C++

The code includes <stdio.h>, <stdlib.h>, etc. which are all C include files. Additionally, the code is written in a purely procedural style that is more C-like than C++-like. I'd recommend altering the style to use more C++ features, as the following suggestions will detail.

Eliminate global variables where practical

Having routines dependent on global variables makes it that much more difficult to understand the logic and introduces many opportunities for error. Eliminating global variables where practical is always a good idea. For global variables such as grid, consider wrapping them in objects to simplify the code.

Use constexpr where appropriate

A number of the defined variables, such as InitPos and MaxExp could and should be static constexpr instead of plain global variables. Making this change will lead to cleaner, more understandable code and may also give the compiler sufficient hints to allow it to produce better, smaller, faster code.

Eliminate unused variables

The signature for main is int main(int, char *[]) and not int main(int, char const *[]), but really, since neither argc nor argv are used in this code, it would be better to omit them both:

int main() 

Use iostream instead of FILE

There's no need to use the old FILE structures from C when we have the much nicer std::ofstream in C++. Here's one way to do that:

std::ofstream out{"FinalDataUnsig.txt", std::ios::app};
out << "%%Total Experiment Number : " << MaxExp << ".  Exp Number-Step Count-Path\n";

Of course, the ShowResult() routine would also have to be similarly altered. One way to do that:

void ShowResult(std::vector <int> &l_path, std::ostream &out)
{   
    if (!out) 
    {
        return;
    }
    out << ExpNumber << ' ' << StepCount << ' ';
    for (std::vector<int>::iterator it = l_path.begin(); it != l_path.end(); it++)
    {
        out << *it;
    }
    out << '\n';
}

Use "range for" and simplify your code

Here is an alternative implementation of the modified ShowResult above:

void ShowResult(const std::vector <int> &l_path, std::ostream &out)
{   
    if (!out) {
        return;
    }
    out << ExpNumber << ' ' << StepCount << ' ';
    for (const auto &step : l_path) {
        out << step;
    }
    out << '\n';
}

Eliminate "magic numbers"

This code has a number of inscrutable "magic numbers," that is, unnamed constants such as 0, 2, etc. Generally it's better to avoid that and give such constants meaningful names. That way, if anything ever needs to be changed, you won't have to go hunting through the code for all instances of "2" and then trying to determine if this particular 2 is relevant to the desired change or if it is some other constant that happens to have the same value.

Use appropriate data types

It appears that the peculiarly named AntsBag variable, although declared as an int, is actually expected to have only two possible values: 0 and 2. Any variable having only two states would normally be a bool rather than an int. Alternatively, one could use an enum or enum class for this purpose.

Consider using a better random number generator

You are currently using

int direction = (rand() % 4) + 1;

There are two problems with this approach. One is that the low order bits of the random number generator are not particularly random, so direction won't be. On my machine, there's a slight but measurable bias toward 0 with that. The second problem is that it's not thread safe because rand stores hidden state. A better solution, if your compiler and library supports it, would be to use the C++11 `std::uniform_int_distribution. It looks complex, but it's actually pretty easy to use. In this case, I'd use something like this:

std::mt19937 gen{std::random_device{}()};
std::uniform_int_distribution<int> dist{1, 4};

And then within the loop:

int direction = dist(gen);

Use more whitespace to enhance readability of the code

Instead of crowding things together like this:

if (pos[1] == 4&&grid[pos[0]][4]==2&&AntsBag==0)

most people find it more easily readable if you use more space:

if (pos[1] == 4 && grid[pos[0]][4] == 2 && AntsBag == 0)

Don't check the same condition twice

In the fragment above, the conditon of the if statement is checked once to see if we need to call CarryFood() and then again within CarryFood(). We don't need both! In this case, I'd suggest removing the function and doing it instead like this:

Use objects

Use of this simulation code could be greatly simplified using objects. One way to do it would be to wrap the entire thing up into a single AntSim object that has three externally available functions:

AntSim(int max);  // constructor defining number of iterations
bool operator()() const; // returns true if more iterations left
AntSim &operator++(); // perform one iteration 

Doing that would make it such that there are no global variables and main could look like this:

int main() 
{       
    for (AntSim sim{5000000}; sim(); ++sim) 
    { }
}

However, I would probably structure things a little differently. The steps below show how that might be done.

Consider rearranging the problem

What is being printed as a result is the path that is created for each iteration of the simulation. Each iteration continues until the ant gets successfully to the destination row. This suggests that instead of storing the path it could be printed as it is created. The only problem with that approach is that the current ordering of output prints the path length first.

Consider each step separately

Here's how I'd probably want to actually write main():

int main() 
{       
    static constexpr NumTrials{5000000};
    AntSim sim;
    std::cout << "%%Total Experiment Number : " << MaxExp << ".  Exp Number-Step Count-Path\n";
    for (int i=1; i <= 5000000; ++i) {
    { 
        auto path = sim.run();
        std::cout << i << ' ' << path.size() << ' ' << path << '\n';
    }
}

The assumption here is that there exists a run() method that returns a path. It may be simplest at the moment to assume that a path is represented as a std::string. This makes it easier to understand what the simulator is actually doing and simpler to output. Note, too, that I'm directing output to std::cout. This can be redirected to a file if desired, but keeps the code very simple.

Keep track of the goal

Instead of calling checkSuccess each time, instead keep track of the number of delivered seeds. When the number of delivered seeds is 5, the iteration is complete. There's no reason to iterate through the grid each time.

Only operate on valid moves

The code should only operate on valid moves. That is, if a chosen direction would move the ant off the grid, keep choosing until it's a valid move. No other code should run until a valid move is generated. How I'd code that:

char direction{dist(gen)};
while (isInvalidMove(pos, direction) ) {
    direction = dist(gen); 
}

Minimize condition checking

If a seed is picked up, it can't also be dropped off in the same move; they are mutually exclusive. So that suggests an if ... else construct instead of just two if statements.

Preallocate space for a path

Growing the path each time can be computationally costly. An alternative would be to reserve some space, say 1K or so, and use that instead. It may be quicker.

Parallelize

Each path can be generated in parallel, so you could use the C++11 thread functions or related and run each trial in parallel. This would speed things considerably.

Do everything in C++

Rather than rely on Octave to post-process the results, you could actually use C++ to do everything. In this case, a naive implemenation could use a std::unordered_set with the path as a key. Then simply total all of the path lengths and do the processing in C++.

Example

Here's a rework of your code with many but not all of these suggestions implemented:

#include <chrono>
#include <vector>
#include <iostream>
#include <fstream>
#include <random>

class AntSim 
{
public:
    std::string run() {
        std::string path{};
        path.reserve(1000);
        int isAntCarryingSeed = false;
        bool grid[5][5] = {
            {false, false, false, false, true},
            {false, false, false, false, true},
            {false, false, false, false, true},
            {false, false, false, false, true},
            {false, false, false, false, true}
        };
        int pos[2] = {2, 2};
        for (int seedsDelivered{0}; seedsDelivered < 5; ) {
            char direction{dist(gen)};
            while (isInvalidMove(pos, direction) ) {
                direction = dist(gen); 
            }
            switch(direction){
                case '1':
                {
                    --pos[1];
                    break;
                }
                case '2':
                {
                    --pos[0];
                    break;
                }
                case '3':
                {
                    ++pos[0];
                    break;
                }
                case '4':
                {
                    ++pos[1];
                    break;
                }
            }
            path.push_back(direction);
            // found seed?
            if (pos[1] == 4 && grid[pos[0]][4] == true && isAntCarryingSeed == false)
            {
                isAntCarryingSeed = true;
                grid[pos[0]][4] = false;
            }
            // drop seed?
            else if (pos[1] == 0 && grid[pos[0]][0] == false && isAntCarryingSeed == true)
            {
                isAntCarryingSeed = false;
                grid[pos[0]][0] = true;
                ++seedsDelivered;
            }
        }
        return path;
    }   

private:
    std::mt19937 gen{std::random_device{}()};
    std::uniform_int_distribution<char> dist{'1', '4'};
    bool isInvalidMove(int * pos, char direction)
    {
        switch(direction)
        {
            case '1':
                if(pos[1] == 0){
                    return true;
                }
                break;
            case '2':
                if (pos[0] == 0)
                {
                    return true;
                }
                break;
            case '3':
                if (pos[0] == 4)
                {
                    return true;
                }
                break;
            case '4':
                if (pos[1] == 4)
                {
                    return true;
                }
                break;
        }
        return false;
    }

};

int main() 
{       
    static constexpr int NumTrials{5000000};
    AntSim sim;
    std::cout << "%%Total Experiment Number : " << NumTrials << ".  Exp Number-Step Count-Path\n";
    for (int i=1; i <= NumTrials; ++i) {
        auto path = sim.run();
        std::cout << i << ' ' << path.size() << ' ' << path << '\n';
    }
}
\$\endgroup\$
  • \$\begingroup\$ What do you mean by "consider wrapping them[such as grid] in objects" \$\endgroup\$ – onurcanbektas Dec 17 '17 at 7:06
  • \$\begingroup\$ Secondly, what is the reason for using static keyword for global variables ? \$\endgroup\$ – onurcanbektas Dec 17 '17 at 7:10
  • 1
    \$\begingroup\$ I’ve added example code to show how one might wrap the code in an object. As shown, it runs around 33% faster than the original. \$\endgroup\$ – Edward Dec 17 '17 at 8:55
  • \$\begingroup\$ One would declare global variables “static” to limit them to file scope. Generally, reducing the scope of variables to the smallest practical produces smaller, faster code, less prone to error and misunderstanding. \$\endgroup\$ – Edward Dec 17 '17 at 9:05
3
\$\begingroup\$

This is a really neat problem and a cool way to solve it! It's very straightforward and easy to understand your solution.

Performance

Usually, the best optimization you can make is to use a better algorithm. I don't know what that would be in this case. So instead of doing that, I tested what you had and tried to improve it.

I profiled your code on my MacBook Pro using llvm with optimizations set to -Os (fastest, smallest). About 70% of the time is spent in ShowResult(). I was able to cut that down to about 17% by writing the entire path out at once instead of writing it out one character at a time. Here's what I did:

void ShowResult(std::vector <int> &l_path)
{
    fprintf(file, "%d %d ", ExpNumber, StepCount);
    if (file != NULL)
    {
        std::vector<char> path(l_path.size());
        for (std::vector<int>::iterator it = l_path.begin(); it != l_path.end(); it++)
        {
            path.push_back('0' + *it);
        }
        fwrite(&path[0], sizeof(char), path.size(), file);
    }
    fprintf(file, "\n");
}

Note that this takes slightly more memory than before. If you could write the data out as binary, you could just write out the l_path variable and skip the loop altogether.

Next, I noticed that std::vector<int>::push_back() was taking about 15% of the time. That's the 3rd highest thing on the list, not the highest, but it looked like an easy target, so I went for it. I created a new variable to hold the length of the path of the previous run. I called it lastPathLength and initialized it to 10:

...
int ExpNumber = 1;
int AntsBag = 0;
size_t lastPathSize = 10;
...

Then, I reserved that much space for the path each iteration through the loop in main():

...
while(ExpNumber <= MaxExp)
{
    Init();
    std::vector <int> path;
    path.reserve(lastPathSize);
    ...

and at the end I set the lastPathSize to the size of the current path:

...
        checkSuccess();
    }
    while(!Success);

    lastPathSize = path.size();

    ShowResult(path);
...

That took it from 15% of total time down to about 6% of total time. At this point, checkMovability() is taking the most time - about 22% of run time. I don't immediately see an obvious way to speed it up. Off the top of my head, maybe some sort of table-driven method instead of a switch statement would make it faster? I can't say for sure.

It looks like rand() is also taking about 14% of total run time. It might be worth checking out other random number generators like arc4random(). I notice there's an arc4random_buf(). It might make sense to fill a buffer with random numbers all at once and pull them off as you need them. I gave it a try and got it down from 14% of total time to 7%. I did it by making a constant for the maximum number of random values to generate:

...
#include <iostream>
#include <sys/time.h>
#define RAND_MAX 5

const size_t    kMaxRands   = 1000;
...

Then I added an array to hold them and a variable to tell us which one is next:

...
int ExpNumber = 1;
int AntsBag = 0;
size_t lastPathSize = 10;
size_t  nextRand    = kMaxRands;
uint32_t rands [ kMaxRands ];
...

I wrote a routine to fill up the array:

void RefillRands()
{
    nextRand = 0;
    arc4random_buf(rands, sizeof(rands));
}

Call the function to fill it before the loop in main():

...
fprintf(file, "%%Total Experiment Number : %d.  Exp Number-Step Count-Path\n", MaxExp);
RefillRands();
while(ExpNumber <= MaxExp)
{
...

Then I modified the code in the loop in main() to pull random values from the array instead of from calling rand():

        int direction = (rands[nextRand] % 4) + 1;
        nextRand++;
        if (nextRand == kMaxRands)
        {
            RefillRands();
        }

It's conceivable that using something like xorshift128() might be faster. I don't know how well it compares in terms of randomness to arc4random() though.

One other way you could speed this up is to run the simulation on multiple cores at the same time. While running it on my machine, I noticed that only 1 core was active, though it was pegged. This seems like it would scale fairly well. (Note than rand() is not thread safe though!)

That's what I was able to do on an initial pass. I hope it helps!

\$\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.