C
C#•2y ago
popcorn

✅ Why is my bfs so slow?

        private const int BOARD_SIZE = 8;
        private static readonly List<Point> KING_MOVES = new List<Point>() { new Point(-1, 0), new Point(-1, 1), new Point(0, 1), new Point(1, 1), new Point(1, 0), new Point(1, -1), new Point(0, -1), new Point(-1, -1) };

        class Point
        {
            public int x;
            public int y;

            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }

            public Point(Point p)
            {
                this.x = p.x;
                this.y = p.y;
            }

            public override bool Equals(object? obj)
            {
                Point p = obj as Point;
                return this.x == p.x && this.y == p.y;
            }

            public void Add(Point p)
            {
                this.x = this.x + p.x;
                this.y = this.y + p.y;
            }
        }

        static bool PointInBounds(Point p)
        {
            if (p.x < 1 || p.y < 1)
            {
                return false;
            }

            if (p.x > BOARD_SIZE || p.y > BOARD_SIZE)
            {
                return false;
            }
            return true;
        }
        private const int BOARD_SIZE = 8;
        private static readonly List<Point> KING_MOVES = new List<Point>() { new Point(-1, 0), new Point(-1, 1), new Point(0, 1), new Point(1, 1), new Point(1, 0), new Point(1, -1), new Point(0, -1), new Point(-1, -1) };

        class Point
        {
            public int x;
            public int y;

            public Point(int x, int y)
            {
                this.x = x;
                this.y = y;
            }

            public Point(Point p)
            {
                this.x = p.x;
                this.y = p.y;
            }

            public override bool Equals(object? obj)
            {
                Point p = obj as Point;
                return this.x == p.x && this.y == p.y;
            }

            public void Add(Point p)
            {
                this.x = this.x + p.x;
                this.y = this.y + p.y;
            }
        }

        static bool PointInBounds(Point p)
        {
            if (p.x < 1 || p.y < 1)
            {
                return false;
            }

            if (p.x > BOARD_SIZE || p.y > BOARD_SIZE)
            {
                return false;
            }
            return true;
        }
Here are my "support" classes and method
15 Replies
popcorn
popcornOP•2y ago
        static int bfs(List<Point> obstacles, Point start, Point end)
        {
            List<Tuple<Point, int>> dummyQueue = new List<Tuple<Point, int>>();
            List<Point> visited = new List<Point>();
            visited.Add(start);

            dummyQueue.Add(Tuple.Create(start, 0));
            while (dummyQueue.Count > 0)
            {
                var state = dummyQueue[0];
                Point currentPoint = state.Item1;
                int steps = state.Item2;
                dummyQueue.RemoveAt(0);

                foreach(var move in KING_MOVES)
                {
                    Point next_step = new Point(currentPoint);
                    next_step.Add(move);

                    if (next_step.Equals(end))
                    {
                        return steps + 1;
                    }

                    if (PointInBounds(next_step) && !obstacles.Contains(next_step) && !visited.Contains(next_step));
                    {
                        visited.Add(next_step);
                        dummyQueue.Add(Tuple.Create(next_step, steps + 1));
                    }

                    
                }
            }

            return -1;
        }
        static int bfs(List<Point> obstacles, Point start, Point end)
        {
            List<Tuple<Point, int>> dummyQueue = new List<Tuple<Point, int>>();
            List<Point> visited = new List<Point>();
            visited.Add(start);

            dummyQueue.Add(Tuple.Create(start, 0));
            while (dummyQueue.Count > 0)
            {
                var state = dummyQueue[0];
                Point currentPoint = state.Item1;
                int steps = state.Item2;
                dummyQueue.RemoveAt(0);

                foreach(var move in KING_MOVES)
                {
                    Point next_step = new Point(currentPoint);
                    next_step.Add(move);

                    if (next_step.Equals(end))
                    {
                        return steps + 1;
                    }

                    if (PointInBounds(next_step) && !obstacles.Contains(next_step) && !visited.Contains(next_step));
                    {
                        visited.Add(next_step);
                        dummyQueue.Add(Tuple.Create(next_step, steps + 1));
                    }

                    
                }
            }

            return -1;
        }
And this is the main bfs function. Why is it running slow? I know because it is actually an assessment and it is failing because of time limit exceeded. Hmm, it was because of my "implementation" of the dummyQueue via list. I wonder why is it so slow though? There's not many items as the board is only 8x8. But it is significantly slower than the normal Queue class.
ero
ero•2y ago
do you have a minimal reproduction that we can test?
popcorn
popcornOP•2y ago
        static void Main(string[] args)
        {
            Point start = new Point(1, 1);
            Point end = new Point(8, 8);
            List<Point> obstacles = new List<Point>();
            obstacles.Add(new Point(2, 2));
            obstacles.Add(new Point(3, 3));
            obstacles.Add(new Point(4, 4));
            obstacles.Add(new Point(5, 5));
            obstacles.Add(new Point(6, 6));

            Console.WriteLine(bfs(obstacles, start, end));
        }
        static void Main(string[] args)
        {
            Point start = new Point(1, 1);
            Point end = new Point(8, 8);
            List<Point> obstacles = new List<Point>();
            obstacles.Add(new Point(2, 2));
            obstacles.Add(new Point(3, 3));
            obstacles.Add(new Point(4, 4));
            obstacles.Add(new Point(5, 5));
            obstacles.Add(new Point(6, 6));

            Console.WriteLine(bfs(obstacles, start, end));
        }
Here is the main func
ero
ero•2y ago
what does bfs stand for?
popcorn
popcornOP•2y ago
Breadth-First Search It's a modified Breadth-First Search algorithm to find shortest path for a KING on a board with given start, end and obstacles.
ero
ero•2y ago
oh you have a syntax error here btw or, not error but a HUGE mistake
popcorn
popcornOP•2y ago
What's that?
ero
ero•2y ago
you have a semicolon at the end of your last if which means the code in the block gets executed, no matter what the result of that evaluation is
popcorn
popcornOP•2y ago
Oh yea, I think I spotted that right after I copied it here, but somehow forgot to remove it here.
ero
ero•2y ago
took me forever to find an issue, but here are my benchmark results; 
|                   Method |              Runtime |    Median | Allocated |
|------------------------- |--------------------- |----------:|----------:|
| Board_BreadthFirstSearch |             .NET 7.0 |  7.587 us |      4 KB |
| Board_BreadthFirstSearch | .NET Framework 4.8.1 | 51.813 us |  12.61 KB |
|                   Method |              Runtime |    Median | Allocated |
|------------------------- |--------------------- |----------:|----------:|
| Board_BreadthFirstSearch |             .NET 7.0 |  7.587 us |      4 KB |
| Board_BreadthFirstSearch | .NET Framework 4.8.1 | 51.813 us |  12.61 KB |
public readonly record struct Point(int X, int Y)
{
    public bool IsInBounds
    {
        get => X is >= 1 and <= Board.SIZE
            && Y is >= 1 and <= Board.SIZE;
    }

    public static Point operator +(Point left, Point right)
    {
        return new(left.X + right.X, left.Y + right.Y);
    }

    public static Point operator -(Point left, Point right)
    {
        return new(left.X - right.X, left.Y - right.Y);
    }
}
public readonly record struct Point(int X, int Y)
{
    public bool IsInBounds
    {
        get => X is >= 1 and <= Board.SIZE
            && Y is >= 1 and <= Board.SIZE;
    }

    public static Point operator +(Point left, Point right)
    {
        return new(left.X + right.X, left.Y + right.Y);
    }

    public static Point operator -(Point left, Point right)
    {
        return new(left.X - right.X, left.Y - right.Y);
    }
}
private static ReadOnlySpan<Point> KingMoves
{
    get => new Point[]
    {
        new(-1, 0), new(-1,  1), new(0,  1), new( 1,  1),
        new( 1, 0), new( 1, -1), new(0, -1), new(-1, -1)
    };
}

public static int BreadthFirstSearch(Point start, Point end, params Point[] obstacles)
{
    return BreadthFirstSearch(start, end, obstacles.AsSpan());
}

public static unsafe int BreadthFirstSearch(Point start, Point end, ReadOnlySpan<Point> obstacles)
{
    HashSet<Point> visited = new() { start };
    Queue<(Point, int)> nextSteps = new();
    nextSteps.Enqueue((start, 0));

    ReadOnlySpan<Point> km = KingMoves;
    int moves = km.Length;

    fixed (Point* pKingMoves = km)
    {
        while (nextSteps.Count > 0)
        {
            (Point current, int steps) = nextSteps.Dequeue();

            for (int i = 0; i < moves; i++)
            {
                Point next = current + pKingMoves[i];

                if (next == end)
                {
                    return steps + 1;
                }

                if (next.IsInBounds && !obstacles.Contains(next) && visited.Add(next))
                {
                    nextSteps.Enqueue((next, steps + 1));
                }
            }
        }

        return -1;
    }
}
private static ReadOnlySpan<Point> KingMoves
{
    get => new Point[]
    {
        new(-1, 0), new(-1,  1), new(0,  1), new( 1,  1),
        new( 1, 0), new( 1, -1), new(0, -1), new(-1, -1)
    };
}

public static int BreadthFirstSearch(Point start, Point end, params Point[] obstacles)
{
    return BreadthFirstSearch(start, end, obstacles.AsSpan());
}

public static unsafe int BreadthFirstSearch(Point start, Point end, ReadOnlySpan<Point> obstacles)
{
    HashSet<Point> visited = new() { start };
    Queue<(Point, int)> nextSteps = new();
    nextSteps.Enqueue((start, 0));

    ReadOnlySpan<Point> km = KingMoves;
    int moves = km.Length;

    fixed (Point* pKingMoves = km)
    {
        while (nextSteps.Count > 0)
        {
            (Point current, int steps) = nextSteps.Dequeue();

            for (int i = 0; i < moves; i++)
            {
                Point next = current + pKingMoves[i];

                if (next == end)
                {
                    return steps + 1;
                }

                if (next.IsInBounds && !obstacles.Contains(next) && visited.Add(next))
                {
                    nextSteps.Enqueue((next, steps + 1));
                }
            }
        }

        return -1;
    }
}
i don't know if you're locked into .net framework for some reason, but if you're able, just upgrade to .net 7
popcorn
popcornOP•2y ago
Hmm, I used .NET Core 6.0
ero
ero•2y ago
ah. you're not any modern features, that's why i assumed
popcorn
popcornOP•2y ago
But I see you made some nice optimalisations to my code which probably sped things up a lot. Like the usage of hashset and Queue. I think the main problem in my app was that I "implemented" queue using the List<> Where I did .removeAt(0) to pop an item from the list That might have been the bottleneck
basically, i am little cat
basically, i am little cat•2y ago
<:think_eyes:879685758917701642>
Accord
Accord•2y ago
Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.
Want results from more Discord servers?
Add your server