0

这可能不是编程问题，而是最近在工作中出现的问题。一些背景：对性能特别感兴趣的大 C 开发。

我有一组整数，想测试另一个给定整数的成员资格。我很想实现一个算法，它可以用最小的代数函数集来检查它，只使用一个整数来表示第一个集合中包含的整个整数空间。

例如，我尝试过复合康托尔配对功能，但是对于 30 个元素的集合，它似乎太复杂了，并且专注于性能是没有意义的。我玩过一些操作，比如 XORing 和 negating，但它让我对成员资格的估计很低。然后我尝试了连续添加，最后迷路了。

有任何想法吗？

4

3 回答 3

2

对于unsigned long大小为 30 的集合，以下是一种相当明显的方法：

  • 将每个集合存储为一个排序数组，30 * sizeof(unsigned long)每个集合的字节数。
  • 要查找一个整数，先进行几步二分搜索，然后进行线性搜索（配置文件以找出最好的二分搜索步数 - 我的疯狂猜测是 2 步，但您可能会发现不同，当然，如果您测试bsearch并且速度足够快，则可以使用它）。

所以下一个问题是为什么你想要一个大数学的解决方案，它会告诉我这个解决方案除了“它不够令人愉快”之外还有什么问题。

我怀疑任何大数学解决方案都会比这慢。对 N 位数字的单个算术运算至少需要 N 中的线性时间。表示一个集合的单个数字不能比该集合的元素首尾相连并在其间有分隔符小很多。因此，即使是在集合中的线性搜索也与对大数的单个算术运算一样快。除了 Goedel 表示可能的例外，一旦你找到了n第 th 个素数，它可以在一次除法中完成，任何聪明的集合的数学表示都将需要多次算术运算来建立成员资格。

另请注意，您可能关心“在集合中查找整数”的性能有两个不同的原因：

  • 您正在单个集合中查找许多不同的整数，在这种情况下，您可以通过为该数据构建自定义查找函数来加快速度。当然，在 C 语言中，这意味着您需要 (a) 一个简单的虚拟机来执行该“功能”，或者 (b) 运行时代码生成，或者 (c) 在编译时知道集合。这些都不一定是容易的。
  • 您正在许多不同的集合中查找相同的整数（以获取它所属的所有集合的序列），在这种情况下，您可能会受益于您关心的所有集合的组合表示，而不是单独考虑每个集合.

我想你可能偶尔会查找很多不同的整数，每个整数都在不同的集合中，所以这两个原因都不适用。如果这是其中之一，你可以忽略那些东西。

于 2012-08-28T09:51:11.340 回答
0

一个好的开始是尝试Bloom Filters。基本上，它是一种概率数据结构，不会给您带来误报，而是给您一些误报。因此，当一个整数与布隆过滤器匹配时，您必须检查它是否真的与集合匹配，但通过减少要检查的集合数量，这是一个很大的加速。

于 2012-08-28T09:38:38.303 回答
0

如果我理解正确，python 示例：

>>> a=[1,2,3,4,5,6,7,8,9,0]
>>>
>>>
>>> len_a = len(a)
>>> b = [1]
>>> if len(set(a) - set(b)) < len_a:
...     print 'this integer exists in set'
...
this integer exists in set
>>>

数学基础：http ://en.wikipedia.org/wiki/Euler_diagram

于 2012-08-28T09:39:05.367 回答