并发下的搜索与排序

2017-02-15

概论

在传统的串行运行下，在数组内查找特定元素和将数组排序都有一套成熟的方法。

对于数组内查找，如果是有序数组在可以在查找的话可以运用二分查找法，而对于无序数组则应该将数组遍历一遍。

而对于数组排序，则是有类似快排，归并排序等等复杂度控制在O(nlogn）的算法。

从算法的角度来说，似乎并没有往下继续优化的空间了。但是如果运行在并行环境下，虽然理论上的算法复杂度并没有变小，但是我们可以用并行的方式来将时间缩短。

为何可以使用并行

考虑这么一件事情，如果我们将一堆苹果放在一个篮子里，那么我们唯一能做的做法就是将苹果一个个的依次放入篮子，这没什么好说的。那么如果我们要加快速度的话，我们会多派一个人手，比如将苹果堆一分为二，然后两个人分别将两堆苹果同时放到一个篮子里。但是如果我们考虑到我们希望放入苹果时，希望是一个红苹果一个青苹果间隔，那么在两个人毫无配合的情况下，这种方式反而不如一个人依次放入来的效果好。也就是说，运用并行的场景下，要求我们所处理的数据互相不干扰，那么你就可以使用并行来充分的利用起时间。

数组并行搜索

对于一个数组，我们想在里面找到元素a的下标，在串行模式中我们只能运用遍历的方式来搜索指定元素。但是如果我们将数组一分为二，然后将分配两个线程并行的单独搜索，那么CPU也就被更多的利用了。

以Java为例子，首先我们准备好线程池，并发数，原子性的Int与数组

static ExecutorService pool = Executors.newCachedThreadPool();
static final int Thread_Num = 2;
static AtomicInteger res = new AtomicInteger(-1);
static int[] arr;

然后我们在再编写每个线程所应该执行的搜索函数，规定了搜索值与搜索区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static int search(int searchValue,int beginPos,int endPos){

    for(int i = beginPos;i<endPos;i++){
        if(res.get()>=0){
            return res.get();
        }
        if(arr[i] == searchValue){
            System.out.println("Found");
            if( !res.compareAndSet(-1,i)){
                return res.get();
            }
            return i;
        }
    }
    return -1;
}

然后我们创建每个线程完成的任务，以Future模式声明，实现了Callable接口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public static class SearchTask implements Callable<Integer>{

    int begin,end,searchValue;

    public SearchTask(int begin, int end, int searchValue) {
        this.begin = begin;
        this.end = end;
        this.searchValue = searchValue;
    }

    @Override
    public Integer call() throws Exception {
        int re = search(searchValue,begin,end);
        return re;
    }
}

最好我们将搜索封装成一个函数即可，当中由于一个数组被切割成N份来并行搜索，我们可以用Arraylist来包装每个线程，从而遍历每个线程是否得到结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public static int pSearch(int searchValue) throws ExecutionException, InterruptedException {
    int subArrSize = arr.length/Thread_Num+1;
    List<Future<Integer>> re = new ArrayList<Future<Integer>>();
    for(int i = 0;i<arr.length;i++){
        int end = i +subArrSize;
        if(end>=arr.length){
            end = arr.length;
        }
        re.add(pool.submit(new SearchTask(i,end,searchValue)));
    }
    try {
        for (Future<Integer> fu : re) {
            if (fu.get() >= 0) {
                return fu.get();
            }
        }
        return -1;
    }finally {
        pool.shutdown();
    }
}

最后

许多串行情境下的算法，只要当中数据不相互影响，大部分都可以用并发的情境来充分利用CPU，下次我会分析下如何使用并发来数组排序