JAVA-稀疏矩阵

简介: JAVA-稀疏矩阵

稀疏矩阵的压缩与还原(Java实现)


稀疏矩阵的概念


在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为稀疏矩阵,如:

20190829090621613.png


稀疏矩阵的压缩


如果要把一个含有如此多0元素的稀疏矩阵存储到计算机中,这些没有意义的0同样地会消耗掉计算机的内存,那么这势必造成计算机内存的浪费。那么,对于稀疏矩阵的存储,我们应该如何去处理呢?下面介绍一个例子:


例: 现在要模拟一个11*11的五子棋棋盘的存档和续局。棋盘上有黑、白两种棋子,分别用1、2来表示,没有棋子的地方,则用0来表示。假设这个棋盘是只有3颗棋子,2颗白棋子,1颗黑棋子,则该棋盘抽象出来,就是一个稀疏矩阵,其中非0元素只有3个,分别是1,2,2。现在,不想下棋了,那么要保存这个棋盘,也就是保存这个稀疏矩阵。

图解思路:


棋盘上的状态如图:

20190829092602266.png

我们从图所得到的信息:棋盘矩阵是11 * 11的,有3颗棋子


黑子所在的位置是矩阵的第3行第3列,值是1


白子所在的位置是矩阵的第6行第2列、第4行第5列,值都为2


转化成数组的存储,就是:


黑子所在的位置是矩阵的第2行第2列,值是1


白子所在的位置是矩阵的第5行第1列、第3行第4列,值都为2(因为数组的下标是从0开始的)


那么,我们可以将上面的信息抽象成一个新的二维数组:

20190829095016131.png


代码实现


package Array;
public class Demo03 {
    public static void main(String[] args) {
        //1.创建一个二维数组 11*11   0:没有棋子,  1:黑棋,     2:白棋
        int [][] array1 = new int[11][11];
        array1[1][2] = 1;
        array1[2][3] = 2;
        //输出原始的数组
        System.out.println("输出原始数组");
        for (int[] ints:array1) {
            for (int anint :ints) {
                System.out.print(anint+" ");
            }
            System.out.println();
        }
        //转换为稀疏数组保存
        //获取有效值的个数
        int sum = 0;
        for (int i = 0; i <11; i++) {
            for (int j = 0; j <11 ; j++) {
                if (array1[i][j]!=0)
                sum++;
            }
        }
        System.out.println("有效值的个数:"+sum);
        //创建一个稀疏矩阵的数组
        int[][] array2 = new int[sum+1][3];
        array2[0][0] = 11;
        array2[0][1] = 11;
        array2[0][2] = sum;
        //遍历二维数组,将非零的值,存在稀疏数组中
        int count=0;
        for (int i = 1; i < array1.length; i++) {
            for (int j = 0; j < array1[i].length; j++) {
                if (array1[i][j]!=0){
                    count++;
                    array2[count][0] = i;
                    array2[count][1] = j;
                    array2[count][2] = array1[i][j];
                }
            }
        }
        //输出稀疏数组
        System.out.println("输出稀疏数组");
        for (int i = 0; i < array2.length; i++) {
            System.out.println(array2[i][0]+"\t"
            +array2[i][1]+"\t"
            +array2[i][2]+"\t");
        }
        System.out.println("=======================");
        //将稀疏数组还原
        int[][] array3 = new int[array2[0][0]][array2[0][1]];
        //给其中的元素还原值
        for (int i = 1; i < array2.length; i++) {
            array3[array2[i][0]][array2[i][1]] = array2[i][2];
        }
        //打印
        for (int[] ints:array3) {
            for (int anint:ints) {
                System.out.print(anint+" ");
            }
            System.out.println();
        }
    }
}


相关文章
|
存储 算法 Java
稀疏矩阵的压缩与还原(Java实现)
稀疏矩阵的压缩与还原(Java实现)
206 0
稀疏矩阵的压缩与还原(Java实现)
Java里的稀疏矩阵Sparse Array
Java里的稀疏矩阵Sparse Array
Java里的稀疏矩阵Sparse Array
|
存储 Java C语言
《矩阵》——稀疏矩阵(Java)
转载请注明出处: 转载自  Thinkgamer的CSDN博客:blog.csdn.net/gamer_gyt 1:稀疏矩阵的背景 2:什么是稀疏矩阵? 3:为什么要对稀疏矩阵进行压缩存储以及压缩存储的方式? 4:稀疏矩阵的相关运算 一:背景         第一此介绍稀...
2487 0
|
8天前
|
监控 安全 Java
在 Java 中使用线程池监控以及动态调整线程池时需要注意什么?
【10月更文挑战第22天】在进行线程池的监控和动态调整时,要综合考虑多方面的因素,谨慎操作,以确保线程池能够高效、稳定地运行,满足业务的需求。
79 38
|
5天前
|
安全 Java
java 中 i++ 到底是否线程安全?
本文通过实例探讨了 `i++` 在多线程环境下的线程安全性问题。首先,使用 100 个线程分别执行 10000 次 `i++` 操作,发现最终结果小于预期的 1000000,证明 `i++` 是线程不安全的。接着,介绍了两种解决方法:使用 `synchronized` 关键字加锁和使用 `AtomicInteger` 类。其中,`AtomicInteger` 通过 `CAS` 操作实现了高效的线程安全。最后,通过分析字节码和源码,解释了 `i++` 为何线程不安全以及 `AtomicInteger` 如何保证线程安全。
java 中 i++ 到底是否线程安全?
|
9天前
|
Java 调度
[Java]线程生命周期与线程通信
本文详细探讨了线程生命周期与线程通信。文章首先分析了线程的五个基本状态及其转换过程,结合JDK1.8版本的特点进行了深入讲解。接着,通过多个实例介绍了线程通信的几种实现方式,包括使用`volatile`关键字、`Object`类的`wait()`和`notify()`方法、`CountDownLatch`、`ReentrantLock`结合`Condition`以及`LockSupport`等工具。全文旨在帮助读者理解线程管理的核心概念和技术细节。
25 1
[Java]线程生命周期与线程通信
|
7天前
|
安全 Java
在 Java 中使用实现 Runnable 接口的方式创建线程
【10月更文挑战第22天】通过以上内容的介绍,相信你已经对在 Java 中如何使用实现 Runnable 接口的方式创建线程有了更深入的了解。在实际应用中,需要根据具体的需求和场景,合理选择线程创建方式,并注意线程安全、同步、通信等相关问题,以确保程序的正确性和稳定性。
|
1天前
|
安全 Java 调度
Java中的多线程编程入门
【10月更文挑战第29天】在Java的世界中,多线程就像是一场精心编排的交响乐。每个线程都是乐团中的一个乐手,他们各自演奏着自己的部分,却又和谐地共同完成整场演出。本文将带你走进Java多线程的世界,让你从零基础到能够编写基本的多线程程序。
8 1
|
5天前
|
缓存 Java 调度
Java中的多线程编程:从基础到实践
【10月更文挑战第24天】 本文旨在为读者提供一个关于Java多线程编程的全面指南。我们将从多线程的基本概念开始,逐步深入到Java中实现多线程的方法,包括继承Thread类、实现Runnable接口以及使用Executor框架。此外,我们还将探讨多线程编程中的常见问题和最佳实践,帮助读者在实际项目中更好地应用多线程技术。
12 3