4

我试图通过例子来解释：

想象一个编号元素的列表 E = [elem0, elem1, elem2, ...]。

一个索引集现在可以是 {42, 66, 128} 引用 E 中的元素。这个集合中的顺序并不重要，所以 {42, 66, 128} == {66, 128, 42}，但每个元素都是在任何给定的索引集中最多一次（所以它是一个实际的集合）。

我现在想要的是一个节省空间的数据结构，它给了我另一个有序列表 M，其中包含引用 E 中元素的索引集。 M 中的每个索引集只会出现一次（因此 M 在这方面是一个集合）但 M 必须本身是可索引的（所以 M 在这个意义上是一个 List ，因此精确的索引并不重要）。如有必要，可以强制索引集包含相同数量的元素。

例如，M 可能看起来像：

0: {42, 66, 128}
1: {42, 66, 9999}
2: {1, 66, 9999}

我现在可以执行以下操作：

for(i in M[2]) { element = E[i]; /* do something with E[1],E[66],and E[9999] */ }

您可能会看到这是怎么回事：您现在可能有另一个映射 M2，它是指向 M 的有序集合列表，最终指向 E 中的元素。

正如您在此示例中所见，索引集可能相对相似（M[0] 和 M[1] 共享前两个条目，M[1] 和 M[2] 共享后两个）这让我认为必须比使用集合数组的天真方式更有效。但是，我可能无法提出保证良好“共享”的索引条目的良好全局排序。

我可以想到任何东西，从将 M 表示为一棵树（其中 M 的索引来自深度优先搜索排序或其他东西）到联合查找结构的哈希映射（虽然不知道它是如何工作的：）

非常欢迎指向任何此类教科书数据结构的指针（数据库世界中有什么吗？）但如果您提出“自制”解决方案或仅提出随机想法，我也很感激。

空间效率对我来说很重要，因为 E 可能包含数千甚至几百万个元素，（一些）索引集可能很大，至少一些索引集之间的相似性应该很大，并且可能存在多层映射。

万分感谢！

4

4 回答 4

1

可以使用位数组。它们是元素数组，a[i]如果1在i集合中，0如果i不在集合中。size(E)因此，即使每个集合包含少数成员或不包含成员，每个集合也会准确占据位。空间效率不高，但如果你用一些压缩算法压缩这个数组，它的大小会小得多（可能达到最终熵限制）。因此，您可以尝试动态马尔可夫编码器或 RLE 或 Huffman 组，然后选择最适合您的一种。然后，迭代过程可以包括动态解压缩，然后是线性扫描1比特。对于长时间0运行，您可以修改减压算法以检测这种情况（RLE 是最简单的情况）。

如果您发现集合的差异很小，您可以存储集合，A而A xor B不是为公共部分节省空间。在这种情况下，要进行迭代，您必须先解压缩两者，然后再解压缩它们。ABBAA xor Bxor

于 2013-01-23T13:30:56.287 回答
1

您可以合并 M 中的所有数字并删除重复项并将其命名为 UniqueM。

所有 M[X] 集合都转换为位掩码。例如 int 值可以存储 32 个数字（为了支持无限计数，您应该存储整数数组，如果数组大小总共为 10，我们可以存储 320 个不同的元素）。long 类型可以存储 64 位。

E: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

M[0]: {6, 8, 1}
M[1]: {2, 8, 1}
M[2]: {6, 8, 5}

将转换为：

UniqueM: {6, 8, 1, 2, 5}
M[0]: 11100 {this is 7}
M[1]: 01110 {this is 14}
M[2]: 11001 {this is 19}

注意： 您也可以结合 my 和 ring0 方法，而不是重新排列 E 制作新的 UniqueM 并在其中使用间隔。

于 2013-01-23T12:04:14.607 回答
1

击败指数将非常困难。您可以通过使用正确的数据类型来节省一些空间（例如，在 gnu C 中，如果 E 中的元素少于 64k ，则为短，如果 < 4G 则为int ...）。

除了，

既然您说 E 中的顺序并不重要，您可以对 E 进行排序，使其最大化连续元素以尽可能多地匹配 Ms。

例如，

E: { 1,2,3,4,5,6,7,8 }

0: {1,3,5,7}
1: {1,3,5,8}
2: {3,5,7,8}

通过重新排列 E

E: { 1,3,5,7,8,2,4,6 }

并使用 E 索引，而不是值，您可以根据 E 的子集定义 Ms，给出索引

0: {0-3}     // E[0]: 1, E[1]: 3, E[2]: 5, E[3]: 7 etc...
1: {0-2,4}
2: {1-3,4}

这边走

  • 您使用索引而不是原始数字（索引通常更小，没有负数..）
  • Ms 由子集组成，0-3表示 0、1、2、3，

困难的部分是使算法重新排列 E 以便最大化子集大小 - 最小化 Ms 大小。

E 重排算法建议

  • 排序所有女士
  • 处理所有女士：

构建地图的算法，它为元素“x”提供其邻居列表“y”，以及点，“y”在“x”之后的次数

Map map (x,y) -> z
for m in Ms
  for e,f in m // e and f are consecutive elements
    if ( ! map(e,f)) map(e,f) = 1
    else map(e,f)++
  rof
rof

重新排列 E

ER = {}                 // E rearranged
Map mas = sort_map(map) // mas(x) -> list(y) where 'y' are sorted desc based on 'z' 
e = get_min_elem(mas)   // init with lowest element (regardless its 'z' scores)


while (mas has elements) 
  ER += e        // add element e to ER
  f = mas(e)[0]  // get most likely neighbor of e (in f), ie first in the list
  if (empty(mas(e))
    e = get_min_elem(mas) // Get next lowest remaining value
  else
    delete mas(e)[0]  // set next e neighbour in line
    e = f
  fi
elihw

算法（地图）应该是O(n*m)空间，在 E 中有 n 个元素，在所有 Ms 中有 m 个元素。

于 2013-01-23T11:25:09.760 回答
0

另一个有用的解决方案：

E: {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}

M[0]: {1, 2, 3, 4, 5, 10, 14, 15}
M[1]: {1, 2, 3, 4, 5, 11, 14, 15}
M[2]: {1, 2, 3, 4, 5, 12, 13}

缓存常用项目：

Cache[1] = {1, 2, 3, 4, 5}
Cache[2] = {14, 15}
Cache[3] = {-2, 7, 8, 9} //Not used just example.

M[0]: {-1, 10, -2}
M[1]: {-1, 11, -2}
M[2]: {-1, 12, 13}

将指向缓存列表的链接标记为负数。

于 2013-01-23T15:22:27.927 回答