代码之家 › 专栏 › 技术社区 › Tryer

保证集合新性的有效方法

set algorithm c c++

-1

Tryer · 技术社区 · 7 年前

给定集合 N = {1,...,n} ,考虑 P 不同的预先存在的 N . 一个子集, S_p ,以0-1为特征 n 矢量 x_p 在哪里 i 我 第(个) )项是否是子集的一部分。让我们称之为 s .

例如,如果 N={1,2,3,4,5} ,子集 {1,2,5} 用向量表示 (1,0,0,1,1) .

现在,给定 P x\U p公司

用向量表示的候选子集 y 是计算出来的。

检查是否已经是 P 预先存在的子集或确实是一个新的子集,而不是 P 子集?

以下是我能想到的方法:

(方法1)基本上,我们必须对所有预先存在的集合逐个元素进行检查。伪代码如下:

for(int p = 0; p < P; p++){
     //(check if x_p == y by doing an element by element comparison)
     int i;
     for(i = 0; i < n; i++){
         if(x_pi != y_i){
             i = 999999;
         }             
     }
     if(i < 999999)
          return that y is pre-existing

}
return that y is new

(方法2)想到的另一个想法是存储指标向量的十进制等价物 x\U p公司 P 预先存在的集合是: { (0,1,0,0,1), (1,0,1,1,0) } ,此集合存储的小数将是 {9, 22} . 如果 y (0,1,1,0,0) ,我们计算 12 把这个和背景对照一下 {9, 22} . 这种方法的好处是 y n 每个预先存在的集合的元素。我们可以比较一下十进制数。

问题1。在我看来,(方法2)应该比(方法1)更有效。对于(方法2),是否有一种有效的方式(C/C++中的内置库函数)转换 x\U p公司 y 从二进制到十进制?这些指标变量的数据类型应该是什么?例如。, bool y[5]; 或 char y[5]; ?

2 回复 | 直到 7 年前

Sneftel 7 年前

正如您所注意到的,在指示符向量和N位整数之间有一个微不足道的同构。这意味着问题2的答案是“否”:用于维护集合和测试集合成员身份的工具与整数相同(哈希表带来了正常的方法)。一个评论提到了Bloom fillers,它可以有效地测试成员资格,但是Bloom fillers通常用于比您所看到的更大的数据量。

vector<bool> 不给你一个简单的方法把它变成整数块,在实现上我知道它已经实现了这种方式(C++标准允许对特定向量类型的特殊处理,现在认为这是一个很差的决定,但偶尔会产生一些好处)。这些向量是可散列的。所以保持冷静 unordered_set<vector<bool>> 你会得到接近最佳的性能(如果你知道 N bitset 到 向量<布尔> .)

-1

addy 7 年前

#define M 1000000007  //big prime number
unordered_set<long long> subset;  //containing decimal representation of all the 
                                  //previous found subsets

/*fast computation of power of 2*/
long long Pow(long long num,long long pow){
    long long result=1;
    while(pow)
    {
        if(pow&1)
        {
            result*=num;
            result%=M;
        }
        num*=num;
        num%=M;
        pow>>=1;
    }
    return result;
}
/*checks if subset pre exists*/
bool check(vector<bool> booleanVector){
    long long result=0;
    for(int i=0;i<booleanVector.size();i++)
        if(booleanVector[i])
            result+=Pow(2,i);
    return (subset.find(result)==subset.end());
}