看！源码Redis之算法扩展一(Diff差集)

在set中支持获取多set中的差集结果,而redis作者提供了两种算法,此处针对这两种算法进行比较。
这里需要注意的是这里的差集是以第一个集合做为目标集合进行计算的

//此处代码用于判断具体使用的两种算法
//默认算法为算法一，此处下方讲解
int diff_algo = 1;
//判断使用算法的依据在于集合的元素数
//此处将多个集合的元素数分为两块
//1. algo_one_work 目标集合元素数 * 集合个数
//2. algo_two_work 所有集合的元素数
long long algo_one_work = 0, algo_two_work = 0;
for (j = 0; j < setnum; j++) {
    if (sets[j] == NULL) continue;
    
    algo_one_work += setTypeSize(sets[0]);
    algo_two_work += setTypeSize(sets[j]);
}

//此处作者更加倾向于算法一 所以即使algo_two_work == algo_one_work * 2,也选择算法一,只有超过
//才使用算法二
algo_one_work /= 2;
diff_algo = (algo_one_work <= algo_two_work) ? 1 : 2;
//如果根据上方的计算得到算法一
if (diff_algo == 1 && setnum > 1) {
   //则排序除目标集合的剩余集合,排序结果是数组集合中每个集合数的降序
    qsort(sets+1,setnum-1,sizeof(robj*),
        qsortCompareSetsByRevCardinality);
}

算法一

//算法一的流程是使用降序结果的第一个集合即最大的那个集合去遍历其他集合
//获取最大集合
si = setTypeInitIterator(sets[0]);
//遍历最大集合的元素
while((ele = setTypeNextObject(si)) != NULL) {
    //遍历其他集合数组
    for (j = 1; j < setnum; j++) {
        //如果为空则跳过当前集合
        if (!sets[j]) continue; 
        //如果当前集合等于最大集合则跳过
        if (sets[j] == sets[0]) break;
        //根据第一个集合中的元素查看当前集合中是否存在
        if (setTypeIsMember(sets[j],ele)) break;
    }
     //如果存在当前j必然不会等于setnum,因为setnum是集合的总数量,只有检查过所有的集合都不存在才代表
     //当前元素是唯一的 那么就是差集了,从而j就等于setnum,则在下方将元素添加到结果集合中
     //j != setnum 说明未到尾部 就跳出了上方的for循环,j == setnum则上方的for是完整执行了的
    if (j == setnum) {
        /* There is no other set with this element. Add it. */
        setTypeAdd(dstset,ele);
        cardinality++;
    }
    sdsfree(ele);
}
setTypeReleaseIterator(si);

算法二

//遍历所有集合
for (j = 0; j < setnum; j++) {
    if (!sets[j]) continue; 

    si = setTypeInitIterator(sets[j]);
    while((ele = setTypeNextObject(si)) != NULL) {
        //将第一个集合即目标集合添加到结果集中
        if (j == 0) {
            if (setTypeAdd(dstset,ele)) cardinality++;
        } else {
            //然后遍历剩余集合从结果集中进行删除,如果删除成功则说明当前元素存在其他集合中
            if (setTypeRemove(dstset,ele)) cardinality--;
        }
        sdsfree(ele);
    }
    setTypeReleaseIterator(si);
    //为了避免不必要的循环当上方remove了结果集中的所有数据那么card便为0则直接跳出循环
    if (cardinality == 0) break;
}

• 算法一

总结: 使用目标集合(即第一个集合)遍历剩余集合,只有剩余所有集合都不存在才添加到结果集中.

• 算法二

总结: 使用其他集合遍历目标集合(即第一个集合),默认将目标集合所有元素添加到结果集中,然后遍历剩余集合,如果剩余集合的元素存在结果集中则删除相同元素。

从算法可以看出,此处的差集并不是所有集合的差集结果,而是第一个集合即(目标集合)针对其神域集合的差集。

总结两个算法的复杂度

排除remove和setTypeIsMember的查找复杂度

• 算法一

n * m ，n是目标元素数,m是剩余集合数。只用遍历的变量目标集合,然后查找剩余集合如果存在则跳过当前元素n，如果不存在则添加到结果集中

• 算法二

n*m,n是集合元素数,m集合数,完整的遍历所有的集合,如果存在则从结果集中移除，否则下一个元素

虽然二者的复杂度都是nm但是因为nm的含义不同差距巨大，这也是为什么作者跟倾向于第一个算法。

案例

例子一： 目标集合 大小为 100 ,其它10个集合平均各1000

• 第一个算法
  100 * 10 = 1000只用遍历执行1000次setTypeIsMember就可以得到结果
• 第二个算法
  100 + 10 * 1000 = 10100 需要遍历一万多次才可以得到结果

例子二：目标集合 大小为 10000 其它10个集合平均各490

• 第一个算法
  10000*10 = 100000 需要遍历10万次才能得到结果
• 第二个算法
  490*10 + 10000 = 14900 只用遍历14900次就可以得到结果

此处需要感谢田巨佬的举例