这可能不是编程问题,而是最近在工作中出现的问题。一些背景:对性能特别感兴趣的大 C 开发。
我有一组整数,想测试另一个给定整数的成员资格。我很想实现一个算法,它可以用最小的代数函数集来检查它,只使用一个整数来表示第一个集合中包含的整个整数空间。
例如,我尝试过复合康托尔配对功能,但是对于 30 个元素的集合,它似乎太复杂了,并且专注于性能是没有意义的。我玩过一些操作,比如 XORing 和 negating,但它让我对成员资格的估计很低。然后我尝试了连续添加,最后迷路了。
有任何想法吗?
对于unsigned long
大小为 30 的集合,以下是一种相当明显的方法:
30 * sizeof(unsigned long)
每个集合的字节数。bsearch
并且速度足够快,则可以使用它)。所以下一个问题是为什么你想要一个大数学的解决方案,它会告诉我这个解决方案除了“它不够令人愉快”之外还有什么问题。
我怀疑任何大数学解决方案都会比这慢。对 N 位数字的单个算术运算至少需要 N 中的线性时间。表示一个集合的单个数字不能比该集合的元素首尾相连并在其间有分隔符小很多。因此,即使是在集合中的线性搜索也与对大数的单个算术运算一样快。除了 Goedel 表示可能的例外,一旦你找到了n
第 th 个素数,它可以在一次除法中完成,任何聪明的集合的数学表示都将需要多次算术运算来建立成员资格。
另请注意,您可能关心“在集合中查找整数”的性能有两个不同的原因:
我想你可能偶尔会查找很多不同的整数,每个整数都在不同的集合中,所以这两个原因都不适用。如果这是其中之一,你可以忽略那些东西。
一个好的开始是尝试Bloom Filters。基本上,它是一种概率数据结构,不会给您带来误报,而是给您一些误报。因此,当一个整数与布隆过滤器匹配时,您必须检查它是否真的与集合匹配,但通过减少要检查的集合数量,这是一个很大的加速。
如果我理解正确,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
>>>