如何优化BFS实现亚毫秒级执行及多线程方案咨询

云原生阿岚

2026-8-7

问题描述

我现有一个可正常运行的BFS实现，但CPU占用过高：深度为4时耗时亚毫秒，深度为10时却达到10ms。我确信该算法即使在深度为100时也应能实现亚毫秒级执行，但不清楚问题所在。以下是我的Unity代码：

using System.Collections.Generic;
using System.Linq;
using UnityEngine;

public class VisionGraph : MonoBehaviour
{
    public Transform Ground;
    public int Height;
    public int Width;
    private MeshFilter mf;
    public Vector3[] Vertices;
    public float precision;
    public Vector3 SelectedVertex;


    // Start is called before the first frame update
    private void Start()
    {
        mf = Ground.GetComponent<MeshFilter>();
        Matrix4x4 localToWorld = transform.localToWorldMatrix;

        Vector3 world_max = localToWorld.MultiplyPoint3x4(mf.mesh.vertices[0]);

        Width = Mathf.RoundToInt(world_max.z * (1 / precision));
        int maxIndex = Mathf.RoundToInt((world_max.z * (1 / precision)) * (Height * (1 / precision)) * world_max.x);
        Vertices = new Vector3[maxIndex];
        
        //This is the graph initialization. 
        //Indices increment by 1 while actual coordinates increments by `precision`. 
        //Indices are then reversed to coordinates in BFS with `position/precision`.
        int xInd, yInd, zInd; xInd = yInd = zInd = 0;
        float x, y, z; x = y = z = 0;

        int index = 0;

        while (index < Vertices.Length - 1)
        {
            index = (yInd * (Width * Width)) + (zInd * Width) + xInd;

            Debug.Log(index + " " + maxIndex);
            Vertices[index] = new(x, y, z);
            x += precision;
            xInd++;

            if (x > world_max.x)
            {
                x = 0;
                xInd = 0;
                z += precision;
                zInd++;

                if (z > world_max.z)
                {
                    z = 0;
                    zInd = 0;
                    y += precision;
                    yInd++;
                }
            }
        }

        SelectedVertex = Vertices[600];
    }

    private void OnDrawGizmos()
    {
        // Needs to be turned into retrieve index from position.
        // but i'm not sure how to clamp the continuous position to `precision` steps.

        SelectedVertex = Vertices.Where(v => Vector3.Distance(v, SelectedVertex) <= precision - 0.0001 ).FirstOrDefault();

        var watch = System.Diagnostics.Stopwatch.StartNew();
        List<Vector3Int> closeVertices = BFS(SelectedVertex, 10); // second param is the search depth

        watch.Stop();
        Debug.Log(watch.ElapsedMilliseconds);
        foreach (var vert in closeVertices)
        {
            var index = (vert.y * (Width * Width)) + (vert.z * Width) + vert.x;
            if (index >= Vertices.Length) continue;
            Gizmos.color = Color.red;
            Gizmos.DrawSphere(Vertices[index], 0.1f);
        }
    }

    private List<Vector3Int> BFS(Vector3 start, int depth)
    {
        Vector3Int startIndex = new((int)(start.x / precision), (int)(start.y / precision), (int)(start.z / precision));

        Dictionary<Vector3Int, bool> closedList = new();
        List<Vector3Int> queue = new() { startIndex };

        while (queue.Count > 0)
        {
            Vector3Int v = queue[^1];
            queue.RemoveAt(queue.Count-1);

            Vector3Int[] neighbors = new[]
            {
                v + Vector3Int.left,
                v + Vector3Int.right,
                v + Vector3Int.up,
                v + Vector3Int.down,
                v + Vector3Int.forward,
                v + Vector3Int.back,
            };
            foreach (Vector3Int n in neighbors)
            {
                if (n.x < 0 || n.y < 0 || n.z < 0) continue; // this will alos include the high limit of the grid but i dont "need" it at this point of the tests

                //For every implementation of graph search algorithms I make, this always seem to bee the weak part.
                if ((n - startIndex).sqrMagnitude > depth*depth || queue.Any(vert => vert == n) || closedList.ContainsKey(n)) continue;

                queue.Insert(0, n);
            }
            closedList.Add(v, true); 
        }

        return closedList.Keys.ToList();
    }
}

我尝试用Dictionary作为closedList来减少列表搜索时间（之前用closedList.Any(vert => vert == n)），但优化效果不明显，希望有人能指出性能瓶颈。此外，我还想咨询：如何为BFS实现多线程？队列和closedList都具有很强的动态性，是否有方案可以用NativeLists来解决？感谢您的时间，如有不清楚的地方请告知。

性能瓶颈分析

1. 队列操作的时间复杂度问题

你用List模拟队列，RemoveAt(queue.Count-1)是O(1)操作，但Insert(0, n)是O(n)操作——每次往列表头部插入元素都需要移动所有现有元素。深度越大，队列元素数量指数级增长，这个开销会急剧上升。改用Queue<T>，它的Enqueue和Dequeue都是O(1)操作，这是核心性能问题。

2. `queue.Any(vert => vert == n)`的线性搜索

每次检查邻居是否在队列里都要遍历整个队列，时间复杂度O(k)（k为队列长度），深度越大开销越恐怖。用额外的HashSet<Vector3Int>记录待访问队列中的元素，Contains操作变为O(1)。

3. 深度判断的计算冗余

(n - startIndex).sqrMagnitude > depth*depth每次都要计算向量差的平方模长，且没有利用BFS层级遍历的特性。直接记录每个节点的层级，当层级超过深度时停止处理邻居，比距离计算更高效。

4. Vector3Int的哈希性能

Dictionary和HashSet使用Vector3Int作为键时，默认哈希函数效率一般。把Vector3Int转换成唯一整数（比如x + y * width + z * width * height，和Vertices索引生成逻辑一致），用整数作为键能提升哈希性能。

优化后的BFS示例

private List<Vector3Int> BFS(Vector3 start, int depth)
{
    Vector3Int startIndex = new((int)(start.x / precision), (int)(start.y / precision), (int)(start.z / precision));

    // 用Queue实现O(1)入队出队，同时记录节点层级
    Queue<(Vector3Int pos, int currentDepth)> queue = new();
    queue.Enqueue((startIndex, 0));

    // 用HashSet记录已访问节点，避免重复处理
    HashSet<Vector3Int> closedList = new();
    closedList.Add(startIndex);

    while (queue.Count > 0)
    {
        var (v, currentDepth) = queue.Dequeue();

        // 当前层级达到深度，不再处理邻居
        if (currentDepth >= depth)
            continue;

        Vector3Int[] neighbors = new[]
        {
            v + Vector3Int.left, v + Vector3Int.right,
            v + Vector3Int.up, v + Vector3Int.down,
            v + Vector3Int.forward, v + Vector3Int.back
        };

        foreach (Vector3Int n in neighbors)
        {
            if (n.x < 0 || n.y < 0 || n.z < 0) continue;
            // 补充x/y/z的上限检查，避免越界

            if (closedList.Contains(n))
                continue;

            queue.Enqueue((n, currentDepth + 1));
            closedList.Add(n);
        }
    }

    return closedList.ToList();
}

多线程与NativeList方案

1. 普通多线程实现

直接多线程处理BFS需要解决线程安全问题：

用ConcurrentQueue<T>代替普通Queue，用ConcurrentHashSet<T>（.NET Core 3.0+支持，或自行实现）代替普通HashSet，保证多线程下的操作安全。
任务拆分建议按邻居处理并行化，但要注意避免重复访问节点，逻辑复杂度会提升，适合深度极大、节点数量极多的场景。

2. Unity Job System + NativeList方案（无GC高性能）

如果项目使用Unity ECS/Job System，可用NativeQueue<T>和NativeHashSet<T>实现无GC、线程安全的BFS：

using Unity.Burst;
using Unity.Collections;
using Unity.Jobs;
using UnityEngine;

public struct BFSJob : IJob
{
    public NativeQueue<(Vector3Int pos, int depth)>.ParallelWriter queueWriter;
    public NativeQueue<(Vector3Int pos, int depth)>.ReadOnly queueReader;
    public NativeHashSet<Vector3Int> closedList;
    public int maxDepth;
    public int width;
    public int height;

    public void Execute()
    {
        while (queueReader.TryDequeue(out var item))
        {
            var (v, currentDepth) = item;
            if (currentDepth >= maxDepth)
                continue;

            Vector3Int[] neighbors = new[]
            {
                v + Vector3Int.left, v + Vector3Int.right,
                v + Vector3Int.up, v + Vector3Int.down,
                v + Vector3Int.forward, v + Vector3Int.back
            };

            foreach (var n in neighbors)
            {
                if (n.x < 0 || n.y < 0 || n.z < 0 || n.x >= width || n.z >= width || n.y >= height)
                    continue;

                // 原子操作保证线程安全，避免重复添加
                if (closedList.TryAdd(n))
                {
                    queueWriter.Enqueue((n, currentDepth + 1));
                }
            }
        }
    }
}

// 主线程调度Job
private void RunBFSJob(Vector3Int startPos, int depth)
{
    // 分配临时Native容器，用完必须释放
    var queue = new NativeQueue<(Vector3Int pos, int depth)>(Allocator.TempJob);
    var closedList = new NativeHashSet<Vector3Int>(Allocator.TempJob);
    
    queue.Enqueue((startPos, 0));
    closedList.Add(startPos);

    var job = new BFSJob
    {
        queueWriter = queue.AsParallelWriter(),
        queueReader = queue.AsReadOnly(),
        closedList = closedList,
        maxDepth = depth,
        width = Width,
        height = Height
    };

    JobHandle handle = job.Schedule();
    handle.Complete();

    // 转换结果到普通List
    List<Vector3Int> result = new List<Vector3Int>();
    foreach (var item in closedList)
    {
        result.Add(item);
    }

    // 释放Native容器，避免内存泄漏
    queue.Dispose();
    closedList.Dispose();
}

注意：需要开启Unity的ECS相关包，配合Burst编译器能进一步提升性能。

内容的提问来源于stack exchange，提问作者CrimsonFreak

如何优化BFS实现亚毫秒级执行及多线程方案咨询

1. 队列操作的时间复杂度问题 #

2. queue.Any(vert => vert == n)的线性搜索 #

3. 深度判断的计算冗余 #

4. Vector3Int的哈希性能 #

优化后的BFS示例 #

1. 普通多线程实现 #

2. Unity Job System + NativeList方案（无GC高性能） #