提问人：Robert Fraser 提问时间：12/15/2016 最后编辑：Robert Fraser 更新时间：12/15/2016 访问量：68
用于查看许多不同的数组是否是另一个数组的子集的算法？
Algorithm for seeing if many different arrays are subsets of another one?
问：
例如，假设我有一个 ~20-100 个整数的数组（实际上数字更像是 ，所有非负 64 位整数都在 2^63 以下，但出于演示目的，让我们使用它们）。[0, 1, 2, 3, 4, 5, 6, 7, 8, 9][106511349 , 173316561, ...]
以及许多 （~50,000） 通常为 1-20 项的较小数组来匹配或不匹配：
1=[2, 3, 8, 20]
2=[2, 3, NOT 8]
3=[2, 8, NOT 16]
4=[2, 8, NOT 16] (there will be duplicates with different list IDs)
我需要找出其中哪些是正在测试的数组的子集。匹配列表必须包含所有正匹配项，而没有负匹配项。因此，对于这个小示例，我需要返回类似 .列表 1 不匹配，因为它需要 20，列表 2 不匹配，因为它没有 8。在这些情况下，可以很容易地通过使用高位/使数字为负数来表示 NOT。[3, 4]
我需要以每秒 10,000 次的速度快速执行此操作。小数组是“固定的”（它们不经常变化，比如每隔几秒钟一次），而大数组是按要扫描的数据项完成的（因此每秒 10,000 个不同的大数组）。
这已经成为一个瓶颈，所以我正在寻找优化它的方法。
我不确定最好的数据结构或表示方式。一种解决方案是把它转过来，看看我们甚至需要考虑哪些小列表：
2=[1, 2, 3, 4]
3=[1, 2]
8=[1, 2, 3, 4]
16=[3, 4]
20=[1]
然后，我们将建立一个列表列表进行检查，并对这些列表进行完整的子集匹配。但是，某些术语（通常是更频繁的术语）最终会出现在许多列表中，因此这里并没有太大的实际胜利。
我想知道是否有人知道解决此类问题的更好算法？
答：
0赞
Rusty Rob
12/15/2016
#1
您可以尝试使用较小的数组创建树，因为它们更改的频率较低，因此每个子树都试图将剩余的小数组数量减半。
例如，对较小数组中的数字进行频率分析。找出在最接近一半的较小数组中找到的数字。将其作为树中的第一个检查。在您的示例中，这将是“3”，因为它出现在一半的小数组中。现在，这是树中的头节点。现在将所有包含 3 的小列表放在左边的子树上，把所有其他列表放在右边的子树上。现在，在每个子树上递归地重复此过程。然后，当一个大数组进来时，反向索引它，然后遍历子树以获取列表。
评论
0赞
ruakh
12/15/2016
构建一棵树是有道理的，但我认为它必须是一棵三元树：一个子树将包含指定的数组，一个子树将包含指定的数组，一个子树将包含不指定的数组。在每个分支上，您需要下降到三个子树中的两个。最佳树结构可能是非指定任何子树最小的子树结构，因为这是您必须无条件下降到的子树。3NOT 3
0赞
Rusty Rob
12/15/2016
“Not 3”也可以是“3”节点的单独节点。
0赞
ruakh
12/16/2016
没错，但我的主要观点是，你总是会递归到“不需要这个”子树中;因此，您的目标“每个子树都试图将剩余的小数组数量减半”并不理想。相反，您的目标应该是选择条件，如果不满足这些条件，则尽可能多地消除小数组。
0赞
Rusty Rob
12/16/2016
好点，多个分支。我想可以在小数组上使用各种测试。因此，一个贪婪的算法，“给定一个小数组列表，测试最有可能将我们必须继续查看的小数组的数量分成两半”，它不断拆分，用小数组组组成一棵树，就易于编码和相当快而言，可能是相当不错的。
0赞
Nicko Po
12/15/2016
#2
您没有说明对哪些数组进行了排序 - 如果有的话。
由于您的数据不是那么大，我将使用哈希映射来存储源集（具有 ~20-100 个整数的条目）的条目。这基本上可以让你测试 O（1） 中是否存在整数。
然后，假设 50,000（数组） * 20（每个项）* 8（每项字节数）= 8 兆字节 + （哈希映射开销），对于大多数系统来说似乎也不大，我将使用另一个哈希映射来存储测试的数组。这样，您就不必重新测试重复项。
0赞
ruakh
12/15/2016
#3
我意识到从 CS 的角度来看，这可能不太令人满意，但如果你正在执行大量互不影响的小任务，您可能需要考虑并行化它们（多线程）。每秒 10,000 个任务，比较每个任务中的不同数组，应该符合要求;你没有提供任何关于你正在做什么的细节（例如，所有这些数组来自哪里），但可以想象，多线程可以大大提高你的吞吐量。
0赞
Dean J
12/15/2016
#4
首先，按照你的建议去做;将输入整数的哈希映射制作到它所在的过滤器数组的 ID。这样一来，你就可以说“输入 #27 在这 400 个过滤器中”，并将这 400 个过滤器扔进一个排序的集合中。然后，您必须对每个集合进行排序集合的交集。
可选：从每个输入整数到过滤器集中的频率制作第二个哈希图。当输入进来时，使用第二个哈希图对其进行排序。然后，取最不常见的输入整数并从它开始，这样您就减少了每个步骤的总工作量。还要计算“非”情况的频率，这样您基本上可以在每一步中获得最大的收益。
最后：这可以很容易地变成一个并行编程问题;如果它在一台机器上不够快，那么如果它返回的任何内容都足够有用，那么你似乎可以很容易地将更多的机器放在它上面。
评论