Set与Multiset

我想将<Object A, Relation R, Object B>类型的不同关系存储在一个集合或多个集合中（约100到1000个）。我希望能够搜索A和(A,R)，但不会为(A,R,B)（并且将只有少数（< 5）与A和R相同的关系，所以线性搜索如果罚款那么）。Set与Multiset

是更好地存储在一个集中的关系（由A，R和B订购）或将它们存储在由A和R订购了多集？我已经研究了哈希表，但是他们的迭代没有（有序）集迭代那么快，并且模式匹配也需要很多迭代。（这将不得不寻找曾经找迭代开始，然后重复，直到与同一对象的所有关系都做了。）

感谢，拉格纳

来源

2013-08-25 Ragnar

如何将它们存储在向量中？对于1000个元素，我的钱就是最快的实现。 –

程序会经常搜索集合/向量，因为它必须在不同的关系上进行大量的模式匹配（程序是一个几何问题求解器，它必须找到它可以应用某个定理的情况） – Ragnar

@Ragnar：问题并不在于搜索的频率如何，而是当地图的复杂结构与矢量的简单结构相得益彰时。它在支付使用地图之前的元素数量往往远高于人们的预期。 –

从评论我了解，你有查找精确匹配，无论是A还是对（A，R）。

如果这是正确的，你可以做的最好的事情是使用两个哈希表：一个用A作为键，另一个用（A，R）作为键。关系本身可以存储在一个未排序的向量中，其中索引被插入到两个散列表中。这是您查找任务时只有O（1）复杂性的唯一方法。

对于性能至关重要的是您有两个独立的索引结构：如果您只使用A作为键，您将获得对象的列表，您必须在查找（A，R）时寻找合适的R的对象列表，对。在相反的情况下，如果您只有（A，R）键，您将无法仅在O（1）时间内查看某个A。

来源

2013-08-25 20:03:37 cmaster

我从来没有使用过散列表，但它可能还清了解它们，因为O（1）查找可能会加速程序。 – Ragnar

是不是只能使用（A，R）键并按A排序，然后按（enum）R排序并搜索（A，0）和（A，255）的下界？ – Ragnar

不，在O（1）时间内不可能，因为您必须能够查找不存在的（A，R）对的位置。这不能用散列表完成。使用其他索引结构（如二叉树或排序数组中的二进制搜索）是可能的，但这意味着O（log N）时间复杂度。 – cmaster

回答

相关问题