C++ 中编译时拓扑排序超过递归深度

问题描述 投票：0回答：1

你好:)

我正在使用 C++ 模板元编程实现编译时拓扑排序算法。该算法旨在对游戏引擎中不同系统之间的依赖关系图进行排序，但它也可用于对任何有向无环图 (DAG) 进行排序。

该图表示为 SystemNode 对象的元组，每个对象代表一个系统及其依赖项。该算法以每个节点出现在排序列表中其依赖项之前的方式对这些节点进行排序。

故障

  1. GraphWithDegrees_t：这是算法的起点。它采用 

    SystemNode
    对象的元组，并将每个节点转换为 
    NodeWithDegree
    对象，该对象是一个还包含其度数（依赖于它的节点数）的节点。每个节点的度数由 
    CountDependencies
    结构体计算。

  2. 拓扑排序：这是算法的主要部分。它是一个执行拓扑排序的递归结构。其工作原理如下：

    • 提取所有度数为零的节点（即没有其他节点依赖的节点）。这些节点被添加到 

      ExtractedSystems
      元组中，该元组保存已排序的节点。

    • 收集零度节点的依赖关系。这样做是为了知道下一步需要减少哪些节点的度数。

    • 从原始元组中删除零度节点。

    • 减少依赖于已删除节点的任何节点的度数。这是通过检查节点是否位于上一步中收集的依赖项中来完成的。

    • 使用更新的元组和 

      TopologicalSort
      元组递归调用 
      ExtractedSystems
      。

    • 当元组为空时（即所有节点都已排序），递归结束并返回

      ExtractedSystems
      元组作为结果。

  3. ExtractZeroDegree_t 和RemoveZeroDegree_t：这些结构用于从元组中提取和删除零度节点。它们的工作原理是递归地迭代元组并根据其度数向新元组添加/删除节点。

  4. DecrementDegrees_t：该结构用于减少依赖于给定节点集的节点的度数。它的工作原理是递归地迭代元组并减少 

    Dependencies
    元组中任何节点的度数。

  5. AddSystemsToTuple_t：该结构用于将零度节点添加到

    ExtractedSystems
    元组中。它的工作原理是递归迭代零度节点的元组并将每个节点添加到 
    ExtractedSystems
    元组。

问题

我面临的问题是该算法对于最多 15 种类型可以正常工作，但是对于 16 种类型，它超出了最大递归深度。我相信递归深度应该是 O(M)，其中 M 是最大度数，所以我不确定为什么 16 种类型会失败。

我的问题是：

  1. 为什么这个算法会超过最大递归深度16 类型？
  2. 如何修改它以处理更多类型？
  3. 考虑到这种方法的复杂性，是否建议 采用更简单的方法来达到相同的结果？如果是这样，什么 可以推荐替代方案吗？

请放心，我是新来的:)

源代码

您还可以在此处重现该问题：https://godbolt.org/z/T8cohdasr。

#include <tuple>
#include <iostream>
#include <type_traits>
#include <string_view>

template<typename SystemType, typename... DependencyTypes>
class SystemNode;

template<typename SystemType, typename... DependencyTypes>
class SystemNode<SystemType, std::tuple<DependencyTypes...>>
{
public:
    using system = SystemType;
    using dependencies = std::tuple<DependencyTypes...>;
};

template <typename System, typename Dependencies, size_t Degree>
struct NodeWithDegree 
{
    using system = System;
    using dependencies = Dependencies;
    static constexpr size_t degree = Degree;
};

template <typename Node, size_t Degree>
struct ToNodeWithDegree
{
    using type = NodeWithDegree<typename Node::system, typename Node::dependencies, Degree>;
};

template <typename Node, size_t Degree>
using ToNodeWithDegree_t = typename ToNodeWithDegree<Node, Degree>::type;

template <typename T, typename Tuple>
struct Contains;

template <typename T, typename... Us>
struct Contains<T, std::tuple<Us...>> : std::disjunction<std::is_same<T, Us>...> {};

template <typename T, typename... Us>
constexpr size_t Contains_v = Contains<T, Us...>::value;

template <typename Node, typename Nodes>
struct CountDependencies;

template <typename Node, typename First, typename... Rest>
struct CountDependencies<Node, std::tuple<First, Rest...>>
{
    static constexpr size_t value = 
        Contains_v<typename Node::system, typename First::dependencies> 
        + CountDependencies<Node, std::tuple<Rest...>>::value;
};

template <typename Node>
struct CountDependencies<Node, std::tuple<>>
{
    static constexpr size_t value = 0;
};

template <typename... Nodes>
struct GraphWithDegrees
{
    template<typename Node>
    static constexpr size_t CountDependencies_v = CountDependencies<Node, std::tuple<Nodes...>>::value;

    using type = std::tuple<ToNodeWithDegree_t<Nodes, CountDependencies_v<Nodes>>...>;
};

template <typename... Nodes>
using GraphWithDegrees_t = typename GraphWithDegrees<Nodes...>::type;

template <typename NodesWithDegrees, typename ZeroDegreeNodes = std::tuple<>>
struct ExtractZeroDegree;

template <typename FirstNode, typename... RestNodes, typename... ZeroDegreeNodes>
struct ExtractZeroDegree<std::tuple<FirstNode, RestNodes...>, std::tuple<ZeroDegreeNodes...>>
{
    using type = std::conditional_t<
        FirstNode::degree == 0,
        typename ExtractZeroDegree<std::tuple<RestNodes...>, std::tuple<ZeroDegreeNodes..., FirstNode>>::type,
        typename ExtractZeroDegree<std::tuple<RestNodes...>, std::tuple<ZeroDegreeNodes...>>::type
    >;
};

template <typename... ZeroDegreeNodes>
struct ExtractZeroDegree<std::tuple<>, std::tuple<ZeroDegreeNodes...>>
{
    using type = std::tuple<ZeroDegreeNodes...>; 
};

template <typename NodesWithDegrees, typename ZeroDegreeNodes = std::tuple<>>
using ExtractZeroDegree_t = typename ExtractZeroDegree<NodesWithDegrees, ZeroDegreeNodes>::type;

template <typename NodesWithDegrees, typename NonZeroDegreeNodes = std::tuple<>>
struct RemoveZeroDegree;

template <typename FirstNode, typename... RestNodes, typename... NonZeroDegreeNodes>
struct RemoveZeroDegree<std::tuple<FirstNode, RestNodes...>, std::tuple<NonZeroDegreeNodes...>>
{
    using type = std::conditional_t<
        FirstNode::degree == 0,
        typename RemoveZeroDegree<std::tuple<RestNodes...>, std::tuple<NonZeroDegreeNodes...>>::type,
        typename RemoveZeroDegree<std::tuple<RestNodes...>, std::tuple<NonZeroDegreeNodes..., FirstNode>>::type
    >;
};

template <typename... NonZeroDegreeNodes>
struct RemoveZeroDegree<std::tuple<>, std::tuple<NonZeroDegreeNodes...>>
{
    using type = std::tuple<NonZeroDegreeNodes...>; 
};

template <typename NodesWithDegrees, typename NonZeroDegreeNodes = std::tuple<>>
using RemoveZeroDegree_t = typename RemoveZeroDegree<NodesWithDegrees, NonZeroDegreeNodes>::type;

template <typename T, typename Tuple>
struct Prepend;

template <typename T, typename... Ts>
struct Prepend<T, std::tuple<Ts...>>
{
    using type = std::tuple<T, Ts...>;
};

template <typename T, typename Tuple>
using Prepend_t = typename Prepend<T, Tuple>::type;

template <typename T, typename Tuple>
struct AddUnique;

template <typename T>
struct AddUnique<T, std::tuple<>>
{
    using type = std::tuple<T>;
};

template <typename T, typename First, typename... Rest>
struct AddUnique<T, std::tuple<First, Rest...>>
{
    using type = std::conditional_t<
        std::is_same_v<T, First>,
        std::tuple<First, Rest...>,
        Prepend_t<First, typename AddUnique<T, std::tuple<Rest...>>::type>
    >;
};

template <typename T, typename Tuple>
using AddUnique_t = typename AddUnique<T, Tuple>::type;

template <typename Tuple1, typename Tuple2>
struct AddUniqueElements;

template <typename First, typename... Rest, typename Tuple2>
struct AddUniqueElements<std::tuple<First, Rest...>, Tuple2>
{
    using type = typename AddUniqueElements<std::tuple<Rest...>, AddUnique_t<First, Tuple2>>::type;
};

template <typename Tuple2>
struct AddUniqueElements<std::tuple<>, Tuple2>
{
    using type = Tuple2;
};

template <typename Tuple1, typename Tuple2>
using AddUniqueElements_t = typename AddUniqueElements<Tuple1, Tuple2>::type;

template <typename Nodes>
struct CollectDependencies;

template <typename FirstNode, typename... RestNodes>
struct CollectDependencies<std::tuple<FirstNode, RestNodes...>>
{
    using type = AddUniqueElements_t<
        typename FirstNode::dependencies,
        typename CollectDependencies<std::tuple<RestNodes...>>::type
    >;
};

template <>
struct CollectDependencies<std::tuple<>>
{
    using type = std::tuple<>;
};

template <typename... Nodes>
using CollectDependencies_t = typename CollectDependencies<Nodes...>::type;

template <typename NodesWithDegrees, typename Dependencies>
struct DecrementDegrees;

template <typename FirstNode, typename... RestNodes, typename... Dependencies>
struct DecrementDegrees<std::tuple<FirstNode, RestNodes...>, std::tuple<Dependencies...>>
{
    using type = std::conditional_t<
        Contains_v<typename FirstNode::system, std::tuple<Dependencies...>>,
        Prepend_t<
            NodeWithDegree<
                typename FirstNode::system, 
                typename FirstNode::dependencies, 
                FirstNode::degree - 1
            >, 
            typename DecrementDegrees<std::tuple<RestNodes...>, std::tuple<Dependencies...>>::type
        >,
        Prepend_t<
            FirstNode, 
            typename DecrementDegrees<std::tuple<RestNodes...>, std::tuple<Dependencies...>>::type
        >
    >;
};

template <typename... Dependencies>
struct DecrementDegrees<std::tuple<>, std::tuple<Dependencies...>>
{
    using type = std::tuple<>; 
};

template <typename NodesWithDegrees, typename Dependencies>
using DecrementDegrees_t = typename DecrementDegrees<NodesWithDegrees, Dependencies>::type;

template <typename NodesWithDegrees, typename ExtractedSystems>
struct AddSystemsToTuple;

template <typename FirstNode, typename... RestNodes, typename... ExtractedSystems>
struct AddSystemsToTuple<std::tuple<FirstNode, RestNodes...>, std::tuple<ExtractedSystems...>>
{
    using nextTuple = std::tuple<RestNodes...>;
    using newExtractedSystems = std::tuple<typename FirstNode::system, ExtractedSystems...>;
    using type = typename AddSystemsToTuple<nextTuple, newExtractedSystems>::type;
};

template <typename... ExtractedSystems>
struct AddSystemsToTuple<std::tuple<>, std::tuple<ExtractedSystems...>>
{
    using type = std::tuple<ExtractedSystems...>;
};

template <typename NodesWithDegrees, typename ExtractedSystems>
using AddSystemsToTuple_t = typename AddSystemsToTuple<NodesWithDegrees, ExtractedSystems>::type;

template <typename SystemsWithDegrees, typename ExtractedSystems = std::tuple<>>
struct TopologicalSort
{
    using ZeroDegreeSystems = ExtractZeroDegree_t<SystemsWithDegrees>;
    using NewExtractedSystems = AddSystemsToTuple_t<ZeroDegreeSystems, ExtractedSystems>;
    using Dependencies = CollectDependencies_t<ZeroDegreeSystems>;
    using RemainingSystems = RemoveZeroDegree_t<SystemsWithDegrees>;
    using DecrementRemainingSystems = DecrementDegrees_t<RemainingSystems, Dependencies>;
    using type = typename TopologicalSort<DecrementRemainingSystems, NewExtractedSystems>::type;
};

template <typename ExtractedSystems>
struct TopologicalSort<std::tuple<>, ExtractedSystems>
{
    using type = ExtractedSystems;
};

template <typename SystemsWithDegrees, typename ExtractedSystems = std::tuple<>>
using TopologicalSort_t = typename TopologicalSort<SystemsWithDegrees, ExtractedSystems>::type;

template <typename T>
constexpr auto type_name() noexcept {
    std::string_view name = "Error: unsupported compiler", prefix, suffix;
#ifdef __clang__
    name = __PRETTY_FUNCTION__;
    prefix = "auto type_name() [T = ";
    suffix = "]";
#elif defined(__GNUC__)
    name = __PRETTY_FUNCTION__;
    prefix = "constexpr auto type_name() [with T = ";
    suffix = "]";
#elif defined(_MSC_VER)
    name = __FUNCSIG__;
    prefix = "auto __cdecl type_name<";
    suffix = ">(void) noexcept";
#else
    static_assert(false, "Unsupported compiler!");
#endif
    name.remove_prefix(prefix.size());
    name.remove_suffix(suffix.size());
    return name;
}

template <typename T>
void printSystem()
{
    std::cout << type_name<T>() << '\n';
}

struct System1 {};
struct System2 {};
struct System3 {};
struct System4 {};
struct System5 {};
struct System6 {};
struct System7 {};
struct System8 {};
struct System9 {};
struct System10 {};
struct System11 {};
struct System12 {};
struct System13 {};
struct System14 {};
struct System15 {};
struct System16 {};
struct System17 {};
struct System18 {};
struct System19 {};
struct System20 {};

using Node1 = SystemNode<System1, std::tuple<>>;
using Node2 = SystemNode<System2, std::tuple<System1>>;
using Node3 = SystemNode<System3, std::tuple<System2>>;
using Node4 = SystemNode<System4, std::tuple<System3>>;
using Node5 = SystemNode<System5, std::tuple<System4>>;
using Node6 = SystemNode<System6, std::tuple<System5>>;
using Node7 = SystemNode<System7, std::tuple<System6>>;
using Node8 = SystemNode<System8, std::tuple<System7>>;
using Node9 = SystemNode<System9, std::tuple<System8>>;
using Node10 = SystemNode<System10, std::tuple<System9>>;
using Node11 = SystemNode<System11, std::tuple<System10>>;
using Node12 = SystemNode<System12, std::tuple<System11>>;
using Node13 = SystemNode<System13, std::tuple<System12>>;
using Node14 = SystemNode<System14, std::tuple<System13>>;
using Node15 = SystemNode<System15, std::tuple<System14>>;
using Node16 = SystemNode<System16, std::tuple<System15>>;
using Node17 = SystemNode<System17, std::tuple<System16>>;
using Node18 = SystemNode<System18, std::tuple<System17>>;
using Node19 = SystemNode<System19, std::tuple<System18>>;
using Node20 = SystemNode<System20, std::tuple<System19>>;

int main()
{
    using tuple = GraphWithDegrees_t<
        Node10, Node9, Node8, Node7, Node6, Node5, Node4, Node3, Node2, Node1, 
        Node11, Node12, Node13, Node14, Node15, Node16, Node17, Node18, Node19, Node20
    >;
    using SortedTuple = TopologicalSort_t<tuple>;
    printSystem<SortedTuple>();
    return 0;
}

输出：

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc```
c++ algorithm sorting templates template-meta-programming
1个回答
0
投票

您的编译器存在内部错误/内存不足情况。它不是某种任意嵌套模板实例化限制。

我能够在本地机器上编译出具有 20 个节点的版本。使用 gcc 大约需要 20 秒，使用 clang 大约需要 30 秒。

然后我将节点数量增加到 50 个。编译使我的计算机（按今天的标准来说确实不是很强大）变得缓慢，大约 20 分钟后我杀死了它。

因此，在实践中，将模板元编程推进那么远可能不是一个好主意。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.