完数的Java多线程并行程序设计-并行计算

朴灿烈づ我的快乐病毒、 2022-07-16 13:43 207阅读 0赞

1.问题描述... 2

2.算法设计... 2

2.1 串行算法设计... 2

2.2 使用Runnable接口实现并行的算法设计... 3

2.3继承Thread类实现并行的算法设计... 3

2.4 理论加速比分析... 3

3.使用Runnable接口的并行算法实现... 4

3.1 代码及注释... 4

3.2 执行结果截图... 6

3.3 实验加速比分析... 6

4.继承Thread类的并行算法实现... 6

4.1 代码及注释... 6

4.2 执行结果截图... 8

4.3 实验加速比分析... 9

# 1.问题描述 #

一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3，再如8的因子和是7（即1+2+4），8不是完数。输入一个数n，编程找出n以内的所有完数及其个数。

# 2.算法设计 #

## 2.1 串行算法设计 ##

串行算法步骤如下：

①因为1不算入一个完数，所以令数i=2，初始化答案值ans=0；

②因为1是任何数的一个因数，所以可初始化因数之和sum=1；

③令数k=2；

④如果数i能整除数k，说明k是i的一个因数，则sum += k；

⑤若k<=i/2（控制范围保证i%k能进行计算），++k，转到④，否则转到⑥；

⑥若sum = i，++ans；

⑦若i <=n，++i，转到②，否则转到⑧；

⑧函数返回答案值ans。

## 2.2 使用Runnable接口实现并行的算法设计 ##

并行算法步骤如下：

①定义好run()方法，以实现了run()方法的work类为参数创建系统类Thread的对象，来继承定义好的run()方法；

②两个线程分别从2~n和3~n开始并行执行计算；

③执行完毕将两个线程的结果求和；

④串行执行2~n的计算。

## 2.3继承Thread类实现并行的算法设计 ##

并行算法步骤如下：

①在Number类中定义一个Thread类，在主函数中创建两个线程，使这两个线程并行执行；

②两个线程分别从2~n和3~n开始并行执行计算；

③执行完毕将两个线程的结果求和；

④串行执行2~n的计算。

## 2.4 理论加速比分析 ##

若p个处理器上数据量为n，则S=np/（n+2plogp）。

本机测试中，p=2：若n=10000，则S=1.99976；若n=100000，则S=1.99998。

# 3.使用Runnable接口的并行算法实现 #

## 3.1 代码及注释 ##

/*问题描述：一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3，再如8的因子和是7（即1+2+4），8不是完数。编程找出n以内的所有完数。
    */
    //
     
    importjava.util.Scanner;
    public class Number
    {
        public static void main(String[] args) throws InterruptedException
        {
           System.out.print("请输入n=");
           Scanner input = newScanner(System.in);
           long n = input.nextInt();//计算范围是1~n
                                 /********并行*******/
                                 //1不是完数分成两个线程，分别从2和3开始
           work work1 = newwork(2, n);
           work work2 = newwork(3, n);
           Thread thread1 = newThread(work1);
           Thread thread2 = newThread(work2);
           long startTime = System.currentTimeMillis();
           thread1.start();//启动线程
           thread2.start();
           thread1.join();
           thread2.join();
           long endTime = System.currentTimeMillis();
           System.out.println("并行结果=" +(work1.getSum() + work2.getSum()));//两个线程的结果求和
           System.out.println("并行时间=" +(endTime - startTime));
           /********串行*******/
           startTime = System.currentTimeMillis();
           work work = newwork(2, n);
           long sum = work.sum();
           endTime = System.currentTimeMillis();
           System.out.println("串行结果=" +sum);
           System.out.println("串行时间=" +(endTime - startTime));
        }
    }
    class work implements Runnable
    {
        private   longstart;
        private   longend;
        private   long sum= 0;
     
        public work(long start, long end)
        {
           super();
           this.start = start;
           this.end = end;
        }
        public void run()
        {
           for (long i = start; i <= end; i += 2)  //1不算入一个完数。
           {
               longtemp = 1;                 //数的因数之和,1是任何数的一个因数。
               for (long k =2; k <= i / 2; k++)  //k<=i/2是要保证i%k能进行计算。
                  if(i%k == 0)
                      temp += k;       //因数之和
               if(temp == i)       //找到一个完数
                  ++sum;                 //函数返回答案值
           }
        }
     
        public long sum()
        {
           for (long i = start; i <= end; i++)  //1不算入一个完数。
           {
               longtemp = 1;                 //数的因数之和,1是任何数的一个因数。
               for (long k =2; k <= i / 2; k++)  //k<=i/2是要保证i%k能进行计算。
                  if(i%k == 0)
                      temp += k;       //因数之和
               if(temp == i)       //找到一个完数
                  ++sum;                 //函数返回答案值
           }
           return sum;
        }
        public long getSum()
        {
            returnsum;
        }
    }

## 3.2 执行结果截图 ##

（1）小数据量验证正确性的执行结果截图（不考虑加速比）

![20161119152532155][]

（2）大数据量获得较好加速比的执行结果截图

（体现串行时间、并行时间和好的加速比）

![20161119152536612][]

## 3.3 实验加速比分析 ##

若n=10000，S=Ts/Tp=1.9083；若n=100000，S=Ts/Tp=1.9636。

实验加速比与理论加速比相差不大，在误差允许范围内可认为结果正确。

# 4.继承Thread类的并行算法实现 #

## 4.1 代码及注释 ##

/*问题描述：一个数如果恰好等于它的因子之和，这个数就称为“完数”。例如6=1＋2＋3，再如8的因子和是7（即1+2+4），8不是完数。编程找出n以内的所有完数。
    */
    //
    importjava.util.Scanner;
    public class Number extends Thread
    {
        private   longstart;
        private   longend;
        private   long sum= 0;
     
        public Number(long start, long end)
        {
           super();
           this.start = start;
           this.end = end;
        }
     
        public void run()
        {
           for (long i = start; i <= end; i += 2)  //1不算入一个完数。
           {
               longtemp = 1;                 //数的因数之和,1是任何数的一个因数。
               for (long k =2; k <= i / 2; k++)  //k<=i/2是要保证i%k能进行计算。
                  if(i%k == 0)
                      temp+= k;       //因数之和
               if(temp == i)       //找到一个完数
                  ++sum;                 //函数返回答案值
           }
        }
        public long sum()
        {
           for (long i = start; i <= end; i++)  //1不算入一个完数。
           {
               longtemp = 1;                 //数的因数之和,1是任何数的一个因数。
               for (long k =2; k <= i / 2; k++)  //k<=i/2是要保证i%k能进行计算。
                  if(i%k == 0)
                      temp += k;       //因数之和
               if(temp == i)       //找到一个完数
                  ++sum;                 //函数返回答案值
           }
           return sum;
        }
        public long getSum()
        {
           return sum;
        }
        public static void main(String[] args) throws InterruptedException
        {
           System.out.print("请输入n=");
           Scanner input = newScanner(System.in);
           long n = input.nextInt();//计算范围是1~n
                                 /**********并行**********/
           Number thread1 = newNumber(2, n);//1不计入完数
           Number thread2 = newNumber(3, n);
           long startTime = System.currentTimeMillis();
           thread1.start();
           thread2.start();
           thread1.join();
           thread2.join();
           long endTime = System.currentTimeMillis();
           System.out.println("并行结果=" +(thread1.getSum() + thread2.getSum()));
           System.out.println("并行时间=" +(endTime - startTime));
           /**********串行**********/
           startTime = System.currentTimeMillis();
           Number serial = newNumber(2, n);
           long sum = serial.sum();
           endTime = System.currentTimeMillis();
           System.out.println("串行结果=" +sum);
           System.out.println("串行时间=" +(endTime - startTime));
        }
    }

## 4.2 执行结果截图 ##

（1）小数据量验证正确性的执行结果截图（不考虑加速比）

![20161119152613078][]

（2）大数据量获得较好加速比的执行结果截图

（体现串行时间、并行时间和好的加速比）

![20161119152617284][]

## 4.3 实验加速比分析 ##

若n=10000，S=Ts/Tp=2.0436；若n=100000，S=Ts/Tp=1.8717。

实验加速比与理论加速比相差不大，在误差允许范围内可认为结果正确。

[20161119152532155]: /images/20220715/dc074d2c8072430e8bdeec6d043df486.png
[20161119152536612]: /images/20220715/bf8365916e8b4e0ca38e4b4dcff062e3.png
[20161119152613078]: /images/20220715/023bdabb37104930aaf41f2ac5cabbdd.png
[20161119152617284]: /images/20220715/433bc84c622e430fa542e6594cb3bb54.png