算法导论第4章strassen算法JAVA实现

2024-06-02 16:38
文章标签 java 算法 实现 导论 strassen

本文主要是介绍算法导论第4章strassen算法JAVA实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 

今天看了strassen算法，用java实现了一下。

另外题目4.2-3，如何修改Strassen算法，使之适应矩阵规模n不是2的幂的情况？

答：添加额外的行或列使之成为2的幂的方阵，添加的行或列均为0即可。

 

文章中提到在分解矩阵时使用复杂度为θ(1)的下标运算，本人为了方便，是采用拷贝赋值的方式进行的矩阵分解。

 

package answers.chapter04;import java.util.Arrays;public class MatrixMultiply {public static void SquareMatrixMultiply(int A[][], int B[][]) {int rows = A.length;int C[][] = new int[rows][rows];for (int i = 0; i < rows; i++) {for (int j = 0; j < rows; j++) {C[i][j] = 0;for (int k = 0; k < rows; k++) {C[i][j] += A[i][k] * B[k][j];}}}displaySquare(C);}public static void displaySquare(int matrix[][]) {for (int i = 0; i < matrix.length; i++) {for (int j : matrix[i]) {System.out.print(j+" ");}System.out.println();}}public static void copyToMatrixArray(int srcMatrix[][], int startI, int startJ, int iLen, int jLen, int destMatrix[][]) {for (int i = startI; i < startI + iLen; i++) {for (int j = startJ; j < startJ + jLen; j++) {destMatrix[i - startI][j - startJ] = srcMatrix[i][j]; }}}public static void copyFromMatrixArray(int destMatrix[][], int startI, int startJ, int iLen, int jLen, int srcMatrix[][]) {for (int i = 0; i < iLen; i++) {for (int j = 0; j < jLen; j++) {destMatrix[startI + i][startJ + j] = srcMatrix[i][j]; }}}public static void squareMatrixAdd(int A[][], int B[][], int C[][]) {for (int i = 0; i < A.length; i++) {for (int j = 0; j < A[i].length; j++) {C[i][j] = A[i][j] + B[i][j];}}}public static void squareMatrixSub(int A[][], int B[][], int C[][]) {for (int i = 0; i < A.length; i++) {for (int j = 0; j < A[i].length; j++) {C[i][j] = A[i][j] - B[i][j];}}}public static int[][] squareMatrixMultiplyRecursive(int A[][], int B[][]) {int n = A.length;int C[][] = new int[n][n];if (n == 1) {C[0][0] = A[0][0] * B[0][0];} else {int A11[][], A12[][], A21[][], A22[][];int B11[][], B12[][], B21[][], B22[][];int C11[][], C12[][], C21[][], C22[][];A11 = new int[n/2][n/2];A12 = new int[n/2][n/2];A21 = new int[n/2][n/2];A22 = new int[n/2][n/2];copyToMatrixArray(A, 0, 0, n/2, n/2, A11);copyToMatrixArray(A, 0, n/2, n/2, n/2, A12);copyToMatrixArray(A, n/2, 0, n/2, n/2, A21);copyToMatrixArray(A, n/2, n/2, n/2, n/2, A22);B11 = new int[n/2][n/2];B12 = new int[n/2][n/2];B21 = new int[n/2][n/2];B22 = new int[n/2][n/2];copyToMatrixArray(B, 0, 0, n/2, n/2, B11);copyToMatrixArray(B, 0, n/2, n/2, n/2, B12);copyToMatrixArray(B, n/2, 0, n/2, n/2, B21);copyToMatrixArray(B, n/2, n/2, n/2, n/2, B22);C11 = new int[n/2][n/2];C12 = new int[n/2][n/2];C21 = new int[n/2][n/2];C22 = new int[n/2][n/2];squareMatrixAdd(squareMatrixMultiplyRecursive(A11, B11), squareMatrixMultiplyRecursive(A12, B21),C11);squareMatrixAdd(squareMatrixMultiplyRecursive(A11, B12), squareMatrixMultiplyRecursive(A12, B22),C12);squareMatrixAdd(squareMatrixMultiplyRecursive(A21, B11), squareMatrixMultiplyRecursive(A22, B21),C21);squareMatrixAdd(squareMatrixMultiplyRecursive(A21, B12), squareMatrixMultiplyRecursive(A22, B22),C22);copyFromMatrixArray(C, 0, 0, n/2, n/2, C11);copyFromMatrixArray(C, 0, n/2, n/2, n/2, C12);copyFromMatrixArray(C, n/2, 0, n/2, n/2, C21);copyFromMatrixArray(C, n/2, n/2, n/2, n/2, C22);}return C;}public static int[][] strassenMatrixMultiplyRecursive(int A[][], int B[][]) {int n = A.length;int C[][] = new int[n][n];if (n == 1) {C[0][0] = A[0][0] * B[0][0];} else {int A11[][], A12[][], A21[][], A22[][];int B11[][], B12[][], B21[][], B22[][];int C11[][], C12[][], C21[][], C22[][];int S1[][], S2[][], S3[][], S4[][], S5[][], S6[][], S7[][], S8[][], S9[][], S10[][];int P1[][], P2[][], P3[][], P4[][], P5[][], P6[][], P7[][];A11 = new int[n/2][n/2];A12 = new int[n/2][n/2];A21 = new int[n/2][n/2];A22 = new int[n/2][n/2];copyToMatrixArray(A, 0, 0, n/2, n/2, A11);copyToMatrixArray(A, 0, n/2, n/2, n/2, A12);copyToMatrixArray(A, n/2, 0, n/2, n/2, A21);copyToMatrixArray(A, n/2, n/2, n/2, n/2, A22);B11 = new int[n/2][n/2];B12 = new int[n/2][n/2];B21 = new int[n/2][n/2];B22 = new int[n/2][n/2];copyToMatrixArray(B, 0, 0, n/2, n/2, B11);copyToMatrixArray(B, 0, n/2, n/2, n/2, B12);copyToMatrixArray(B, n/2, 0, n/2, n/2, B21);copyToMatrixArray(B, n/2, n/2, n/2, n/2, B22);S1 = new int[n/2][n/2];S2 = new int[n/2][n/2];S3 = new int[n/2][n/2];S4 = new int[n/2][n/2];S5 = new int[n/2][n/2];S6 = new int[n/2][n/2];S7 = new int[n/2][n/2];S8 = new int[n/2][n/2];S9 = new int[n/2][n/2];S10 = new int[n/2][n/2];squareMatrixSub(B12, B22, S1);squareMatrixAdd(A11, A12, S2);squareMatrixAdd(A21, A22, S3);squareMatrixSub(B21, B11, S4);squareMatrixAdd(A11, A22, S5);squareMatrixAdd(B11, B22, S6);squareMatrixSub(A12, A22, S7);squareMatrixAdd(B21, B22, S8);squareMatrixSub(A11, A21, S9);squareMatrixAdd(B11, B12, S10);P1 = new int[n/2][n/2];P2 = new int[n/2][n/2];P3 = new int[n/2][n/2];P4 = new int[n/2][n/2];P5 = new int[n/2][n/2];P6 = new int[n/2][n/2];P7 = new int[n/2][n/2];P1 = strassenMatrixMultiplyRecursive(A11, S1);P2 = strassenMatrixMultiplyRecursive(S2, B22);P3 = strassenMatrixMultiplyRecursive(S3, B11);P4 = strassenMatrixMultiplyRecursive(A22, S4);P5 = strassenMatrixMultiplyRecursive(S5, S6);P6 = strassenMatrixMultiplyRecursive(S7, S8);P7 = strassenMatrixMultiplyRecursive(S9, S10);C11 = new int[n/2][n/2];C12 = new int[n/2][n/2];C21 = new int[n/2][n/2];C22 = new int[n/2][n/2];int temp[][] = new int[n/2][n/2];squareMatrixAdd(P5, P4, temp);squareMatrixSub(temp, P2, temp);squareMatrixAdd(temp, P6, C11);squareMatrixAdd(P1, P2, C12);squareMatrixAdd(P3, P4, C21);squareMatrixAdd(P5, P1, temp);squareMatrixSub(temp, P3, temp);squareMatrixSub(temp, P7, C22);copyFromMatrixArray(C, 0, 0, n/2, n/2, C11);copyFromMatrixArray(C, 0, n/2, n/2, n/2, C12);copyFromMatrixArray(C, n/2, 0, n/2, n/2, C21);copyFromMatrixArray(C, n/2, n/2, n/2, n/2, C22);}return C;}public static int sMatrixA[][] = new int[][] {{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},{1, 2, 3, 4, 5, 6, 7, 8},};public static int sMatrixB[][] = new int[][] {{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},{5, 6, 7, 8, 1, 2, 3, 4},};public static void main(String[] args) {System.out.println("普通矩阵乘法");SquareMatrixMultiply(sMatrixA, sMatrixB);System.out.println("\n递归矩阵乘法");int C[][] = squareMatrixMultiplyRecursive(sMatrixA, sMatrixB);displaySquare(C);System.out.println("\n Strassen 递归矩阵乘法");C = strassenMatrixMultiplyRecursive(sMatrixA, sMatrixB);displaySquare(C);}
}

这篇关于算法导论第4章strassen算法JAVA实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1024516。

相关文章

Java中流式并行操作parallelStream的原理和使用方法

Java中流式并行操作parallelStream的原理和使用方法

《Java中流式并行操作parallelStream的原理和使用方法》本文详细介绍了Java中的并行流（parallelStream）的原理、正确使用方法以及在实际业务中的应用案例,并指出在使用并行流... 目录Java中流式并行操作parallelStream0. 问题的产生1. 什么是parallelS
阅读更多...
C++中unordered_set哈希集合的实现

C++中unordered_set哈希集合的实现

《C++中unordered_set哈希集合的实现》std::unordered_set是C++标准库中的无序关联容器,基于哈希表实现,具有元素唯一性和无序性特点,本文就来详细的介绍一下unorder... 目录一、概述二、头文件与命名空间三、常用方法与示例1. 构造与析构2. 迭代器与遍历3. 容量相关4
阅读更多...
Java中Redisson 的原理深度解析

Java中Redisson 的原理深度解析

《Java中Redisson的原理深度解析》Redisson是一个高性能的Redis客户端,它通过将Redis数据结构映射为Java对象和分布式对象,实现了在Java应用中方便地使用Redis,本文... 目录前言一、核心设计理念二、核心架构与通信层1. 基于 Netty 的异步非阻塞通信2. 编解码器三、
阅读更多...
C++中悬垂引用(Dangling Reference) 的实现

C++中悬垂引用(Dangling Reference) 的实现

《C++中悬垂引用(DanglingReference)的实现》C++中的悬垂引用指引用绑定的对象被销毁后引用仍存在的情况,会导致访问无效内存,下面就来详细的介绍一下产生的原因以及如何避免,感兴趣... 目录悬垂引用的产生原因1. 引用绑定到局部变量，变量超出作用域后销毁2. 引用绑定到动态分配的对象，对象
阅读更多...
SpringBoot基于注解实现数据库字段回填的完整方案

SpringBoot基于注解实现数据库字段回填的完整方案

《SpringBoot基于注解实现数据库字段回填的完整方案》这篇文章主要为大家详细介绍了SpringBoot如何基于注解实现数据库字段回填的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以了解... 目录数据库表pom.XMLRelationFieldRelationFieldMapping基础的一些代
阅读更多...
一篇文章彻底搞懂macOS如何决定java环境

一篇文章彻底搞懂macOS如何决定java环境

《一篇文章彻底搞懂macOS如何决定java环境》MacOS作为一个功能强大的操作系统,为开发者提供了丰富的开发工具和框架,下面：本文主要介绍macOS如何决定java环境的相关资料,文中通过代码... 目录方法一：使用 which命令方法二：使用 Java_home工具（Apple 官方推荐）那问题来了，
阅读更多...
Java HashMap的底层实现原理深度解析

Java HashMap的底层实现原理深度解析

《JavaHashMap的底层实现原理深度解析》HashMap基于数组+链表+红黑树结构,通过哈希算法和扩容机制优化性能,负载因子与树化阈值平衡效率,是Java开发必备的高效数据结构,本文给大家介绍... 目录一、概述：HashMap的宏观结构二、核心数据结构解析1. 数组（桶数组）2. 链表节点（Node
阅读更多...
Java AOP面向切面编程的概念和实现方式

Java AOP面向切面编程的概念和实现方式

《JavaAOP面向切面编程的概念和实现方式》AOP是面向切面编程,通过动态代理将横切关注点（如日志、事务）与核心业务逻辑分离,提升代码复用性和可维护性,本文给大家介绍JavaAOP面向切面编程的概... 目录一、AOP 是什么？二、AOP 的核心概念与实现方式核心概念实现方式三、Spring AOP 的关
阅读更多...
详解SpringBoot+Ehcache使用示例

详解SpringBoot+Ehcache使用示例

《详解SpringBoot+Ehcache使用示例》本文介绍了SpringBoot中配置Ehcache、自定义get/set方式,并实际使用缓存的过程,文中通过示例代码介绍的非常详细,对大家的学习或者... 目录摘要概念内存与磁盘持久化存储：配置灵活性：编码示例引入依赖：配置ehcache.XML文件：配置
阅读更多...
Java 虚拟线程的创建与使用深度解析

Java 虚拟线程的创建与使用深度解析

《Java虚拟线程的创建与使用深度解析》虚拟线程是Java19中以预览特性形式引入,Java21起正式发布的轻量级线程,本文给大家介绍Java虚拟线程的创建与使用,感兴趣的朋友一起看看吧... 目录一、虚拟线程简介1.1 什么是虚拟线程？1.2 为什么需要虚拟线程？二、虚拟线程与平台线程对比代码对比示例：三
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2