时间戳

首页 > 解决方案 > 如何在 Java 中使用多线程实现 2D 方阵乘法？

java - 如何在 Java 中使用多线程实现 2D 方阵乘法？

问题描述

我想使用 Java 中的多线程功能将两个方形 2D 矩阵相乘以节省时间。

做这个的最好方式是什么？我的首要任务是节省时间。

请看我写的代码。我正在寻找的解决方案是它会做我的代码所做的事情，但唯一的区别是执行时间。

多线程应该节省时间吧？

import java.io.BufferedWriter;
import java.io.FileWriter;
import java.io.IOException;
import java.util.Arrays;
import java.util.Date;
import java.util.Scanner;
import java.util.concurrent.TimeUnit;

public class ExtraTaskOS {

    // Generatining Random Number Method
    static int generateRandomNumber() {

        int number = (int) (Math.random() * (9 - 1)) + 1;
        return number;
    }

    public static void main(String[] args) throws IOException {

        // Store current time
        long startTime = System.nanoTime();

        Scanner sc = new Scanner(System.in);

        System.out.print("Enter number of Eelement for both Square Matrix: ");
        int n = sc.nextInt();


        // Generaing First Matrix
        int[][] matrix01 = new int[n][n];

        for (int i = 0; i < matrix01.length; i++) {
            for (int j = 0; j < matrix01.length; j++) {
                matrix01[i][j] = generateRandomNumber();
            }
        }

        // Writing Matrix01 to Text File
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < matrix01.length; i++)//for each row
        {
            for (int j = 0; j < matrix01.length; j++)//for each column
            {
                builder.append(matrix01[i][j] + "");//append to the output string
                if (j < matrix01.length - 1)//if this is not the last row element
                {
                    builder.append(",");//then add comma (if you don't like commas you can use spaces)
                }
            }
            builder.append("\n");//append new line at the end of the row
        }
        BufferedWriter writer = new BufferedWriter(new FileWriter("matrix01.txt"));
        writer.write(builder.toString());//save the string representation of the board
        writer.close();

        // Generating Second Matix
        int[][] matrix02 = new int[n][n];

        for (int i = 0; i < matrix02.length; i++) {
            for (int j = 0; j < matrix02.length; j++) {
                matrix02[i][j] = generateRandomNumber();
            }
        }

        // Writing Matrix02 to Text File
        StringBuilder builder2 = new StringBuilder();

        for (int i = 0; i < matrix02.length; i++)//for each row
        {
            for (int j = 0; j < matrix02.length; j++)//for each column
            {
                builder2.append(matrix02[i][j] + "");//append to the output string
                if (j < matrix02.length - 1)//if this is not the last row element
                {
                    builder2.append(",");//then add comma (if you don't like commas you can use spaces)
                }
            }
            builder2.append("\n");//append new line at the end of the row
        }
        BufferedWriter writer2 = new BufferedWriter(new FileWriter("matrix02.txt"));
        writer2.write(builder2.toString());//save the string representation of the board
        writer2.close();

        // Printing both 2D Arrays
        for (int[] arr : matrix01) {
            System.out.println(Arrays.toString(arr));
        }
        System.out.println("");
        for (int[] arr : matrix02) {
            System.out.println(Arrays.toString(arr));
        }

        // Multiplying both matrix
        int[][] productTwoMatrix = new int[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {

              for(int k=0; k<n; k++){
                productTwoMatrix[i][j] += matrix01[i][k] * matrix02[k][j];

              }  

            }
        }

        // Printing Result
        System.out.println("\nResult: ");
        for (int[] arr : productTwoMatrix) {
            System.out.println(Arrays.toString(arr));
        }

        // Calculate Execution time
        long endTime = System.nanoTime();
        long totalTime = endTime - startTime;
        long timeInMiliSecond = (totalTime / 1_000_000);
        System.out.println("Execution Time: "+ timeInMiliSecond + " miliseconds");


    }

}

使用多线程的新代码应该可以节省时间。

标签： javaarraysmultithreadingmatrixmultidimensional-array

解决方案

第一：学习如何正确测量你的代码。你做

// Store current time
long startTime = System.nanoTime();

甚至在您询问用户的输入之前。然后您执行文件 IO 并将各种内容打印到 System.out。提示：这些动作中的每一个都可能需要数百毫秒，等待人类输入一个数字......可能需要几个小时。因此：只测量对您真正重要的部分（即乘法部分）。测量时也要避免各种IO操作！

你看，一百毫秒，这听起来并不多，但是当你进行正确的测量时，你会发现你的 CPU 可以在 100 毫秒内做很多事情（如果你不一直用 IO 工作打扰它的话） .

关于多线程，你也走错了兔子洞：

我想使用 Java 中的多线程功能将两个方形 2D 矩阵相乘以节省时间。

那是（几乎）没有意义的。您会看到，CPU 密集型工作负载不会从使用多个线程中获益。最后，CPU 需要转向内存，获取值，进行一些计算，然后将值写回内存。并行执行并不一定会让事情进展得更快。相反，你首先要“支付”各种罚款：

  • 创建线程并不是一项廉价的操作。您必须确定处理数以千计的元素，然后才能单独new Thread()弥补价格标签。
  • 当我们谈论巨大的数组时（正如所说：使用多个线程时，小数组肯定会给你带来更糟糕的结果）......那么从内存中请求数据的顺序就很重要了。你知道，CPU 有缓存。缓存未命中可能非常昂贵。猜猜当你有多个线程访问矩阵的不同部分时会发生什么？确切地说：您很可能会导致：缓存未命中。

如果我没有劝阻您，而您实际上是出于学习目的而这样做，那么答案很简单。矩阵乘法通过获取一行的值和另一矩阵的一列的值来工作，您将结果相乘并求和。

现在：不是让一个线程进入三个循环来做这些事情，例如，您可以让一个线程计算结果矩阵的第一行，第二个线程计算第二行，依此类推。

这里的好处是：您可以简单地“切片”需要处理的数据。没有结果值依赖于其他结果，所以完全不需要同步。您可以使用 1 个线程、2 个、4 个、n 个线程，几乎可以使用尽可能多的线程。

我的建议是：

  • 不要要求用户输入任何内容。只需生成固定大小的矩阵，可能是 100x100、1000x1000、10000x10000。
  • 也许播种您的随机数生成器，以便所有乘法运算都对完全相同的数据进行。- 最后不要打印整个数组（因为如上所述：使用大数组）。适合您屏幕的阵列太小，无法为您提供任何有意义的测量结果。但是例如总结最终矩阵（为了避免 JIT 优化整个操作：您必须确保以某种方式使用您的操作的某些结果）
  • 尝试编写允许您快速更改线程数而不更改其他任何内容的代码。这样您就可以使用 1、2、4、8、16 个线程。

当你完成使用原始的“裸机”线程时，复制你的代码，删除所有线程的东西，然后尝试使用ExecutorService实现矩阵乘法。如果可行，请更进一步，查看Futures并思考如何在此处使用它们。

如前所述：你不应该为了表现而这样做。您编写此类代码的唯一充分理由是学习如何去做（对）。

推荐阅读