2
\$\begingroup\$

I created a simple program to simulate the Ant's path. The Ant moves north, west, east and south. Each time the Anth moves to an "uncharted" location, I build a Square and give it a color. Each time the Ant steps in a square, the square changes color and the Ant rotates 90° and keeps her track. I use a Stack where I push my Squares. The steps list is something I need to keep track of the path of the Ant. I need to find when the Path stabilizes (Roughly after 10000 steps) and the Ant moves in a uniform manner.

It works great until 106 (takes 5 minutes to run). After that it takes more than 14 hours to get to the 107 mark. I don't get why it takes so much more time, shouldn't it just take 10 × time it took to get to 106 iterations assuming my algorithm is o(n)?

I would like to keep the approach single threaded. What can I optimize?


enum Orientation{
  NORTH, WEST, SOUTH, EAST
}    

public class Square { 
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}

int color = 0;
int x = 0, y = 1;
Stack<Square> squares = new Stack<Square>();
Orientation orientation = Orientation.NORTH;
List<Orientation> steps = new List<Orientation>();
for (int i = 0, counter = 0; i < 10000000; ++i, ++counter)
{

    // First
    if(i == 0)
    {
        squares.Push(new Square() { x = 0, y = 1, color = 1 });
        // Rotate
        orientation = Rotate(orientation, color == 0 ? true : false);
        steps.Add(orientation);
        continue;
    }
    // Move step
    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;

    // Check what the step has
    Square s = squares.Where(square => square.x == x && square.y == y).DefaultIfEmpty(null).FirstOrDefault();

    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }

    // 10^6 mark
    if (i == 999999)
    {
            blackSquaresAt100k = squares.Where(sqa => sqa.color == 1).Count();
            Console.WriteLine(blackSquaresAt100k);
    }

    // 10^7 mark
    if (i == 9999999)
    {
        blackSquaresAt1M = squares.Where(sqa => sqa.color == 1).Count();
        int totalNrOfBlackSquares = (blackSquaresAt1M - blackSquaresAt100k) * 12 + blackSquaresAt1M;
        Console.WriteLine(totalNrOfBlackSquares);
    }
}
\$\endgroup\$
  • 2
    \$\begingroup\$ The question is on the verge of being closed for Lack of concrete context reason. At least, what is squares? Please add all necessary details. \$\endgroup\$ – vnp Jan 15 at 22:19
  • \$\begingroup\$ @vnp Let me know if you need anything more \$\endgroup\$ – Greggz Jan 15 at 22:26
  • 4
    \$\begingroup\$ Well now we see that since squares is a Stack, and Stack.Where takes linear time, the entire thing cannot be \$O(n)\$. Use Set. \$\endgroup\$ – vnp Jan 15 at 23:06
  • \$\begingroup\$ Your code is still incomplete; for example, the Orientation enum is never defined, and the color variable referenced in the if(i==0) block isn't declared. But as @vnp pointed out, your main performance problem is almost certainly the .Where, which may iterate the entire collection. Switching to a Dictionary<Tuple<int, int>, Square>, and using TryGetValue will help you a lot. You may still have issues related to memory allocation as the collections grow very large, however. \$\endgroup\$ – benj2240 Jan 15 at 23:23
  • \$\begingroup\$ Thank you guys for the suggestion I shall try it \$\endgroup\$ – Greggz Jan 15 at 23:29
2
\$\begingroup\$

Optimisation

I use a Stack where I push my Squares.

A stack is the correct data structure when you want last-in-first-out behaviour. Is that the behaviour you need here?

It works great until 106 (takes 5 minutes to run).

That is a long way from "great". 106 shouldn't take 10 seconds. Use the right data structure for the task, which here is something with amortised constant time insertion and lookup.

Other notes

public class Square { 
        public int x, y;
        // White = 0, Black = 1
        public int color = 0;
}

Why are all of the fields mutable? Why is there no explicit constructor? Rather than using a 32-bit type to store a single bit and needing to document the legal values, why not use a 1-bit type (i.e. bool isBlack)?


int color = 0;

Does this need such a wide scope?


for (int i = 0, counter = 0; i < 10000000; ++i, ++counter)

What is the purpose of counter? As far as I can tell, it isn't used anywhere.


        squares.Push(new Square() { x = 0, y = 1, color = 1 });

...

        squares.Push(CreateSquare(x, y, 1));

Why the discrepancy?


        orientation = Rotate(orientation, color == 0 ? true : false);

condition ? true : false is an unnecessarily long way of writing condition.


    if (orientation == Orientation.NORTH) y += 1;
    if (orientation == Orientation.EAST) x -= 1;
    if (orientation == Orientation.WEST) x += 1;
    if (orientation == Orientation.SOUTH) y -= 1;

This is precisely the kind of thing that switch statements were invented to handle.


    // if null create one and rotate
    if (s == null)
    {
        squares.Push(CreateSquare(x, y, 1));
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }else if(s.color == 1)
    {
        s.color = 0;
        orientation = Rotate(orientation, false);
        steps.Add(orientation);
    }else
    {
        s.color = 1;
        orientation = Rotate(orientation, true);
        steps.Add(orientation);
    }

Don't repeat yourself. This could be refactored as

    if (s == null)
    {
        s = new Square { x = x, y = y, color = 0 };
        squares.Push(s);
    }

    orientation = Rotate(orientation, s.color == 0);
    steps.Add(orientation);
    s.color = 1 - s.color;

            blackSquaresAt100k = squares.Where(sqa => sqa.color == 1).Count();

Count has an overload which takes a condition, so enumerable.Where(foo).Count() can be refactored to enumerable.Count(foo).

\$\endgroup\$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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