subset-reduced 增长列表的数据结构
Data structure for subset-reduced growing list
我正在处理一个涉及处理大量数据的问题。为了减少工作量（因为当前的计算需要大约两周的计算时间，我想大大减少它）我想出了一个算法，如果它能够避免某种类型的重复，它会更快。 （当前算法避免存储此信息，因为它太大，未减少，无法放入内存。）
我有一个 collection 集合，如果已经有一个 B 集合 A，我不想插入一个集合 A =].目前，这些集合由整数表示，其中各个二进制数字表示存在或不存在的特定元素。在该解释中，如果已经存在 set/integer B 使得 (~A) & B 为 0，而 ~ 则不应插入 set/integer A按位取反并且 & 是按位与。
例如，如果我的collection有以下集合
[ {a,b}, {b,c}, {b,d,e} ]
我要求添加 {b,c,e} 它不应该添加（因为 {b,c} 已经存在）并且与 {a,b} 类似（因为 {a,b} 存在) 但应添加 {a,e}。
等效的数字将以
开头
[ `0b11`, `0b110`, `0b11010` ]
其中0b10110因为(~0b10110) & 0b110 == 0没有加，0b11因为(~0b11) ^ 0b11 == 0没有加，但是可以加0b10001。
理想情况下 该结构会在添加新集时自行修剪，因此如果添加 {c}，则将删除所有包含 c 的现有集。但如果它不以那种方式更新也是可以接受的，只要我可以经常以某种 not-too-expensive 的方式将它规范化为那种形式。
这是一个众所周知的问题 "finding extremal sets"；不幸的是，没有什么比针对所有现有集合测试新插入的集合的明显方法从根本上更快，但是存在良好的启发式改进。这是最近讨论这个问题的论文：https://arxiv.org/abs/1508.01753
相关算法的开源实现：
https://code.google.com/archive/p/google-extremal-sets/
我正在处理一个涉及处理大量数据的问题。为了减少工作量（因为当前的计算需要大约两周的计算时间，我想大大减少它）我想出了一个算法，如果它能够避免某种类型的重复，它会更快。 （当前算法避免存储此信息，因为它太大，未减少，无法放入内存。）
我有一个 collection 集合，如果已经有一个 B 集合 A，我不想插入一个集合 A =].目前，这些集合由整数表示，其中各个二进制数字表示存在或不存在的特定元素。在该解释中，如果已经存在 set/integer B 使得 (~A) & B 为 0，而 ~ 则不应插入 set/integer A按位取反并且 & 是按位与。
例如，如果我的collection有以下集合
[ {a,b}, {b,c}, {b,d,e} ]
我要求添加 {b,c,e} 它不应该添加（因为 {b,c} 已经存在）并且与 {a,b} 类似（因为 {a,b} 存在) 但应添加 {a,e}。
等效的数字将以
开头[ `0b11`, `0b110`, `0b11010` ]
其中0b10110因为(~0b10110) & 0b110 == 0没有加，0b11因为(~0b11) ^ 0b11 == 0没有加，但是可以加0b10001。
理想情况下 该结构会在添加新集时自行修剪，因此如果添加 {c}，则将删除所有包含 c 的现有集。但如果它不以那种方式更新也是可以接受的，只要我可以经常以某种 not-too-expensive 的方式将它规范化为那种形式。
这是一个众所周知的问题 "finding extremal sets"；不幸的是，没有什么比针对所有现有集合测试新插入的集合的明显方法从根本上更快，但是存在良好的启发式改进。这是最近讨论这个问题的论文：https://arxiv.org/abs/1508.01753
相关算法的开源实现： https://code.google.com/archive/p/google-extremal-sets/