2

我计划创建一个表示严格偏序集的类，并且我假设对其接口建模的最自然方法是作为二元关系。这提供了如下功能：

bool test(elementA, elementB); //return true if elementA < elementB
void set(elementA, elementB); //declare that elementA < elementB
void clear(elementA, elementB); //forget that elementA < elementB

可能的功能如下：

void applyTransitivity(); //if test(a,b) and test(b, c), then set(a, c)
bool checkIrreflexivity(); //return true if for no a, a < a
bool checkAsymmetry(); //return true if for no a and b, a < b and b < a

简单的实现是有一个对列表，使得 (a, b) 表示 a < b。但是，它可能不是最优的。例如，test将是线性时间。也许它可以更好地作为列表的哈希映射来完成。

但是，理想情况下，内存中的表示将根据其性质强制applyTransitivity始终“有效”，并且不允许创建导致自反性或对称性的边。换句话说，数据结构的自由度代表了严格偏序集的自由度。有没有已知的方法可以做到这一点？set或者，更现实地说，是否有一种方法可以检查是否是周期性的，并在每次调用and时保持可摊销和迭代的传递性clear，从而降低执行正确性的成本。有工作实施吗？

4

1 回答 1

1

好吧，我们来谈谈实现裸机刮削微效率，你可以选择你想去多深的那个深渊。在这个架构级别，没有像哈希映射和列表这样的数据结构，甚至没有数据类型，只有内存中的位和字节。

顺便说一句，通过查看 DAG 的常见表示，您还可以在此处找到有关表示的大量信息。然而，大多数常见的代表都是为了方便而不是效率而设计的。

在这里，我们希望将数据a与邻接数据融合到单个内存块中。因此，您想存储与自己的内存块相关的项目的“列表”，以便a我们a's可以潜在地访问单个缓存行中的a所有元素a（如果这些相关元素可能也适合相同的缓存行，但这是一个 NP 难题）。

您可以通过将 32 位索引存储在a. 我们可以像这样对这样的对象进行建模，如果我们再高一点并使用 C 来进行示范：

struct Node
{
    // node data
    ...
    int links[]; // variable-length struct
};

这使得Node可变长度结构的大小甚至地址都发生变化，因此我们需要额外的间接级别来获得稳定性并避免失效，例如索引的索引（如果您控制内存分配器/数组并且它是纯粹连续的)，或指向指针的索引（或某些语言中的引用）。

这使得您的测试函数仍然涉及线性时间搜索，但与 相关的元素数量是线性的a，而不是元素总数。因为我们使用了可变长度结构，a它的邻居索引可能适合单个缓存行，而且很可能a已经在缓存中，只是为了进行查询。

a它类似于您对存储列表的哈希映射的基本想法，但没有列表开销的爆炸式增长，也没有哈希查找（这可能是恒定时间，但不如从同一个内存块访问连接快） . 最重要的是，它对缓存更加友好，这通常会产生几个周期和数百个周期之间的差异。

现在这意味着您仍然必须卷起袖子并自己检查诸如循环之类的事情。如果您想要一个更直接、更方便地对问题建模的数据结构，您会发现更适合围绕有向边的形式化的图数据结构。但是，这些比它们有效的要方便得多。

如果您需要容器是通用的并且a可以是任何给定的类型 T，那么您总是可以包装它（现在使用 C++）：

template <class T>
struct Node
{
    T node_data;
    int links[1]; // VLS, not necessarily actually storing 1 element
};

并且仍然以这种方式将这一切融合到一个内存块中。我们需要在此处放置 new 以保留那些 C++ 对象语义，并可能注意此处的对齐。

传递性检查总是涉及某种搜索（广度优先或深度优先）。我认为没有任何代表可以避免这种情况，除非您想记忆/缓存潜在的大规模传递数据爆炸。

在这一点上，如果您想深入深渊并拥有一个很难维护和理解的解决方案，那么您应该很快就会有一些东西。不幸的是，我发现这并没有像拥有一辆跑得非常快的汽车那样给女士们留下深刻的印象，但它可以让你的软件运行得非常非常快。

于 2015-05-18T09:27:15.457 回答