Question

搜索是几乎每一个软件都必不可少的功能。对于有序数据，通常可以采用二分查找法。对于无序数据，则只能挨个查找。在本节中，我们将讨论有关并行的无序数组的搜索实现。

给定一个数组，我们要查找满足条件的元素。对于串行程序来说，只要遍历一下数组就可以得到结果。但如果要使用并行方式，则需要额外增加一些线程间的通信机制，使各个线程可以有效地运行。

一种简单的策略就是将原始数据集合按照期望的线程数进行分割。如果我们计划使用两个线程进行搜索，那么就可以把一个数组或集合分割成两个。每个线程各自独立搜索，当其中有一个线程找到数据后，立即返回结果即可。

现在假设有一个整型数组，我们需要查找数组内的元素：

static int[] arr;

定义线程池、线程数量以及存放结果的变量result。在result中，我们会保存符合条件的元素在arr数组中的下标。默认为-1，表示没有找到给定元素。

static ExecutorService pool = Executors.newCachedThreadPool();
static final int Thread_Num=2;
static AtomicInteger result=new AtomicInteger(-1);

并发搜索会要求每个线程查找arr中的一段，因此，搜素函数必须指定线程需要搜索的起始和结束位置：

01 public static int search(int searchValue,int beginPos,int endPos){
02   int i=0;
03   for(i=beginPos;i＜endPos;i++){
04     if(result.get()＞=0){
05       return result.get();
06     }
07     if(arr[i] == searchValue){
08       //如果设置失败，表示其他线程已经先找到了
09       if(!result.compareAndSet(-1, i)){
10         return result.get();
11       }
12       return i;
13     }
14   }
15   return -1;
16 }

上述代码第4行，首先通过result判断是否已经有其他线程找到了需要的结果。如果已经找到，则立即返回不再进行查找。如果没有找到，则进行下一步搜索。第7行代码成立则表示当前线程找到了需要的数据，那么就会将结果保存到result变量中。这里使用CAS操作，如果设置失败，则表示其他线程已经先我一步找到了结果。因此，可以无视失败的情况，找到结果后，进行返回。

定义一个线程进行查找，它会调用前面的pSearch()方法：

01 public static class SearchTask implements Callable＜Integer＞{
02   int begin,end,searchValue;
03   public SearchTask(int searchValue,int begin,int end){
04     this.begin=begin;
05     this.end=end;
06     this.searchValue=searchValue;
07   }
08   public Integer call(){
09     int re= search(searchValue,begin,end);
10     return re;
11   }
12 }

最后是pSearch()并行查找函数，它会根据线程数量对arr数组进行划分，并建立对应的任务提交给线程池处理：

01 public static int pSearch(int searchValue) throws InterruptedException,
ExecutionException{
02   int subArrSize=arr.length/Thread_Num+1;
03   List＜Future＜Integer＞＞ re=new ArrayList＜Future＜Integer＞＞();
04   for(int i=0;i＜arr.length;i+=subArrSize){
05     int end = i+subArrSize;
06     if(end＞=arr.length)end=arr.length;
07     re.add(pool.submit(new SearchTask(searchValue,i,end)));
08   }
09   for(Future＜Integer＞ fu:re){
10     if(fu.get()＞=0)return fu.get();
11   }
12   return -1;
13 }

上述代码中使用了JDK内置的Future模式，其中第4～8行将原始数组arr划分为若干段，并根据划分结果建立子任务。每一个子任务都会返回一个Future对象，通过Future对象可以获得线程组得到的最终结果。在这里，由于线程之间通过result共享彼此的信息，因此只要当一个线程成功返回后，其他线程都会立即返回。因此，不会出现由于排在前面的任务长时间无法结束而导致整个搜索结果无法立即获取的情况。