假设我们有m个有序集,我们想找到它们的交集。
对于有序集我们应该使用哪些数据结构,哪种算法最有效?
同样的问题:
Algorithm for N-way merge
看来文学作品是巨大的。因此,一个更好的问题是:
有哪些好的实现?
最佳答案
可以创建与父节点链接的二叉树,并实现经典的交并算法:
将iterA
设置为树的最左边(最小)节点(即,从最左边的树枝下降到叶子)。
将iterB
设置为有序集的第一个(最小)节点(如果它是用有序数组实现的,或者如果是树,则设置为最左边的节点)。
按iterA
和iterB
所指项目的比较进行分支
如果更低:联合前进的收益项目iterA
如果等于:屈服并集项和相交项,并同时推进iterA
和itemB
如果大于:屈服于联合和前进项iterB
重复,直到其中一个迭代器无法前进
从其他迭代器访问的其余项作为联合项产生
二叉树迭代器的进展:
如果当前节点有右子节点,则尽可能下降到该节点的最左侧子节点。交出那件东西。
如果节点有父节点在其上提升并在我们从右子节点提升时重复该操作。交出那件东西。
否则:树的所有项都已生成(集合结束)。
更新:
如果您知道您的有序集(walked byiterB
)比树小得多,则可以使用更复杂的算法进行相交:
最初将iterB
设置为有序集的开始(较低的值)。
将iterA
设置为值iterB
的最小上限节点。
按iterA
和iterB
所指项目的比较进行分支
如果等于:交集的屈服项。
前进到下一个值。
从电流itemB
开始,将iterA
前进到itemB
处的最小值上限。
重复此操作,直到itemA
传递所有有序集合的项。
其中,从特定节点前进到最小上界是:
如果当前节点的值小于目标值
通过遍历每个节点的右子节点来查找右子节点的上界
如果该分支的最右节点低于目标节点:从右子节点移动时上升到父节点,然后从该节点重新启动。
从我们找到上限的节点
查找最左边的大多数子项,其值小于目标值
如果找不到:该分支的最左边的叶是最小上界
否则从该节点重新启动(更准确地说,将使用子算法遍历最左和最右的节点以缩小边界)。
搜索范围的主要思想是缩小上下限(“-”是忽略的节点,“…”是新的搜索范围):
for B < X < A
U
/ \-
L
-/ \...
for A < X < B
L
-/ \
U
.../ \-
关于database - 内存中m个有序集相交的有效算法?,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/13570026/