欢迎来到知嘟嘟! 联系电话:13336804447 卖家免费入驻,海量在线求购! 卖家免费入驻,海量在线求购!
知嘟嘟
我要发布
联系电话:13336804447
知嘟嘟经纪人
收藏
专利号: 2022114274162
申请人: 南京邮电大学
专利类型:发明专利
专利状态:已下证
专利领域: 计算;推算;计数
更新日期:2026-11-16
缴费截止日期: 暂无
价格&联系人
年费信息
委托购买

摘要:

权利要求书:

1.一种基于多线程的Costas序列的搜索方法,该方法包含以下步骤:步骤S1、输入需要搜索的Costas序列的阶数;

步骤S2、建立双向链表的框架数据结构,通过递归迭代生成对应阶数的置换矩阵;

步骤S3、生成判定置换矩阵对应的校验矩阵的任务,提交任务;

步骤S4、对收到S2,S3提交任务,利用线程池技术创建线程池创建多线程结合任务窃取技术进行多线程运算,加速对于校验矩阵的判定;以及步骤S5、将任务进行汇总,最终得到Costas序列的数量与搜索花费时间并与传统多线程搜索对比;

其中,在步骤S2中递归迭代生成置换矩阵的步骤如下:

S21、Costas序列对应的置换矩阵的特点是:n阶置换矩阵的任意行,任意列中有且仅有一个元素为1;

S22、假设搜索n阶Costas序列,其对应的置换矩阵的生成方式采用从集合[1,2,……n]中不重复的取出数字存放在长度为n的置换矩阵记录数组中,规定记录数组的索引index对应置换矩阵第index+1列,数组中每个元素置换矩阵的表示第几行有元素1;

对于步骤S22中存放n个元素的集合,采用含有头结点的双向链表,每个节点Node中包含数据域val和next节点,pre节点,节点中的数据域val存储该节点对应的数据,next节点指向下一个节点,pre节点指向前一个节点,通过Node.pre.next=Node.next,Node.next.pre=Node.pre,实现对当前节点的删除,从而保证在递归生成置换矩阵的过程中无法访问到已经遍历到的节点,即保证置换矩阵的任意行和列有且只有一个元素“1”;删除后的节点通过judge(参数)进行判决和下一层递归,然后将该节点重新插入,不影响重新递归生成新的置换矩阵时,链表的初始条件;插入方式为:Node.pre.next=Node,Node.next.pre=Node;

在步骤S4中,利用线程池技术创建线程池创建多线程结合任务窃取,任务分解,分治算法进行多线程运算,加速对于置换矩阵和是否满足Costas序列条件的判定;具体步骤包括:S41、调用函数public ForkThread(int order,int innerPre,int[]preCostas,boolean flag)当多个线程在执行置换矩阵的判别任务时,如果有线程出现空闲,将自动获取其他线程没有执行的任务并执行该任务,提高线程的利用率;

S42、调用函数public void distributeTask(Integer order,Integer subSize)将任务规模进行分解,当subSize>4时,将subSize调整到4,如果subSize<0,设置subSize=1。

2.根据权利要求1所述的方法,其特征在于:步骤S3包括以下步骤:S31、根据Costas序列判定条件,置换矩阵的自相关函数的最大峰值不超过1,转换到矩阵图形上为置换矩阵对应的图形在任意平移过程中最多只有一个元素“1”位置重合;若平移过程中存在2个或以上的点重合,则该置换矩阵的图形中必定存在四个点依次连接形成的图形是平行四边形,反之,若置换矩阵图形中不存在平行四边形,则不存在2个或以上的点重合,则该置换矩阵满足Costas序列的判定条件;

S32、对于一个已知的阶置换矩阵,所有元素“1”之间的相对位置的状态是确定的,并且相对位置所有可能情况的总个数是有限的,结合上文介绍的散列表的思想,利用一个有限长度的散列表记录元素“1”之间相对位置关系,通过散列函数将相对位置关系映射到散列表中,在生成置换矩阵时遍历准置换矩阵所有的相对位置关系;在遍历过程中,若散列表中对应键已存在映射则表明已存在同样相对位置关系的元素组合,即在准置换矩阵图形中形成了平行四边形,可判断基于该准置换矩阵不可能构成Costas序列,否则当递归判定结束时,散列表的键没有产生冲突说明生成了一个置换矩阵,且该矩阵满足Costas序列判定条件;

S33、实现judge(参数);以及

S34、置换矩阵生成方法和对置换矩阵的判定交叉进行。

3.根据权利要求2所述的方法,其特征在于:步骤S33实现judge(参数)步骤为:(1)If(参数满足要求),

(2)存储记录数组到结果集合中,

(3)Else,

(4)遍历相对位置,

(5)设置散列表并判断,

(6)If(散列表中该位置已存在映射),

(7)结束递归,

(8)Else,

(9)nodes.delete();

(10)填充到记录数组元素,

(11)judge(参数)//进入下一层递归,

(12)nodes.insert();

(13)End。

4.根据权利要求1所述的方法,其特征在于:步骤S4启用线程池技术,创建多线程结合工作窃取机制,完成S2,S3的递归迭代生成置换矩阵,并进行判定,其中线程池线程调度策略具体如下:(1)、检查线程池的核心线程数,如果存在空闲线程,就用空闲线程执行任务,否则,进入(2);

(2)、检查线程池任务队列状态,如果任务队列中执行的任务数量没有达到设定的最大容量,将提交的待执行任务加入任务队列中,否则,进入(3);

(3)、检查当前运行线程数是否等于最大线程数,如果等于就执行指定的饱和策略处理提交的任务,否则,创建新的线程执行新提交的任务。

5.一种基于多线程的Costas序列的搜索系统,其特征在于,执行权利要求1-4任一项所述方法。