具有许多已定义子集的有序集的数据结构; 以相同的顺序检索子集

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)。

选择与时间集对应的列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)时间。然后从该数组中删除它，并从矩阵中删除该索引处的行。

不要简单地删除，只需将它们标记为失效即可。当失效的列/行达到阈值数量时，您可以进行合并。同样，首先为阵列提供高容量。不过，现代实现应该自动执行此操作。