我有一个包含几百万个集合的大型集合，C。我集合的元素来自大约 2000 种可能元素的宇宙。我需要知道，对于给定的集合 s，C 中的哪个集合与 s 的交集最大？ (或者 C 中具有 k 个最大交集的 k 个集合)。我将针对不同的 s 依次进行许多此类查询。
我知道这样做的明显方法是循环遍历 C 中的每个集合并计算交集并取最大值。是否有任何智能数据结构/编程技巧可以加快我的搜索速度？如果我能比 O(C) 更快地做到这一点，那就太好了。
编辑:大概的答案也可以
最佳答案
我不认为存在有助于渐近性能的聪明数据结构。但这是一个完美的 map 减少问题。 GPGPU 会做得很好。对于 2048 个元素的宇宙，作为位图的集合只有 256 字节。 400万只是一个千兆字节。即使是适度规范的 Nvidia 也有。例如。在 CUDA 中编程，您将 C 复制到显卡 RAM，将千兆字节的一 block 映射到每个 GPU 核心进行搜索，然后跨核心减少以找到最终答案。这应该需要几毫秒的时间。不够快？就买hotter hardware .
如果您按照这些思路重新表述您的问题，您可能会从此类编程专家那里得到答案，而我不是。
关于具有给定集合的集合集合中最大集合交集的算法/数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31735817/