>主集中项目的顺序快速变化(子集保持主集的顺序)
>可以定义和检索许多子集
>主集中的成员数量迅速增长
>经常在子集中添加和删除成员
>必须允许有效地合并任意数量的子集
理想情况下,性能会偏向于检索任何子集(或合并子集)的前N个项,并且存储将在内存中(并且最终可能在磁盘上持久)
我是这个论坛的新成员,我希望你没有忘记这个老问题:)解
将主集存储在索引数据结构中 – 例如数组(或arraylist,如果您的库支持它).假设您可以将id与每个集合关联(如果没有,那么您如何知道要检索哪个集合？).因此,我们现在需要一种方法来找出阵列中哪些元素参与该集合以及哪些元素不参与.
使用矩阵(n x m),其中n是数组中元素的数量,m是初始的集合数. i引用行索引,j引用列索引.
A[i][j] = 0 if ith element is not in jth set A[i][j] = 1 if ith element is in jth set
不要使用简单的二维数组,转到ArrayList< ArrayList>. Java / C#/ C支持这样的通用构造,但在其他语言(如Perl)中这样做不应该非常困难.在C#中,您甚至可以使用DataTable.
是时候添加一套了
您可以在O(n)时间内添加新集.只需为该集添加新列,并为该列设置适当的行为1.只要原始数组已排序,就不需要对此集进行排序.
是时候添加新元素了
在简单排序的数组中,插入的时间是O(log n).在我们的例子中,我们将首先向数组添加元素(在我们添加元素的任何索引处,矩阵也将在该索引处获得全0行).然后,如果元素属于集合,我们将该列中的条目设置为1.这样,最坏情况运行时变为O(log n)O(m).
是时候从集合中获取前N个元素了
在O(1)时间内拾取与该集合对应的列,然后选择前面的N个条目1.这将是线性的.
合并两套的时间
假设我们将j1和j2处的集合合并为j3处的第三集.
for (int i = 0; i < n - 1; i++) {
A[i][j3] = A[i][j1] | A[i][j2];
}
这又是线性的.
是时候删除一个元素了
首先在主数组中找到元素 – 这需要O(log n)时间.然后从该数组中删除它,并从矩阵中删除该索引处的行.
从阵列中有效删除
不要简单地删除,只是将它们标记为已解散.在阈值数量的已解散的列/行后,您可以合并.同样,最初从阵列的高容量开始.现代实现应该自动执行此操作.