Поиск пути Dijkstra в C # в 15 раз медленнее, чем версия C ++

Я реализую алгоритм Дейкстры с приоритетной очередью для игры, которую я разрабатываю в Unity с C #. Я немного разочаровался в производительности, поэтому решил перенести код на C ++ и посмотреть, была ли производительность связана с языком или с самим алгоритмом. Поиск путей выполняет поиск через трехмерную сетку и выбирает определенные края /соседи на основе некоторых дополнительных критериев (фильтр ячейки).

Проблема состоит в том, что эта сетка содержит только 3000 ячеек, а алгоритм C # занимает 38 мс, чтобы найти путь. Версия C ++ занимает всего 2 мс, чтобы сделать то же самое!

Ниже приведены два исходных файла алгоритма, и мне интересно, может ли кто-то, кто сталкивался с C #, указать, что я сделал что-то ужасно неэффективное или если C # здесь только медленнее. Версия C # сохраняет сетку в виде многомерного массива, а версия C ++ имитирует ее с помощью дополнительной функции get_index, которая вычисляет индекс в вектор, используя координаты x, y и z. Я имитирую очередь приоритетов в C # с помощью SortedSet со специальным узлом очереди, содержащим как значение, так и значение приоритета (dist). Оба алгоритма имитируют обновление очереди приоритетов, просто добавив новое значение, которое делает недействительным старый. Это делается путем сохранения приоритетов в хэш-таблице dist.

С #:

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");
        }
    }
}

С ++

#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 .

172 голоса | спросил Overv 16 Jam1000000amMon, 16 Jan 2017 06:06:39 +030017 2017, 06:06:39

4 ответа


273

Прежде всего, вы должны запустить метод FindPath пару раз перед измерением, чтобы дать C # runtime возможность оптимизировать код.

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

Выполнение этого времени сокращает время до 17 мс на моей машине (начиная с 38 мс).

Запуск кода в профилировщике показывает, что более 70% времени тратится на методы Dictionary и SortedSet. Для JIT, чтобы оптимизировать те, которые вы должны предоставить ему необходимую информацию для своих типов ключей, в противном случае он будет возвращаться к отражениям во время выполнения и вызовам виртуальных методов.

Любая структура, которая используется как Key в Dictionary, должна реализовывать интерфейс IEquatable<T>. Также GetHashCode и Equals должен быть переопределен (компилятор даже предупреждает об этом).

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;
    }
}

SortedSet, скорее всего, нужен интерфейс IComparable<T>, который уже имеет QueueNode, но его следует изменить на общий.

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

После этих изменений FindPath требуется всего 4 мс.

Мы также можем оптимизировать словари, перейдя в пользовательский IEqualityComparer и исключив вызовы int.GetHashCode().

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);

    [...]
}

Последний код занимает около 2,8 мс для FindPath.

В заключение всегда используйте правильные общие интерфейсы для структур, которые используются в коллекциях. Это позволяет JIT фактически оптимизировать код.

Полезные ссылки

Конечный код

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

namespace PathFinding.NET {
    struct Vec3 : IComparable<Vec3>, IEquatable<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(Vec3 other) {
            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);
            }
        }

        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;
        }
    }

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

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

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

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

    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;
        }
    }

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

        private static List<Vec3> GetNeighbours(Vec3 cell, List<Vec3> neighbours) {
            neighbours.Clear();

            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
            Vec3Comparer comparer = new Vec3Comparer();
            var dist = new Dictionary<Vec3, float>(comparer);
            var prev = new Dictionary<Vec3, Vec3?>(comparer);

            // 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));

            List<Vec3> neighbours = new List<Vec3>();

            // 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, neighbours)) {
                    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);

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

            var timer = new System.Diagnostics.Stopwatch();

            timer.Start();
            var path = FindPath(start, end, CellFilter);
            timer.Stop();

            Console.WriteLine("best path is " + path.Count + " cells long");
            Console.WriteLine("path finding took " + timer.Elapsed.TotalMilliseconds + " ms");
        }
    }
}
ответил mordecai154 16 Jpm1000000pmMon, 16 Jan 2017 14:37:14 +030017 2017, 14:37:14
41

На данный момент я игнорирую код 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, я думаю, что попытаюсь инкапсулировать его критерии сравнения с довольно небольшим переписыванием:

struct queue_node {
    vec3 value;
    float dist;

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

С этим мы можем немного упростить priority_queue, чтобы стать:

std::priority_queue<queue_node> Q;

Нейминг

Я думаю, что некоторые из названий могут быть улучшены. Наиболее очевидным будет cellFilter - он имеет тенденцию указывать, что нас интересует, соответствует ли клетка определенному набору критериев, но не сообщает нам ничего о критериях, которые мы хотим, чтобы они встречались.

Timing

Возможно, это потому, что я потратил впустую потратил слишком много времени, отвечая на вопросы как здесь, так и на Stack Overflow, но мне удобнее иметь функцию синхронизации, которая позволяет мне использовать функцию без переписывая код синхронизации каждый раз. Я использую это:

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;
}

Таким образом, ваш код будет выглядеть примерно так:

#include "timer"

// ...

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

Использование endl

Я бы рекомендовал (никогда) использовать std::endl. Наряду с введением символа новой строки он очищает поток. Это редко бывает желательным. В редких случаях, когда это действительно желательно, я думаю, что лучше сделать это явным, с кодом вроде:

std::cout << '\n' << std::flush;

В этом конкретном случае это не будет иметь существенного значения, но это по-прежнему плохая привычка, которая может замедлить код в 10 раз или около того для небольшого реального выигрыша.

Конечный код

(Для простоты я включил времяcode inline вместо использования отдельного заголовка, как обычно.)

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

struct vec3 {
    int x, y, 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;

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

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;

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 = grid.contains(coord); 

                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;

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

    std::priority_queue<queue_node> Q;

    for (int x = 0; x < grid.sx; x++) {
        for (int y = 0; y < grid.sy; y++) {
            for (int z = 0; z < grid.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) {
    return pos.y > 0 && !grid[pos].occupied && grid[(pos + vec3{ 0, -1, 0 })].walkableSurface;
}

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);
    }
}

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;
}

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

    gridFile >> grid;

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

    try {
        auto path = timer(find_path, "Find Path", start, end, cellFilter);
        std::cout << "best path is " << path.size() << " cells long\n";
    } catch (std::exception& e) {
        std::cout << "exception: " << e.what() << '\n';
    }

    return 0;
}
ответил Jerry Coffin 16 Jam1000000amMon, 16 Jan 2017 10:25:17 +030017 2017, 10:25:17
9

Многомерный массив может быть слабостью реализации C #. Попробуйте использовать неровные массивы, которые быстрее, но не так просто.

Подробнее об этом можно узнать в Каковы различия между многомерным массивом и массивом массивов в C #? на SO. В этом ответе сравниваются обе системы массивов.

РЕДАКТИРОВАТЬ: Я сам тестировал это, и разница едва ли можно измерить. Похоже, они уже исправили его.


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 #, вы должны использовать профилировщик.

ответил t3chb0t 16 Jam1000000amMon, 16 Jan 2017 10:23:53 +030017 2017, 10:23:53
4

Худшая проблема - это, вероятно, использование коллекции SortedSet. По моему опыту, коллекции Sorted* редко бывают то, что вы действительно хотите, а производительность сомнительна.

Производительность может быть значительно улучшена, если все соседи соты имеют единичное расстояние до ячейки (или небольшое целое расстояние). Затем у вас есть очередь frontiers , которая может быть обработана /обновлена ​​быстро и просто. Ниже приведен пример реализации, называемый DelayQueue: Ark.Collections.DelayQueue .

ответил Ark-kun 18 Jam1000000amWed, 18 Jan 2017 06:25:06 +030017 2017, 06:25:06

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132