NO.64 分头行动：并行Search模式

关注本公众号，一天一个知识点，持续精进！

碎片时间|体系学习

今天是

2018年的第61天

这是代码荣耀的第117篇原创

今日难度系数 ：

预计阅读时间 ：5分钟

00、引言

搜索算法是常用算法；搜索功能也几乎是所有软件系统的标配功能。在《数据结构与算法》课程中，大都会讲到基于“二分法查找”的搜索算法，而该算法是以数据有序为前提；对于无序的数据集，则只能采用逐个比较查找的方法。

对于容量为N的大数据集，如果采用串行的查找方法，必然导致性能低下。那么，能否基于我们前期介绍的并发技术，大大提升查找的效率了？答案是肯定的！

01、并行查找

面对大而复杂的问题，我们常会按照“分而治之，各个击破”的思想来解决问题。同理，对于一个庞大的数据集合，我们可以将数据集合切割为N份；这样，我们就把一个大问题切分为了N个“子”问题，这些“子”问题的类型是一样的（那么就可以采用相同的技术手段来解决），并且相互独立。

利用并发技术解决多任务的问题。我们可以采用1个线程解决1个“子”问题，N个线程就对应于解决N个“子问题”；N个线程同时执行，当其中一个线程找到目标值时，就通知其他线程停止继续查找，立即返回查找结果。

02、编程实现

我们利用并发技术，按照“分而治之，各个击破”的思想，实现对一个无序数据集的并发查找，提升查找性能。具体实现见代码1，enjoy:

1

importjava.util.ArrayList;

importjava.util.List;

/**

* 适用场景:在大数据容量中查找相应的目标值数据量大得list

*/

publicclassParallelSearchDemo {

// 定义需要查询的无序数组

staticint[]arrayData=

{ 8, 4, 7, 2, 90, 12, 18, 23, 45, 69, 17, 19 };

// 定义查找的目标值

staticinttarget= 7;

// 定义线程池

staticExecutorServicethreadPool=

Executors.newCachedThreadPool();

// 定义同时运行的数据查找线程的数目

staticfinalintthread_num= 3;

//result变量用于储存查找到的变量在目标数组中的索引

//如果没有查找到目标变量则值为-1

staticAtomicIntegerresult=newAtomicInteger(-1);// 初始值定位-1

/**

* 在特定数据范围内，查找特定目标值的工具函数

*@paramsearchValue 查找的目标值

*@parambeginPos查找范围的开始位置

*@paramendPos查找范围的结束位置

*@return目标值在查找范围的位置

*/

publicstaticintsearch(intsearchValue,intbeginPos,intendPos) {

intj = 0;

for(j = beginPos; j

//如果其他线程已经找到目标值，则直接返回

//结束该线程，避免无效查找

if(result.get() >= 0) {

returnresult.get();

}

if(arrayData[j] == searchValue) {

//与-1进行比较，如果不等于-1，则表示其他线程已经“捷足先登”找到了目标值

//原子更新失败；并执行if块内的语句，返回result内的值，结束该线程

if(!result.compareAndSet(-1, j)) {

returnresult.get();

}

//如果等于-1，则表示其他线程还没有找到目标值，

//以原子方式将该值设置为给定的更新值

//并且直接返回，结束该线程

returnj;

}

}

//该范围没有找到目标值，结束该线程

return-1;

}

//数据查找线程

publicstaticclassSearchTaskimplementsCallable {

intbegin,end,searchValue;

publicSearchTask(intsearchValue,intbegin,intend) {

this.begin= begin;

this.end= end;

this.searchValue= searchValue;

}

//Callable接口需要实现的call函数

publicInteger call()throwsException {

intre =search(searchValue,begin,end);

returnre;

}

}

//将整个查找范围切割为N个查找域

//一个线程负责一个查找域；开启N个线程同时对这N个查找域进行查找

publicstaticintsearchWorker(intsearchValue)throwsInterruptedException,ExecutionException {

intsubArrSize =arrayData.length/thread_num+ 1;

List> re =newArrayList>();

//对查找范围进行切割，并开启一个线程对切割的查找域进行查找

for(inti = 0; i arrayData.length; i += subArrSize) {

intend = i + subArrSize;

if(end >=arrayData.length)end =arrayData.length;

//开启线程

re.add(threadPool.submit(newSearchTask(searchValue, i, end)));

}

//阻塞式的打捞计算结果

for(Future fu : re) {

if(fu.get() >= 0)return(fu.get());

}

return-1;

}

//测试客户端

publicstaticvoidmain(String[] args) {

try{

intindex =searchWorker(target);

}catch(InterruptedException e) {

e.printStackTrace();

}catch(ExecutionException e) {

e.printStackTrace();

}

}

}

该程序的输出结果见输出1。

输出1

欲查找的数据为:7;在目标数组中的索引为:2

03、小结

本文对并发查找算法进行了原理性说明，结合实例阐述并行查找模式如何实现。后续文章中我们将对更多、功能更强大的并发编程模型进行介绍，敬请期待。

上例中，我们实现了只要找到目标值就立即返回并结束继续查找；如果我们要查找目标值在数据集里的所有位置信息（因为该目标值可能会在数据集里出现多次），那么该如何实现了？请各位老铁在留言区踊跃留言、交流讨论。

如果本文对老铁有所启发，

请多转发、转载、打赏、点赞！