sorting - 具有许多已定义子集的有序集合的数据结构；按相同顺序检索子集

Question

我正在寻找一种存储有序列表/项目集的有效方法，其中:

主集合中项目的顺序变化很快(子集维护主集合的顺序)

可以定义和检索许多子集

主集成员快速增长

成员经常被添加到子集中或从子集中删除

必须允许对任意数量的子集进行某种有效的合并

理想情况下，性能将偏向于检索任何子集(或合并子集)的前 N ​​个项目，并且存储将在内存中(并可能最终持久保存在磁盘上)

Answer 1

我是这个论坛的新成员，希望你没有忘记这个老问题:)
解决方案
将主集存储在索引数据结构中——例如数组(或数组列表，如果您的库支持它)。假设您可以将 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)时间。然后从该数组中删除它并从矩阵中删除该索引处的行。
从数组中有效删除
不要简单地删除，只需将它们标记为已失效。根据已失效的列/行的阈值数量，您可以合并。同样，最初为阵列提供高容量。不过，现代实现应该自动执行此操作。