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

回答

相關問題