我正在使用在C＃中用Unity开发的游戏的优先级队列来实现Dijkstra的算法。我对性能有些失望，所以我决定将代码移植到C ++，看看性能是否与语言或算法本身有关。路径查找通过3D网格进行搜索，并根据一些附加条件（单元格过滤器）选择某些边缘/邻居。

问题是该网格仅包含3000个单元，C＃算法需要38毫秒找到一条路。 C ++版本仅需2毫秒即可完成完全相同的操作！效率非常低下，或者C＃的速度变慢了。 C＃版本将网格存储为多维数组，C ++版本使用额外的get_index函数对其进行仿真，该函数使用x，y和z坐标计算向量的索引。我通过使用SortedSet和带有同时包含值和优先级值（dist）的特殊队列节点来模拟C＃中的优先级队列。两种算法都只通过添加使旧值无效的新值来模拟更新优先级队列。这也通过将优先级存储在dist哈希表中来完成。

C＃：

using System;
using System.Collections.Generic;
using System.IO;

namespace PathFinding.NET {
    struct Vec3 {
        public int x, y, z;

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

        public static Vec3 operator +(Vec3 a, Vec3 b) {
            return new Vec3(a.x + b.x, a.y + b.y, a.z + b.z);
        }

        public static bool operator ==(Vec3 a, Vec3 b) {
            return a.x == b.x && a.y == b.y && a.z == b.z;
        }

        public static bool operator !=(Vec3 a, Vec3 b) {
            return !(a == b);
        }

        public static float Dist(Vec3 a, Vec3 b) {
            int dx = a.x - b.x;
            int dy = a.y - b.y;
            int dz = a.z - b.z;

            return (float)Math.Sqrt(dx * dx + dy * dy + dz * dz);
        }

        public static Vec3 Min(Vec3 a, Vec3 b) {
            return new Vec3(
                Math.Min(a.x, b.x),
                Math.Min(a.y, b.y),
                Math.Min(a.z, b.z)
            );
        }

        public static Vec3 Max(Vec3 a, Vec3 b) {
            return new Vec3(
                Math.Max(a.x, b.x),
                Math.Max(a.y, b.y),
                Math.Max(a.z, b.z)
            );
        }

        public override string ToString() {
            return "(" + x + ", " + y + ", " + z + ")";
        }

        public int CompareTo(object obj) {
            var other = (Vec3)obj;

            if (x == other.x) {
                if (y == other.y) {
                    return z.CompareTo(other.z);
                } else {
                    return y.CompareTo(other.y);
                }
            } else {
                return x.CompareTo(other.x);
            }
        }
    }

    struct Cell {
        public bool Occupied;
        public bool WalkableSurface;
    }

    struct QueueNode : IComparable {
        public Vec3 Value;
        public float Dist;

        public QueueNode(Vec3 value, float dist) {
            Value = value;
            Dist = dist;
        }

        public int CompareTo(object obj) {
            var other = (QueueNode)obj;

            if (Dist != other.Dist) {
                return Dist.CompareTo(other.Dist);
            } else {
                return Value.CompareTo(other.Value);
            }
        }
    }

    class Program {
        private static Cell[,,] Grid = null;
        private static int sx, sy, sz;

        private static List<Vec3> GetNeighbours(Vec3 cell) {
            var neighbours = new List<Vec3>();

            for (int dx = -1; dx <= 1; dx++) {
                for (int dy = -1; dy <= 1; dy++) {
                    for (int dz = -1; dz <= 1; dz++) {
                        var coord = cell + new Vec3(dx, dy, dz);

                        bool notSelf = !(dx == 0 && dy == 0 && dz == 0);
                        bool connectivity = Math.Abs(dx) + Math.Abs(dy) + Math.Abs(dz) <= 2;
                        bool withinGrid = coord.x >= 0 && coord.y >= 0 && coord.z >= 0 && coord.x < sx && coord.y < sy && coord.z < sz;

                        if (notSelf && connectivity && withinGrid) {
                            neighbours.Add(coord);
                        }
                    }
                }
            }

            return neighbours;
        }

        private static List<Vec3> FindPath(Vec3 start, Vec3 end, Func<Vec3, Vec3, bool> cellFilter) {
            if (!cellFilter(start, start) || !cellFilter(end, end)) {
                throw new ArgumentException("Start and/or end fail cell filter!");
            }

            // Initialize data structures
            var dist = new Dictionary<Vec3, float>();
            var prev = new Dictionary<Vec3, Vec3?>();

            // We're intentionally not using the update priority function to mimic the C++ algorithm
            var Q = new SortedSet<QueueNode>();

            for (int x = 0; x < sx; x++) {
                for (int y = 0; y < sy; y++) {
                    for (int z = 0; z < sz; z++) {
                        var coord = new Vec3(x, y, z);

                        if (cellFilter(coord, coord)) {
                            dist[coord] = float.MaxValue;
                            Q.Add(new QueueNode(coord, float.MaxValue));

                            prev[coord] = null;
                        }
                    }
                }
            }

            dist[start] = 0;
            Q.Add(new QueueNode(start, 0));

            // Search loop
            while (Q.Count > 0) {
                var u = Q.Min;
                Q.Remove(Q.Min);

                // Old priority queue value
                if (u.Dist != dist[u.Value]) {
                    continue;
                }

                if (u.Value == end) {
                    break;
                }

                foreach (var v in GetNeighbours(u.Value)) {
                    if (cellFilter(u.Value, v)) {
                        float alt = dist[u.Value] + Vec3.Dist(u.Value, v);
                        if (alt < dist[v]) {
                            dist[v] = alt;
                            Q.Add(new QueueNode(v, alt));

                            prev[v] = u.Value;
                        }
                    }
                }
            }

            // Trace path - if there is one
            var path = new List<Vec3>();

            if (prev[end] != null) {
                Vec3? current = end;

                while (current != null) {
                    path.Add(current.Value);
                    current = prev[current.Value];
                }

                path.Reverse();
            }

            return path;
        }

        private static bool IsFloor(Vec3 pos) {
            if (pos.y > 0) {
                var posBelow = pos + new Vec3(0, -1, 0);
                return !Grid[pos.x, pos.y, pos.z].Occupied && Grid[posBelow.x, posBelow.y, posBelow.z].WalkableSurface;
            } else {
                return false;
            }
        }

        private static bool CellFilter(Vec3 from, Vec3 to) {
            if (from.y == to.y) {
                // Check if all cells we're moving through are floors (important when moving diagonally)
                var min = Vec3.Min(from, to);
                var max = Vec3.Max(from, to);

                for (int x = min.x; x <= max.x; x++) {
                    for (int z = min.z; z <= max.z; z++) {
                        if (!IsFloor(new Vec3(x, min.y, z))) {
                            return false;
                        }
                    }
                }

                return true;
            } else {
                // If the movement is vertical, then perform no diagonal check
                return IsFloor(to);
            }
        }

        public static void Main(string[] args) {
            // Read grid
            string[] gridLines = File.ReadAllLines("grid.txt");

            sx = int.Parse(gridLines[0].Split(' ')[0]);
            sy = int.Parse(gridLines[0].Split(' ')[1]);
            sz = int.Parse(gridLines[0].Split(' ')[2]);

            Grid = new Cell[sx, sy, sz];

            int i = 1;
            for (int x = 0; x < sx; x++) {
                for (int y = 0; y < sy; y++) {
                    for (int z = 0; z < sz; z++) {
                        Cell cell = new Cell();
                        cell.Occupied = bool.Parse(gridLines[i].Split(' ')[0]);
                        cell.WalkableSurface = bool.Parse(gridLines[i].Split(' ')[0]);
                        Grid[x, y, z] = cell;

                        i++;
                    }
                }
            }

            // Do pathfinding
            Vec3 start = new Vec3(9, 2, 6);
            Vec3 end = new Vec3(45, 2, 0);

            var t1 = DateTime.Now;
            var path = FindPath(start, end, CellFilter);
            var t2 = DateTime.Now;

            Console.WriteLine("best path is " + path.Count + " cells long");
            Console.WriteLine("path finding took " + (t2 - t1).TotalMilliseconds + " ms");
        }
    }
}


C ++ 

#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <functional>
#include <stdexcept>
#include <queue>
#include <unordered_map>
#include <chrono>

struct vec3 {
    int x, y, z;

    int get_index(int sx, int sy, int sz) const {
        return x * sy * sz + y * sz + z;
    }

    bool operator==(const vec3& other) const {
        return x == other.x && y == other.y && z == other.z;
    }

    vec3 operator+(const vec3& other) const {
        return{x + other.x, y + other.y, z + other.z};
    }

    static vec3 min(const vec3& a, const vec3& b) {
        return{std::min(a.x, b.x), std::min(a.y, b.y), std::min(a.z, b.z)};
    }

    static vec3 max(const vec3& a, const vec3& b) {
        return{std::max(a.x, b.x), std::max(a.y, b.y), std::max(a.z, b.z)};
    }

    static float dist(const vec3& a, const vec3& b) {
        auto dx = static_cast<float>(a.x - b.x);
        auto dy = static_cast<float>(a.y - b.y);
        auto dz = static_cast<float>(a.z - b.z);

        return sqrtf(dx*dx + dy*dy + dz*dz);
    }
};

namespace std {
    template<>
    struct hash<vec3> {
        size_t operator()(const vec3& k) const {
            return ((hash<int>()(k.x)
                ^ (hash<int>()(k.y) << 1)) >> 1)
                ^ (hash<int>()(k.z) << 1);
        }
    };
}

struct cell {
    bool occupied;
    bool walkableSurface;
};

int sx, sy, sz;
std::vector<cell> grid;

std::vector<vec3> get_neighbours(const vec3& cell) {
    std::vector<vec3> neighbours;

    for (int dx = -1; dx <= 1; dx++) {
        for (int dy = -1; dy <= 1; dy++) {
            for (int dz = -1; dz <= 1; dz++) {
                auto coord = cell + vec3{dx, dy, dz};

                bool notSelf = !(dx == 0 && dy == 0 && dz == 0);
                bool connectivity = abs(dx) + abs(dy) + abs(dz) <= 2;
                bool withinGrid = coord.x >= 0 && coord.y >= 0 && coord.z >= 0 && coord.x < sx && coord.y < sy && coord.z < sz;

                if (notSelf && connectivity && withinGrid) {
                    neighbours.push_back(coord);
                }
            }
        }
    }

    return neighbours;
}

std::vector<vec3> find_path(const vec3& start, const vec3& end, bool(*cellFilter)(const vec3&, const vec3&)) {
    if (!cellFilter(start, start) || !cellFilter(end, end)) {
        throw std::invalid_argument("start and/or end fail cell filter!");
    }

    // Initialize data structures
    std::unordered_map<vec3, float> dist;
    std::unordered_map<vec3, vec3> prev;

    struct queue_node {
        vec3 value;
        float dist;
    };

    auto cmp = [&](const queue_node& a, const queue_node& b) {
        return a.dist > b.dist;
    };

    std::priority_queue<queue_node, std::vector<queue_node>, decltype(cmp)> Q(cmp);

    for (int x = 0; x < sx; x++) {
        for (int y = 0; y < sy; y++) {
            for (int z = 0; z < sz; z++) {
                vec3 coord = {x, y, z};

                if (cellFilter(coord, coord)) {
                    dist[coord] = std::numeric_limits<float>::max();
                    Q.push({coord, std::numeric_limits<float>::max()});

                    prev[coord] = vec3{-1, -1, -1};
                }
            }
        }
    }

    dist[start] = 0;
    Q.push({start, 0});

    // Search loop
    while (!Q.empty()) {
        auto u = Q.top();
        Q.pop();

        // Old priority queue value
        if (u.dist != dist[u.value]) {
            continue;
        }

        if (u.value == end) {
            break;
        }

        for (const vec3& v : get_neighbours(u.value)) {
            if (cellFilter(u.value, v)) {
                float alt = dist[u.value] + vec3::dist(u.value, v);
                if (alt < dist[v]) {
                    dist[v] = alt;
                    Q.push({v, alt});

                    prev[v] = u.value;
                }
            }
        }
    }

    // Trace path - if there is one
    std::vector<vec3> path;

    if (prev[end].x != -1) {
        vec3 current = end;

        while (current.x != -1) {
            path.push_back(current);
            current = prev[current];
        }

        std::reverse(path.begin(), path.end());
    }

    return path;
}

bool isFloor(const vec3& pos) {
    if (pos.y > 0) {
        return !grid[pos.get_index(sx, sy, sz)].occupied && grid[(pos + vec3{0, -1, 0}).get_index(sx, sy, sz)].walkableSurface;
    } else {
        return false;
    }
}

bool cellFilter(const vec3& from, const vec3& to) {
    if (from.y == to.y) {
        // Check if all cells we're moving through are floors (important when moving diagonally)
        auto min = vec3::min(from, to);
        auto max = vec3::max(from, to);

        for (int x = min.x; x <= max.x; x++) {
            for (int z = min.z; z <= max.z; z++) {
                if (!isFloor({x, min.y, z})) {
                    return false;
                }
            }
        }

        return true;
    } else {
        // If the movement is vertical, then perform no diagonal check
        return isFloor(to);
    }
}

int main() {
    // Read grid
    std::ifstream gridFile("grid.txt");

    gridFile >> sx >> sy >> sz;

    int i = 0;
    grid.resize(sx * sy * sz);

    for (int x = 0; x < sx; x++) {
        for (int y = 0; y < sy; y++) {
            for (int z = 0; z < sz; z++) {
                bool occupied, walkableSurface;
                gridFile >> occupied >> walkableSurface;
                grid[i++] = {occupied, walkableSurface};
            }
        }
    }

    // Do pathfinding
    vec3 start = {9, 2, 6};
    vec3 end = {45, 2, 0};

    try {
        auto t1 = std::chrono::high_resolution_clock::now();
        auto path = find_path(start, end, cellFilter);
        auto t2 = std::chrono::high_resolution_clock::now();

        float ms = std::chrono::duration_cast<std::chrono::microseconds>(t2 - t1).count() / 1000.0f;

        std::cout << "best path is " << path.size() << " cells long" << std::endl;
        std::cout << "path finding took " << ms << " ms" << std::endl;
    } catch (std::exception& e) {
        std::cout << "exception: " << e.what() << std::endl;
    }

    return 0;
}


如果要自己运行算法，则需要此grid.txt文件。

评论

C ++的priority_queue由连续的数组支持，而SortedSet由平衡的二进制搜索树支持。后者需要比前者更多的动态分配和节点调整。尝试在C ++中使用std :: set并再次比较性能。
用科学回答性能问题；使用探查器发现实际上是缓慢的。关于程序中实际上什么慢的一些有根据的猜测是错误的。
公共静态浮点Dist（Vec3 a，Vec3 b）的唯一原因是比较距离。因此，您实际上并不需要那里的距离只是相对值。您应该实现不执行昂贵的平方根运算的公共静态float DistSquared（Vec3 a，Vec3 b）函数，并使用该函数比较相对距离。
@SiyuanRen这个想法是使C＃更快而不是C ++更快。确保通过使翻译不正确而使任何代码看起来快速。建议最好使用C＃代码的后备存储来更好地解决这种情况。
@LokiAstari：我的想法是首先将速度与std :: set进行比较。如果差异很大，那么您就知道瓶颈在于二进制搜索树和堆的差异，然后可以在C＃中实现堆以加快处理速度。您可以直接在C＃中编写堆并比较速度，但是如果发现差异可以忽略，那将是浪费时间。

#1 楼

首先，您应该在测量之前运行FindPath方法几次，以便C＃运行时有机会优化代码。

// Warmup iterations for profiling
for (int j = 0; j < 10; j++) {
    FindPath(start, end, CellFilter);
}


这样做可以得到时间从我最初的38毫秒减少到我的机器上的约17毫秒。为了使JIT最佳化，您必须为其提供有关其Key类型的必要信息，否则它将退回到运行时反射和虚拟方法调用。

任何用作Dictionary的结构SortedSet应该实现Key接口。同样，应该重写Dictionary和IEquatable<T>（编译器甚至会发出警告）。 

struct Vec3 : IComparable<Vec3>, IEquatable<Vec3> {
    [...]
    public bool Equals(Vec3 other) {
        return other == this;
    }

    public override int GetHashCode() {
        return ((x.GetHashCode()
            ^ (y.GetHashCode() << 1)) >> 1)
            ^ (z.GetHashCode() << 1);
    }

    public override bool Equals(object obj) {
        if (obj is Vec3) {
            return (Vec3)obj == this;
        }

        return false;
    }
}


经过这些更改，GetHashCode只用了4毫秒。

我们可以通过传入自定义Equals进一步优化词典并消除了SortedSet调用。

struct QueueNode : IComparable<QueueNode> {
    [...]
    public int CompareTo(QueueNode other) {
        if (Dist != other.Dist) {
            return Dist.CompareTo(other.Dist);
        } else {
            return Value.CompareTo(other.Value);
        }
    }
}


IComparable<T>的最终代码大约需要2.8毫秒。

总而言之，请始终实现正确的通用接口。在集合中使用的结构上。它允许JIT实际上优化代码。

有用的链接


Dictionary（Of TKey，TValue）类。感谢@ t3chb0t，请参阅“备注”部分。
Unity的C＃性能技巧，第2部分：结构和枚举。它专门讨论Unity的实现。

最终代码

class Vec3Comparer : IEqualityComparer<Vec3>
{
    public bool Equals(Vec3 a, Vec3 b) {
        return a == b;
    }

    public int GetHashCode(Vec3 obj) {
        return ((IntegerHash(obj.x)
                ^ (IntegerHash(obj.y) << 1)) >> 1)
                ^ (IntegerHash(obj.z) << 1);
    }

    static int IntegerHash(int a) {
        // fmix32 from murmurhash
        uint h = (uint)a;
        h ^= h >> 16;
        h *= 0x85ebca6bU;
        h ^= h >> 13;
        h *= 0xc2b2ae35U;
        h ^= h >> 16;
        return (int)h;
    }
}

void FindPath(...) {
    [...]

    // Initialize data structures
    Vec3Comparer comparer = new Vec3Comparer();
    var dist = new Dictionary<Vec3, float>(comparer);
    var prev = new Dictionary<Vec3, Vec3?>(comparer);

    [...]
}


评论

\ $ \ begingroup \ $
我一直在想是否应该听那些警告。
\ $ \ endgroup \ $
–t3chb0t
17年1月16日在12:02
\ $ \ begingroup \ $
为什么需要IntegerHash？您不能简单地使用int.GetHashCode方法吗？您写道应该删除GetHashCode，但是为什么呢？
\ $ \ endgroup \ $
–t3chb0t
17年1月16日在12:08


\ $ \ begingroup \ $
@ t3chb0t主要是性能，它从4ms节省了大约1m。因此，性能提高了约25％。我不知道int.GetHashCode的实现是什么，但是GetHashCode绝对是一个虚拟调用，而JIT可能不会内联。 C ++编译器的最大优点是，它可以相对轻松地内嵌该示例中的几乎所有内容。
\ $ \ endgroup \ $
–mordecai154
17年1月16日在12:38
\ $ \ begingroup \ $
@ mordecai154如果我在BenchmarkingDotNET中运行示例，则使用您的哈希值得到2.5131ms±0.0081，使用因子和和int.GetHashCode获得2.3125ms±0.0064，并且通过因子和得到2.3052ms±0.0040，并且整数。
\ $ \ endgroup \ $
– Johnbot
17年1月16日在15:29
\ $ \ begingroup \ $
@ t3chb0t永远不要忽略警告。当然不要提交产生它们的代码。
\ $ \ endgroup \ $
– jpmc26
17年1月18日在12:41

#2 楼

目前，我忽略了C＃代码（及其速度），而是回顾了C ++代码，以了解可能会提高可读性的方式（但对于像样的编译器，我建议的建议不应影响其速度） ）。

单元格

而不是在main中有读取组件的代码，然后将它们组合成cell，我宁愿cell知道如何从中读取自身流：

struct cell {
    bool occupied;
    bool walkableSurface;

    friend std::istream &operator>>(std::istream &is, cell &c) {
        return is >> c.occupied >> c.walkableSurface;
    }
};


网格

同样，在我看来，现在，您已经知道分布式3D网格的结构在很多代码中。 main将数据读取到网格中，vec3::get_index从3D矢量转换为网格索引，依此类推。

我宁愿将其集中到一个类中，该类提供更方便的接口，按此顺序：

class Grid {
    std::vector<cell> data;
public:
    int sx, sy, sz;

    cell &operator[](vec3 const &index) {
        return data[index.x * sy * sz + index.y * sz + index.z];
    }

    friend std::istream &operator>>(std::istream &is, Grid &g) {
        is >> g.sx >> g.sy >> g.sz;

        int i = 0;
        g.data.resize(g.sx * g.sy * g.sz);

        is >> std::boolalpha;

        for (int x = 0; x < g.sx; x++) {
            for (int y = 0; y < g.sy; y++) {
                for (int z = 0; z < g.sz; z++) {
                    is >> g.data[i++];
                }
            }
        }
        return is;
    }

    bool contains(vec3 const &coord) {
        return coord.x >= 0 && coord.x < sx && coord.y >= 0 && coord.y < sy && coord.z >= 0 && coord.x < sz;
    }
} grid;


将这些放置在适当的位置，main在网格中读取如下内容：

std::ifstream gridFile("grid.txt");

gridFile >> grid;


。 ..和isFloor变成这样的东西：

return pos.y > 0 && !grid[pos].occupied && grid[(pos + vec3{ 0, -1, 0 })].walkableSurface;


withinGrid中的get_neighbors 的计算简化为：

bool withinGrid = grid.contains(coord);


queue_node

看着queue_node，我想我会尝试用相当小的重写来封装其比较标准：

这样，我们就可以将priority_queue简化一些，使其成为：可以改善。最明显的是cellFilter-它倾向于表明我们对某个单元格是否符合某些标准感兴趣，但没有告诉我们有关其要满足的标准的任何信息。

Timing

也许是因为我浪费了太多时间在这里以及在Stack Overflow上回答问题，但是我发现拥有计时功能很方便，因为它可以让我在不使用计时功能的情况下计时每次都重写时序代码。我用这个：

struct queue_node {
    vec3 value;
    float dist;

    bool operator<(queue_node const &other) const {
        return other.dist < dist;
    }
};


这样，对您的代码进行计时就变成了这样：

std::priority_queue<queue_node> Q;


使用endl


我建议（永远）反对使用std::endl。插入换行符后，它会刷新流。这是很少需要的。在真正需要的罕见情况下，我认为最好使用以下代码将其明确化：

template <typename F, typename ...Args>
auto timer(F f, std::string const &label, Args && ...args) {
    using namespace std::chrono;

    auto start = high_resolution_clock::now();
    auto holder = f(std::forward<Args>(args)...);
    auto stop = high_resolution_clock::now();
    std::cout << label << " time: " << duration_cast<microseconds>(stop - start).count() << "\n";

    return holder;
}


在这种特殊情况下，它不会使这是一个显着的差异，但这仍然是一个坏习惯，它会使代码的速度降低大约10倍，而实际收益却很小。包括内嵌时间代码，而不是像往常那样使用单独的标头。）

#include "timer"

// ...

auto path = timer(find_path, "Find path", start, end, cellFilter);
std::cout << "best path is " << path.size() << " cells long\n";


评论

\ $ \ begingroup \ $
@Christoph，所有代码都应该可读，无论是一次性代码还是生产代码，这都是一种习惯，您应该始终能够编写可读代码，特别是如果您要向他人展示它，例如发布在CR上。此答案不包含任何无效信息，因此仅出于评论可读性而对其进行投票是不公平的。审查可以包括所有主题，而不必包括OP明确要求的主题。
\ $ \ endgroup \ $
–t3chb0t
17年1月16日在11:12
\ $ \ begingroup \ $
@Christoph：部分出于习惯。 mordecai154的代码提高了C＃代码的速度-但是至少对我而言，C ++代码的速度仍快两倍。通过优化C ++的类似工作，毫无疑问，它的速度也可以提高，因此比C＃快5-8倍看起来是完全可行的。简而言之，他可能想考虑扔掉C＃并维护C ++。
\ $ \ endgroup \ $
–杰里·科芬（Jerry Coffin）
17年1月16日15:00


\ $ \ begingroup \ $
@Christoph：在我看来，这似乎不属于审查代码的范围。我检查了代码。由他来得出结论。
\ $ \ endgroup \ $
–杰里·科芬（Jerry Coffin）
17年1月16日15:56


\ $ \ begingroup \ $
感谢您的代码审查，感谢您的建议，因为其中一些建议也适用于C＃代码的结构。我认为我不能完全切换到C ++，因为Unity要求我至少写一些C＃代码来与之交互。您对cellFilter有一个命名建议吗？这个想法是，不同的对象对路径查找有不同的要求（例如可用空间，它们会飞还是走？）
\ $ \ endgroup \ $
–概述
17年1月16日在17:15
\ $ \ begingroup \ $
@Overv：明显的可能性是cellFilter应该做更多的事情来反映它所做的过滤，而不仅仅是它正在过滤的事实。使用您的示例，一个SpaceAvailableFilter（或者，如果至少相当准确，则可能只是“ EmptyCell”）。
\ $ \ endgroup \ $
–杰里·科芬（Jerry Coffin）
17年1月16日在22:46

#3 楼

多维数组可能是C＃实现的弱点。尝试使用速度更快但不易使用的锯齿状数组。

您可以在C＃中的多维数组和数组数组之间有何区别阅读更多内容。在这样。这个答案将两个阵列系统进行了比较。

编辑：我已经对其进行了测试，其差异几乎无法测量。看来他们已经解决了它。



var t1 = DateTime.Now;
var path = FindPath(start, end, CellFilter);
var t2 = DateTime.Now;



您不应该使用DateTime测量时间。使用Stopwatch 

var sw = Stopwatch.StartNew();
var path = FindPath(start, end, CellFilter);
sw.Stop();

Console.WriteLine($"path finding took {sw.Elapsed}");


如果要获得最佳性能，请确保在Realease模式下和Visual Studio外部运行测试。


要在C＃版本中查找不太明显的瓶颈，应使用探查器。

评论

\ $ \ begingroup \ $
相反，我认为由真实数组提供的连续内存会增加高速缓存命中率，因此比散布在整个内存中的锯齿状数组导致更好的性能；前提是元素是结构。
\ $ \ endgroup \ $
–彼得-恢复莫妮卡
17年1月16日在10:59


\ $ \ begingroup \ $
进行了一段时间的搜索之后，我在stackoverflow的讨论中看到C'编译器/ CLR用于为锯齿形数组创建更快的代码（Mono表现更好）。听起来好像该问题现在已经在Microsoft方面解决了。
\ $ \ endgroup \ $
–彼得-恢复莫妮卡
17年1月16日在11:19


\ $ \ begingroup \ $
@ PeterA.Schneider我发布的链接是您发布的链接问题的答案之一。我尝试通过Google搜索有关此问题的新信息，但未找到任何内容。锯齿状阵列在Windows上似乎仍然更快。
\ $ \ endgroup \ $
–t3chb0t
17年1月16日，11：23


\ $ \ begingroup \ $
同一个帖子：哦:-)。从2013年开始，Amro对这个答案的评论（下第三）以及Eglin的回答似乎都表明该问题到那时已得到解决或至少有所改善。
\ $ \ endgroup \ $
–彼得-恢复莫妮卡
17年1月16日，11：31


\ $ \ begingroup \ $
@mathreadler避免所有边界检查的唯一方法是使用不安全的代码。 C＃可以做到这一点，但这基本上意味着您正在那时编写C。如果您有非常全面的断言和测试，还不错，但是很少值得冒险。对于3000个单元格来说，很明显，这个问题是算法问题，而不是“ bounds-checking-bound”-我跳出来的第一件事是“您正在使用哈希集而不提供良好的哈希值！”请注意，每一代新的Intel CPU的价格都越来越便宜。而且没有分支预测错误，因为无论如何总会在边界内访问正确的代码。
\ $ \ endgroup \ $
–罗安
17年1月19日在14:56

#4 楼

最严重的问题可能是使用了SortedSet集合。以我的经验，Sorted*集合很少是您真正想要的集合，并且性能令人怀疑。距离）。然后，您将拥有可以快速，直接地处理/更新的前沿队列。这里有一个名为DelayQueue的示例实现：Ark.Collections.DelayQueue。

#5 楼

C++和C#的速度更快

重温旧的问题。在阅读此问题及其已经非常好的答案时，发生了以下事情：
哈希表很慢
哈希和随后在RAM周围的跳动都没有那么快。 C ++ unordered_map另外受到阻碍，因为它试图保持向后ABI兼容性。上面算法的内部循环全是关于哈希表查找的。键是int中3个vec3的异或。
首先，我们可以尝试使哈希表更快。一种实现方法通常是更好的哈希函数。上面使用的那个有点“泛型”。我们可以利用我们的领域知识来改进它。我们几乎知道，x,y,z中的vec3不会超过100万。因此，如果我们仅屏蔽每个整数的最低20位，然后将其移位并|将其组合到哈希函数的64位输出中，则将得到“完美的哈希函数”：快速计算并为每个哈希值提供唯一的哈希值输入零碰撞：
namespace std {
template <>
struct hash<vec3> {
  std::size_t operator()(const vec3& v) const {
    return ((static_cast<std::size_t>(v.x) & 0xfffffUL) << 40U) |
           ((static_cast<std::size_t>(v.y) & 0xfffffUL) << 20U) |
           ((static_cast<std::size_t>(v.z) & 0xfffffUL));
  }
};
} // namespace std

这实际上已经是一个巨大的收获。大约快2倍。如果我们使用更好的hashmap实现，我们甚至可以使其速度提高2.5倍。
但是，如果我们了解基本的见解是，我们甚至可以做得更好：
哈希表之间通常存在时间/空间权衡和稀疏数组。
那些整数的范围（网格大小）有限，我们可以将它们用作数组的索引，而不是散列。
在C ++中，我可以轻松地对dist和prev执行此操作使用以下模板：
  template <typename T>
  struct grid_vector {
    explicit grid_vector(vec3 dims, const T& defv = T())
        : sx_(dims.x), sy_(dims.y), sz_(dims.z), data_(sx_ * sy_ * sz_, defv) {}

    T& operator[](const vec3& index) {
      return data_[index.x * sy_ * sz_ + index.y * sz_ + index.z];
    }

  private:
    int            sx_, sy_, sz_;
    std::vector<T> data_;
  };

值得吗？
首先要节省空间。有6000个“单元”，只有约800个通过cellFilter。因此，通过使用x,y,z作为dist / prev的索引，我们在每个向量中浪费了5200个条目。这不是“很多记忆”，但您的里程可能会有所不同。
如果您担心内存使用情况，或者在有效单元很少的情况下网格尺寸会更大（浪费更多的空间），则可以使用上面的更好的哈希函数和更好的hashmap实现。以下收益仍然适用。
如果您乐于刻录一些内存，收益将是可观的。事实证明，删除哈希表解决了主要瓶颈，算法的find_path部分从2ms下降到0.4ms，即增加了5倍。不错这是否值得，取决于应用程序，但是如果需要，则可以获得收益。我没有C＃的数据，但我怀疑那里也有很大的收益（以空间为代价）。
由于我们处于ms级以下，像malloc这样的事情变得很重要。
我们还能加快什么速度？
要小心，不要在这里过早地进行优化。鉴于OP希望find_path()能够尽快运行，因此我们可以从中获得两个更简单的收益：然后遍历该向量并将其丢弃。基本课程：不要在热路径的内部循环中实现基于堆的数据结构，如果不需要的话。因此，我们可以将该方法更改为get_neighbours()，它需要一个std::vector。这种变化使我们从0.4毫秒增加到0.3毫秒〜25％。这不是很容易理解，并且是一个很好的尝试模式。实际上，仅对26个直接3D邻居调用了此函数，以使foreach_neighbours()都在Callback范围内。因此，我们可以将这些计算静态地缓存在3x3x3数组中，并从内部循环中进行查找：进一步的16％增益达到〜0.24ms。

总的来说，这又给我们带来了1.7倍的增益，我们的整体收益> 8倍。
但是，有了“ hypot cache”，我们进入了微优化领域：停止时间了吗？几乎...
级联改进
通常在进行性能工作时，我们发现我们先前拒绝的优化（因为它们并不重要）在消除其他瓶颈时变得很重要。另外，我们所做的一些更改在当时可能还不错，但是随着我们变得越来越快，它们最终成为了瓶颈。
这个过程也不例外。例如：

原始代码具有vec3::dist和std::hypot。我们将其更改为dx,dy,dz和[-1, 1]（请参见上文）。事实证明，部分地因为它们被相同地索引和访问，我们可以将它们组合为一个dist，其中包含prev和unordered_map。事实证明，这是与旧grid_vector<vec3>相同的结构（尽管语义不同），因此我们可以消除grid_vector<float>。由于采用了grid_vector<vertex>包装，因此获得的空间很小，但是没有速度增益...。
我们将过滤器从函数指针传递到vec3，因为我们使该过滤器成为成员函数。 float非常方便，但是确实有开销。 Lambda几乎一样方便且没有开销（编译器可以直接对其进行访问，并在适当时进行内联）。加速0.24ms降至0.20ms => 16％。

使用grid_node对应用程序进行性能分析，我们发现现在大多数工作都在struct的struct和std::invoke中。这并不奇怪，因为Dijkstra的趋势往往受到数据结构效率的限制。使用“保持推送和延迟删除”方法的优先级队列是一种非常好的方法，但是：我们不需要从所有顶点开始就填充队列。这意味着〜800个无限距离节点位于优先级队列中，并且放慢了O（log n）。如果仅根据需要对邻居进行std::invoke处理，我们将得到相同的结果（对所有开始/结束组合进行测试），并且队列很小。加速：0.20ms => 0.17ms或16％
现在我们没有在perf期间填充队列，我们​​只需要填充pop即可，这可以使用批量构造函数而不是3个嵌套循环完成。所有的push有效消失。加速：0.17ms 0.16ms或6％

因此，我们从OP代码2ms的整体加速=> 0.16ms或12.5x。其中大多数更改也将应用于priority queue代码。
尝试并拒绝优化

预分配支持pop和push的std :: vector（使用版本（4在初始化过程中对元素进行push处理后）。它没有可测量的差异，所以我再次将其取出。后来这变得无关紧要，因为我们决定不批量填充队列。
用所有邻居及其距离预先计算一个邻接矩阵。这大约需要1毫秒，因此它比运行Dijkstra的速度慢。如果我们多次调用Dykstra且网格（即init和grid_vector<vertex>）不经常更改，那可能是值得的。但对于给出的示例，这不值得。另一个示例：如果数据结构可以快速计算，则不要实现它们。

其他重构和最终代码
重构时，我在杰里·科芬（Jerry Coffin）的很好回答的基础上，进行了许多其他“样式”更改。其中包括：


init现在是封装内部的更大类了。
不要使用全局变量，尤其是C#
通过使用std::priority_queue-后来又改成lambda来提高性能。
使用“早期回报”来简单地打包一堆条件
分割相当长的main函数。现在所有功能<15行。

std::move正确性：将emplace_back应用于所有可能的功能。这会触发大量建议的occupied添加，也是如此。

最终代码：
// https://raw.githubusercontent.com/oschonrock/toolbelt/master/os/bch.hpp
#include "os/bch.hpp"
#include <benchmark/benchmark.h>
#include <chrono>
#include <cmath>
#include <fstream>
#include <functional>
#include <iomanip>
#include <iostream>
#include <queue>
#include <stdexcept>
#include <string>
#include <vector>

struct vec3 {
  int x, y, z;

  bool operator==(const vec3& o) const noexcept {
    return x == o.x && y == o.y && z == o.z;
  }
  vec3 operator+(const vec3& o) const noexcept {
    return {x + o.x, y + o.y, z + o.z};
  }

  static vec3 min(const vec3& a, const vec3& b) noexcept {
    return {std::min(a.x, b.x), std::min(a.y, b.y), std::min(a.z, b.z)};
  }

  static vec3 max(const vec3& a, const vec3& b) noexcept {
    return {std::max(a.x, b.x), std::max(a.y, b.y), std::max(a.z, b.z)};
  }

  static float dist(const vec3& a, const vec3& b) noexcept {
    return std::hypot(float(a.x - b.x), float(a.y - b.y), float(a.z - b.z));
  }

  // limited to immediate neighbours: (int)dx,dy,dz: -1 => 1. uses lookup table
  static float fast_dist(const vec3& a, const vec3& b) noexcept {
    return hypot[a.x - b.x + 1][a.y - b.y + 1][a.z - b.z + 1];
  }

  inline static float hypot[3][3][3]{}; // NOLINT

  static bool hypot_init() noexcept {
    for (int dx = -1; dx <= 1; dx++)
      for (int dy = -1; dy <= 1; dy++)
        for (int dz = -1; dz <= 1; dz++) {
          hypot[dx + 1][dy + 1][dz + 1] =
              std::hypot(float(dx), float(dy), float(dz));
        }
    return true;
  }

  inline static bool hypot_initialized = hypot_init();

  friend std::ostream& operator<<(std::ostream& os, const vec3& v3) {
    return os << "[" << v3.x << ", " << v3.y << ", " << v3.z << "]";
  }
};

class grid {
  struct cell; // fwd declaration

public:
  cell& operator[](vec3 const& index) noexcept {
    return cells[index.x * sy_ * sz_ + index.y * sz_ + index.z];
  }

  const cell& operator[](vec3 const& index) const noexcept {
    return cells[index.x * sy_ * sz_ + index.y * sz_ + index.z];
  }

  friend std::istream& operator>>(std::istream& istream, grid& g) {
    // os::bch::Timer t{"load"};
    istream >> g.sx_ >> g.sy_ >> g.sz_;
    g.cells.resize(g.sx_ * g.sy_ * g.sz_);
    istream >> std::boolalpha;
    int i = 0;
    for (int x = 0; x < g.sx_; ++x)
      for (int y = 0; y < g.sy_; ++y)
        for (int z = 0; z < g.sz_; ++z) istream >> g.cells[i++];
    return istream;
  }

  [[nodiscard]] vec3 dims() const { return {sx_, sy_, sz_}; }

  template <typename Filter>
  [[nodiscard]] std::vector<vec3> find_path(const vec3& start, const vec3& end,
                                            const Filter& filter) const {

    if (!filter(start, start) || !filter(end, end))
      throw std::invalid_argument("start and/or end fail cell filter!");

    // previuous coord / finalised dist to start
    // could be added to grid.cells but that would make multi-threaded access
    // very hard
    grid_vector<vertex> vertices(
        dims(), {{-1, -1, -1}, std::numeric_limits<float>::max()});

    find_path_search(start, end, vertices, filter);
    return find_path_extract(end, vertices);
  }

  [[nodiscard]] bool cellFilter(const vec3& from, const vec3& to) const {
    if (from.y != to.y)
      // If the movement is vertical, then perform no diagonal check
      return isFreeFloor(to);

    // Check if all cells we're moving through are floors
    // important when moving diagonally
    auto min = vec3::min(from, to);
    auto max = vec3::max(from, to);

    for (int x = min.x; x <= max.x; ++x)
      for (int z = min.z; z <= max.z; ++z)
        if (!isFreeFloor({x, min.y, z})) return false;
    return true;
  }

private:
  int sx_{}, sy_{}, sz_{};

  struct cell {
    bool occupied;
    bool walkableSurface;

    friend std::istream& operator>>(std::istream& is, cell& c) {
      return is >> c.occupied >> c.walkableSurface;
    }
  };

  std::vector<cell> cells;

  struct vertex {
    vec3  coord;
    float dist;

    bool operator<(vertex const& o) const { return dist > o.dist; } // min-heap!

    friend std::ostream& operator<<(std::ostream& os, const vertex& v) {
      return os << v.coord << ": " << v.dist;
    }
  };

  template <typename T>
  struct grid_vector {
    explicit grid_vector(vec3 dims, const T& defv = T())
        : sx_(dims.x), sy_(dims.y), sz_(dims.z), data_(sx_ * sy_ * sz_, defv) {}

    T& operator[](const vec3& index) {
      return data_[index.x * sy_ * sz_ + index.y * sz_ + index.z];
    }

  private:
    int            sx_, sy_, sz_;
    std::vector<T> data_;
  };

  template <typename Filter>
  void find_path_search(const vec3& start, const vec3& end,
                        grid_vector<vertex>& vertices,
                        const Filter&        filter) const {
    // os::bch::Timer t{"find_path_search"};

    // search queue: not prefilled, because not required and that slows it down
    // current coord / estimated dist to start
    std::priority_queue<vertex> queue;

    vertices[start].dist = 0;
    queue.push({start, 0});

    while (!queue.empty()) {
      auto u = queue.top();
      queue.pop();
      if (u.dist != vertices[u.coord].dist)
        continue;                // lazy remove/skip of old queue value
      if (u.coord == end) break; // we arrived. stop.

      foreach_neighbours(u.coord, [&](const vec3& v) {
        if (filter(u.coord, v)) {
          float new_dist = vertices[u.coord].dist + vec3::fast_dist(u.coord, v);
          if (new_dist < vertices[v].dist) {
            // update min distance to "start", record path "back"
            vertices[v] = {u.coord, new_dist};
            queue.push({v, new_dist}); // leave old one in, to be lazily removed
          }
        }
      });
    }
  }

  static std::vector<vec3> find_path_extract(const vec3&          end,
                                             grid_vector<vertex>& vertices) {
    // os::bch::Timer    t{"find_path_extract"};
    std::vector<vec3> path;
    if (vertices[end].coord.x != -1) {
      vec3 current = end;
      while (current.x != -1) {
        path.push_back(current);
        current = vertices[current].coord;
      }
      std::reverse(path.begin(), path.end());
    }
    return path;
  }

  [[nodiscard]] bool isFreeFloor(const vec3& pos) const {
    return pos.y > 0 && !(*this)[pos].occupied &&
           (*this)[pos + vec3{0, -1, 0}].walkableSurface;
  }

  [[nodiscard]] bool contains(vec3 const& coord) const {
    // clang-format off
    return coord.x >= 0 && coord.x < sx_ &&
           coord.y >= 0 && coord.y < sy_ &&
           coord.z >= 0 && coord.z < sz_;
    // clang-format on
  }

  // faster to loop with callback than to materialise
  // a vector on heap and RVO return it
  template <typename Callback>
  void foreach_neighbours(const vec3& coord, const Callback& callback) const {
    for (int dx = -1; dx <= 1; dx++)
      for (int dy = -1; dy <= 1; dy++)
        for (int dz = -1; dz <= 1; dz++) {
          if (dx == 0 && dy == 0 && dz == 0) continue; // ignore self
          auto new_coord  = coord + vec3{dx, dy, dz};
          bool connected  = abs(dx) + abs(dy) + abs(dz) <= 2;
          bool withinGrid = contains(new_coord);
          if (connected && withinGrid) callback(new_coord);
        }
  }
}; // Grid

int main() {
  std::ifstream gridFile("grid.txt");
  grid          g;
  gridFile >> g;

  vec3 start = {9, 2, 6};
  vec3 end   = {45, 2, 0};

  auto filter = [&g](const vec3& from, const vec3& to) {
    return g.cellFilter(from, to);
  };
  try {
    auto path = g.find_path(start, end, filter);
    std::cout << "best path is " << path.size() << " cells long\n";
    for (auto& e: path) std::cout << e << "\n";
  } catch (std::exception& e) {
    std::cout << "exception: " << e.what() << '\n';
  }
}


评论

\ $ \ begingroup \ $
顺便说一句，std :: hypot不仅仅是一个小巧之处-更精确的是sqrt（a * a + b * b）可能会下溢。
\ $ \ endgroup \ $
– Toby Speight
2月5日7:53