如何表示二元关系

Question

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

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 始终为 "in effect"，并且不允许创建导致反身性或对称性的边。换句话说，数据结构的自由度代表了一个严格偏序集的自由度。有没有已知的方法来做到这一点？或者，更现实地说，是否有一种方法可以检查循环性，并在每次调用 set 和 clear 时保持传递性和迭代性，从而降低执行正确性的成本。有有效的实施吗？

Answer 1

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

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

在这里，我们希望 a 的数据与该邻接数据融合到一个内存块中。所以你想在 a's 自己的内存块中存储 'list'，可以说，与 a 有关系的项目，这样我们就可以潜在地访问 a 和所有单个缓存行中与 a 相关的元素（如果这些相关元素也可能适合同一缓存行，则加分，但这是一个 NP-hard 问题）。

您可以通过在 a 中存储 32 位索引来做到这一点。如果我们走得更高一点并使用 C 作为示例，我们可以像这样对此类对象进行建模：

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

这使得 Node 成为一个可变长度结构，其大小甚至地址都可能发生变化，因此我们需要一个额外的间接级别来获得稳定性并避免失效，例如索引到索引（如果您控制内存 allocator/array 并且它是完全连续的），或指针的索引（或某些语言中的引用）。

这使得您的测试函数仍然涉及线性时间搜索，但与 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++ 对象语义，并可能注意此处的对齐方式。

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

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

如何表示二元关系

How to represent a binary relation

optimization

data-structures

poset