精华内容
下载资源
问答
  • 隐私保护集合交集计算技术研究综述
  • 针对开放网络中指纹认证的隐私保护问题,利用智能卡设计通用可组合安全的隐秘双方交集计算协议。该协议使用对称加密算法实现双方交集计算,具有较高的计算和通信效率。在此基础上,提出一种隐私保护型身份认证方案,...
  • 这里写目录标题5.9 SINTER、SINTERSTORE:对集合执行交集计算5.9.1 SINTERSTORE命令5.9.2 其他信息参考目录 5.9 SINTER、SINTERSTORE:对集合执行交集计算         SINTER...

    5.9 SINTER、SINTERSTORE:对集合执行交集计算

            SINTER命令可以计算出用户给定的所有集合的交集,然后返回这个交集包含的所有元素:

    在这里插入图片描述

            比如对于以下这两个集合来说:

    在这里插入图片描述

            我们可以通过执行以下命令计算出这两个集合的交集:

    在这里插入图片描述

            从结果可以看出,s1和s2的交集包含了"c"和"d"这两个元素。

    5.9.1 SINTERSTORE命令

            除了SINTER命令之外,Redis还提供了SINTERSTORE命令,这个命令可以把给定集合的交集计算结果存储到指定的键里面:

    在这里插入图片描述

            如果给定的键已经存在,那么SINTERSTORE命令在执行存储操作之前 会先删除已有的键。

            SINTERSTORE命令在执行完毕之后会返回被存储的交集元素数量作为返回值。

            例如,通过执行以下命令,我们可以把s1和s2的交集计算结果存储到集合s1-inter-s2中:

    在这里插入图片描述

    5.9.2 其他信息

            复杂度:SINTER命令和SINTERSTORE命令的复杂度都是O(N*M), 其中N为给定集合的数量,而M则是所有给定集合当中,包含元素最少 的那个集合的大小。

            版本要求:SINTER命令和SINTERSTORE命令从Redis 1.0.0版本开始可用。

    参考目录

    绝大多数 内容来自 Redis使用手册 (黄健宏 著) 第5章 集合

    展开全文
  • 区间列表的交集计算

    2019-02-03 12:19:27
    返回这两个区间列表的交集。 (形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2,...

    给定两个由一些闭区间组成的列表,每个区间列表都是成对不相交的,并且已经排序。

    返回这两个区间列表的交集。

    (形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b。两个闭区间的交集是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3]。)

    示例:

    输入:A = [[0,2],[5,10],[13,23],[24,25]], B = [[1,5],[8,12],[15,24],[25,26]]

    输出:[[1,2],[5,5],[8,10],[15,23],[24,24],[25,25]]

    注意:输入和所需的输出都是区间对象组成的列表,而不是数组或列表。

    我的思路:

    可以借鉴两个有序数组合并时候的思路。对A、B进行遍历,只要有一个遍历完就停止遍历。

    遍历过程如下:

    ①如果A的一个区间的end比B的start要小,说明这个区间一定在前面即不可能与后续的B有交集,因此A往后走。反之如果B的end比A的start小,则B往后走。

    ②A(B)的start小于等于A(B)的start且A(B)的end大于等于B(A)的start。这种情况一定是有交集的。但还要分两种情况:

          a.A(B)是包含在B(A)里面的,也就是A(B)整个的就是交集

          b.A(B)与B(A)是交错的。

     

    我的代码:

    class Interval {
       int start;
       int end;
       Interval() { start = 0; end = 0; }
       Interval(int s, int e) { start = s; end = e; }
     }
    public class IntervalListIntersections {
    	public Interval[] intervalIntersection(Interval[] A, Interval[] B) {
            ArrayList<Interval> res = new ArrayList<>();
            if(A.length == 0 || B.length == 0) {
            	Interval[] t = new Interval[0];
            	return t;
            }
            int i = 0 , j = 0,count = 0;
            while (i<A.length && j<B.length) {
    			if(A[i].end<B[j].start) i++;
    			else if (B[j].end<A[i].start) j++;
    			else if (A[i].start<=B[j].start && A[i].end>=B[j].start) {
    				if(A[i].end<B[j].end) {
    					Interval tmp = new Interval(B[j].start,A[i].end);
    					//res[count++] = tmp;
    					res.add(tmp);
    					i++;
    				}else {
    					Interval tmp = new Interval(B[j].start, B[j].end);
    					res.add(tmp);
    					j++;
    				}
    				
    			}else if (B[j].start<=A[i].start && B[j].end>=A[i].start) {
    				if(B[j].end<A[i].end) {
    					Interval tmp = new Interval(A[i].start,B[j].end);
    					res.add(tmp);
    					j++;
    				}else {
    					Interval tmp = new Interval(A[i].start,A[i].end);
    					res.add(tmp);
    					i++;
    				}
    				
    			}
    		}
            Interval[] tIntervals = new Interval[res.size()];
            return res.toArray(tIntervals);
        }
    	public static void main(String[] args) {
    		Interval[] tIntervals = new IntervalListIntersections().intervalIntersection(new Interval[] {
    				new Interval(0, 2),new Interval(5,10),
    				new Interval(13,23),new Interval(24, 25)
    		}, new Interval[] {
    				new Interval(1, 5),new Interval(8, 12),
    				new Interval(15, 24),new Interval(25, 26)
    		});
    		for(Interval i:tIntervals) {
    			System.out.println(i.start+" "+i.end);
    		}
    		Interval[] tIntervals1 = new IntervalListIntersections().intervalIntersection(new Interval[] {
    				
    		}, new Interval[] {
    				
    		});
    		for(Interval i:tIntervals1) {
    			System.out.println(i.start+" "+i.end);
    		}
    		Interval[] tIntervals3 = new IntervalListIntersections().intervalIntersection(new Interval[] {
    				new Interval(5, 10)
    		}, new Interval[] {
    				new Interval(5, 6)
    		});
    		for(Interval i:tIntervals3) {
    			System.out.println(i.start+" "+i.end);
    		}
    	}
    }

    运行结果:

    展开全文
  • 对当前存在的PSI协议做的总结,主要分三大类, 分别为基于多项式的PSI,基于混乱电路的PSI,基于不经意传输的PSI
  • 计算二维平面的两个矩形的面积交集实际上是可以转换为一维线段的交集来解决的,下图是一维线段的并集: 二维平面对应线段的交集的乘积就是两个矩形的面积交集,如下图所示,实际上是二维平面的线段在坐标轴上的...

    计算二维平面的两个矩形的面积交集实际上是可以转换为一维线段的交集来解决的,下图是一维线段的并集:

    二维平面对应线段的交集的乘积就是两个矩形的面积交集,如下图所示,实际上是二维平面的线段在坐标轴上的投影这样就可以转换为一维线段来解决,也就是可以对应上面的一维线段的交集

    展开全文
  • GPU方法做倒排压缩和交集计算

    千次阅读 2014-09-17 23:32:12
    使用Linear Regression Compression,可以很好压缩(但压缩比只有二点几,不知道和group variant比怎么样),但是具有不保存delta的优势,在GPU上可以直接应用binary search,只是每次需要浮点数计算. Efficent Parallel...
    之前一直想读这篇,今天读了一下,颇有收获:
    
    1.对文档按相似term聚类之后,delta较小,可以提高压缩率(similarity graph)
    1.GPU一般可以有几百个核,有shared memory和global memory,shared memory相当于寄存器的速度,global memory速度较慢
    2.有序数组上的搜索算法除了binary search还有interplation search(插值搜索),平均复杂度是O(loglogn),但memory access是binary search的三倍,一般不使用
    3.一般到排链基本都符合线性增长趋势,可以对应直线的点,取范围查找可以减少binary search的范围,提升效率(LR Algorithm)
    4.或使用hash表,将一定范围内的docId放在一个bucket中,哈希函数简单、哈希表在shared memory中,虽然有些内存的overhead,但效率非常高,快于LR(HS Algorithm)
    5.因为一般倒排表是线性增长的,使用Linear Regression Compression,可以很好压缩(但压缩比只有二点几,不知道和group variant比怎么样),但是具有不保存delta的优势,在GPU上可以直接应用binary search,只是每次需要浮点数计算.
    Efficent Parallel Lists Intersection and Index Compression Algorithms using Graphics Processing Units:
    http://www.vldb.org/pvldb/vol4/p470-ao.pdf
    展开全文
  • 一种两方交集保密计算协议,陈治宇,,在Boyen-Waters的匿名IBE方案的两方数据集交集保密计算协议的理论基础上,补充了原文中未完全提及的零知识证明和承诺方案的相关理论,
  • 计算两个点圈交集

    2016-08-16 11:34:25
    计算两个由点组成的封闭图形的交集
  • 主要介绍了Java计算交集,差集,并集的方法,结合实例形式简单分析了java集合运算的简单操作技巧,需要的朋友可以参考下
  •         设两个闭区间分别为:[a1,a2], [b1,b2],如果她俩有并集,那么并集一定是[max...你的第一个区间的终点要比第二个的起点大,不然不可能有交集(并集) 你的第二个区间的终点要比第一个的起.
  • 两个集合之间进行交集、差集、并集计算。 在日常工作中前端可能传过来一个数据集合,需要和数据库中查出的集合进行比较,判断前端的集合中那些数据是需要在数据库新增、那些数据是需要从数据库中删除、那些数据需要...
  • 在PHP中,数组函数 array_intersect_key () 用来计算多个数组的交集,交集计算时只比较数组元素的键key。 函数语法: array_intersect_key(array$array1,array$array2[,array$...]):array 函数参数说明: 参数 ...
  • 主要介绍了Python3实现计算两个数组的交集算法,结合2个实例形式总结分析了Python3针对数组的遍历、位运算以及元素的添加、删除等相关操作技巧,需要的朋友可以参考下
  • VBA利用数组极速计算交集和并集,超过普通算法交集,极速版本
  • 个人实现的求取图形交集的工程,效果见链接: http://blog.csdn.net/qq_24038299/article/details/79382418,大家相互学习借鉴
  • 请首先查看右侧的示例选项卡(.mlx 文件)以获取完整说明。 下载后,在Matlab控制台中键入“ help planes_intersection”或“ doc planes_intersection”以获取支持。
  • 安全多方计算之隐私保护集合交集

    千次阅读 2020-02-28 22:58:11
    作为安全多方计算领域具有广泛的应用场景的一类协议,隐私保护集合交集技术在近年来得到了极大的优化,达到了在某些场景下与目前正在使用的非安全交集技术同一量级的运行复杂度。 摘要:隐私保护集合交集...
  • 计算两个数组的交集

    2018-02-02 10:25:29
    计算机两个数组的交集 方法思路: 依次对两个数组进行遍历,直至其中一个数组结束(下面程序的方法) 遍历两个数组,将两个数组放入哈希表中,并对元素个数进行统计,若为2,即为两数组的交集 // MixedArray....
  • 今天小编就为大家分享一篇PHP 计算两个时间段之间交集的天数示例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 倒排表交集计算

    千次阅读 2009-05-16 23:43:00
    对排序后的倒排表进行求交集的时间复杂度是o(n + m)3. 两两合并和多路同时合并的效果差不多4.可以采用跳表来加速合并过程,所谓跳表即是 因此在查询时可以根据快表进行跳转,但快表的长度不宜太长或过短,经验值是...
  • 遇到一个问题,比较苦恼没有较好的计算方法去解决。具体是这样,有两个时间段,根据这两个时间段的交集和非交集部分,拆分出至多三个时间段。当时就用了最基础最笨的方法,两个时间段的起止时间相互比较区分多种情况...
  • 问题描述: 假设两个含有n个元素的有序(非降序)整型数组a和b,其中 a = { 0,1,2 ...若当前遍历的位置a[i]==b[j],则次=此数为两个数组的交集,记录下来,并且继续向后遍历a1,b1. 若a[i] &gt; b[j] ,则继续向...
  • 有两个数组arr1,arr2 实现arr2中去除arr1相同的元素 e.g arr1=[1,2,3] arr2=...获取两个数组(arr1,arr2)的交集arr3 获取交集arr3与arr2中arr2的差集就是我们要的result 交集 var arr3 = arr2.filter(function(v){ ...
  • 计算几何】多边形交集

    千次阅读 2015-05-16 19:28:00
    问题描述:已知两个多边形Poly1和Poly2,分别由点集C1={P1,P2,...,Pm}和C2={Q1,Q2,...,Qn}表示,求这两个多边形的交集。 算法思想: 两个多边形相交后,其顶点要么是两个多边形边的交点,要么是在多边形内部的点。 ...
  • #include ...//采用二路归并法,查找两个数组的交集进行保存,并返回交集的个数。 int mix(int a[],int m,int b[],int n,int *c) { int i=0,j=0,k=0; while(i { if(a[i]>b[j]) j++; else if(a[i] i++; else

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 86,783
精华内容 34,713
关键字:

交集如何计算