多线程查找数组的最大值和最小值

Tue May 12 13:14:53 CST 2015 3897 Java

文章摘要给一个大数组,要求用多线程找出数组的最大值和最小值。策略是分治思想,将数组均分为n段,然后启动n个线程分别对每一段进行查找操作。

有一个大数组,要求使用多线程来找出数组的最大值、最小值。一个可行的策略是分治思想,将数组均分为n段,然后启动n个线程分别对每一段进行查找操作。

关键点是多个线程之间的通信:如何知道哪个部分找到的是最大值是最终的最大值?什么时候主线程可以认为多个线程已经完成了查找操作?

  1. 可以引入信号量机制,设置四个静态成员变量min,max,threadCount,isStarted,其中min和max用来记录最小值最大值,threadCount用来记录正在运行中的线程个数,isStarted用来表示是否已经有线程运行过了。但对这四个成员变量的访问一定要经过同步控制;

  2. 也可以在每个线程都查找完它们各自负责部分的最大最小值,然后在这些最大最小值里面找出最终的最大最小值。这种方法可以利用Java中concurrent包提供的FutureTask类来进行操作。


下面是方法1的Java代码:

package com.chenzuhuang.main;
public class ThreadSearch implements Runnable{
    //下面两个静态成员变量需要通过用关键字synchronized修饰 的方法来访问
    private static int min = Integer.MAX_VALUE;        //初始最小值
    private static int max = Integer.MIN_VALUE;            //初始最大值
     
    //下面为成员变量,每个线程对象私有
    private int[] nums;            //待查找数组
    private int low;                  //当前线程对象需要处理的数组开始下标
    private int high;                 //当前线程对象需要处理的数组结束下标
     
    //构造方法,传入待查找数组、开始下标和结束下标
    public ThreadSearch(int[] nums, int low, int high){
        this.nums = nums;
        this.low = low;
        this.high = high;
    }
 
    //线程run方法
    @Override
    public void run() {
        //在当前线程负责的数组部分里面查找最小、最大值
        for(int i=low; i<=high; i++){
            if(nums[i]<min) {
                ThreadSearch.setMin(nums[i]);
            }
            else if(nums[i]>max) {
                ThreadSearch.setMax(nums[i]);
            }
        }
    }
 
    //下面为各个对静态成员变量加锁的访问方法
    public static synchronized int getMin() {
        return min;
    }
    public static synchronized void setMin(int min) {
        ThreadSearch.min = min;
    }
    public static synchronized int getMax() {
        return max;
    }
    public static synchronized void setMax(int max) {
        ThreadSearch.max = max;
    }
     
    //程序入口,main方法
    public static void main(String[] args) throws InterruptedException {
        //测试数组
        int[] nums = new int[]{8,4,5,1,5,7,5,4,45,45,4,8,7,8,7,7,8,9,5,4,9,5,5,4,9,8,7,44,5,55,6,6,3,6,5,4,6,8,7,5,6,5,8,4,5,6,123,9,8,999,454};
         
        //创建两个线程,并启动之
        Thread t1 = new Thread(new ThreadSearch(nums, 0, nums.length/2));
        Thread t2 = new Thread(new ThreadSearch(nums, nums.length/2, nums.length-1));
         
        //启动两个查找子线程
        t1.start();
        t2.start();
      
        //主线程等待两个查找子线程结束
        t1.join();
        t2.join();
        
        //输出结果
        System.out.println("The min is "+ThreadSearch.min);
        System.out.println("The max is "+ThreadSearch.max);
    }
}


下面是方法2的Java代码

import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.FutureTask;


public class FutureTest {
	
	/**
	 * 实现Callable接口,在call方法里进行查找最大值、最小值操作
	 * @author zuhuang.chen
	 *
	 */
	public static class Task implements Callable<int[]>{
		private int[] nums;		
		private int low;		//该异步任务负责的部分开始下标
		private int height;		//该异步任务负责的部分结束下标
		
		public Task(int[] nums, int low, int height){
			this.nums= nums;
			this.low = low;
			this.height = height;
		}
		
		//返回int[]数组,int[0]保存最小值,int[1]保存最大值
		@Override
		public int[] call() throws Exception {
			int min = nums[low];
			int max = nums[low];
			
			for(int i = low+1; i <= height; i++){
				if(nums[i] < min){
					min = nums[i];
				}
				else if(nums[i] > max){
					max = nums[i];
				}
			}
			int[] result = new int[2];
			result[0] = min;
			result[1] = max;
			return result;
		}
		
	}
	
	public static void main(String[] args) throws InterruptedException, ExecutionException{
		int[] nums = new int[]{8,4,5,1,5,7,5,4,45,45,4,8,7,8,7,7,8,9,5,4,9,5,5,4,9,8,7,44,5,55,6,6,3,6,5,4,6,8,7,5,6,5,8,4,5,6,123,9,8,999,454};
		
		FutureTask<int[]> task1 = new FutureTask<int[]>(new Task(nums, 0, nums.length/2));
		FutureTask<int[]> task2 = new FutureTask<int[]>(new Task(nums, nums.length/2, nums.length-1));
		
		new Thread(task1).start();
		new Thread(task2).start();
		
		//等待异步任务返回,并获得两个异步任务的结果
		int[] result1 = task1.get();
		int[] result2 = task2.get();
		
		int min = result1[0]<result2[0] ? result1[0]:result2[0];
		int max = result1[1]>result2[1] ? result1[1]:result2[1];
	
		System.out.println("The min is " + min);
		System.out.println("The max is " + max);
	}
}




打赏
打赏

分享到: