PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(五)——数组的压缩与转置

(原创内容,转载请注明来源,谢谢)

1、数组可以看作是多个线性表组成的数据结构,二维数组可以有两种存储方式:一种是以行为主序,另一种是以列为主序。

2、当数组存在特殊情况时,为了节省存储空间,可以进行压缩存储,把相同值并有规律分布的元素只分配一个存储空间,对于零元素不进行存储。

有两种情况可以进行压缩存储——特殊矩阵与稀疏矩阵。

3、当数组为特殊的矩阵,例如数组为n阶对称矩阵(满足aij=aji)。对于该类型矩阵,可以只存储一半的数值加上对角线的内容,一共需要分配n*(n+1)/2的存储空间。同时,上(下)三角矩阵也可以用此方式进行存储。(三角矩阵为一半有值,另一半值为0的矩阵)

存储N阶对称矩阵的方式,即以对称对角线为分界,仅取其中一半的内容以及对角线进行存储。

PHP压缩与还原n阶对称矩阵的源码如下:

         <?php
//存储n阶对称矩阵
function symmetricMatrixSave($n,$arr){
         $arrResult= array();
         $k= 0;//结果数组的下标
         for($i=0;$i<$n;$i++){
                   for($j=0;$j<=$i; $j++){
                            $arrResult[$k++]= $arr[$i][$j];
                   }
         }
         return$arrResult;
}
//还原n阶对称矩阵
function symmetricMatrixRe($arr){
         $rank= $arr[0];
         $arrResult= array();
         $row= 0;
         $col= 0;
         for($k=0;$k<count($arr); $k++){
                   //根据取出的值还原半边
                   $arrResult[$row][$col]= $arr[$k];
                   //根据对称性还原另一半
                   $arrResult[$col][$row]= $arrResult[$row][$col];
                   $col++;
                   //根据存储规则,只存一半的值,因此col不会大于row
                   if($col> $row){
                            $col= 0;
                            $row++;
                   }                
         }
         return$arrResult;
}
//调用n阶矩阵的存储还原
$arr = array(
         0=> array(0, 1, 2, 3),
         1=> array(1, 2, 3, 4),
         2=> array(2, 3, 4, 5),
         3=> array(3, 4, 5, 6)
);
print_r($arr);
//打印原数组Array ( [0]=> Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 ) [1] => Array( [0] => 1 [1] => 2 [2] => 3 [3] => 4 ) [2] => Array ( [0] =>2 [1] => 3 [2] => 4 [3] => 5 ) [3] => Array ( [0] => 3 [1] =>4 [2] => 5 [3] => 6 ) )

echo '<br />';
$arrResult = symmetricMatrixSave(4, $arr);
print_r($arrResult);
//压缩后的结果Array ( [0]=> 0 [1] => 1 [2] => 2 [3] => 2 [4] => 3 [5] => 4 [6] => 3[7] => 4 [8] => 5 [9] => 6 )
echo '<br />';
$arrRe = symmetricMatrixRe($arrResult);
print_r($arrRe);
//还原后的结果,与压缩前相同Array ([0] => Array ( [0] => 0 [1] => 1 [2] => 2 [3] => 3 ) [1] =>Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 4 ) [2] => Array ( [0]=> 2 [1] => 3 [2] => 4 [3] => 5 ) [3] => Array ( [0] => 3 [1]=> 4 [2] => 5 [3] => 6 ) )

4、当矩阵为稀疏矩阵,即在m*n的矩阵中,有t个不为0的元素,且满足t/(m*n)<=0.5。稀疏矩阵通常用三元数组进行存储,(i,j,value)分别表示不为零的元素的行、列以及值。

除了上述的三元数组的压缩方式,稀疏矩阵还有两种压缩方式。分别是行逻辑链接的顺序表、十字链表。

4.1 三元组顺序表

三元组顺序表以行为主序,以列为次序,从小到大进行排列。例如:[(0,1,30),(0,3,50),(1,2,18),(3,5,20)],表示该稀疏矩阵共有四个非零元素,分别在(0,1)、(0,3)、(1,2)、(3,5)四个位置,值分别是30、50、18、20。

该方法存储的表,要进行转置操作非常便利。转置需要进行三步操作,分别是:行列的值进行转换、i和j进行转换、重新从小到大排列i和j。因此,转置的重点在于最后一步——排序。

对于排序,可以通过从0开始扫描原数组的列,并将结果相应放入新数组的行。也可以采用下述的快速转置法。

快速转置数组算法:

假设原矩阵为M,新矩阵为T,引入两个新的数组,数组num[col]为第col列非零元的个数,cpot[col]为第col列第一个非零元在新矩阵T生成的三元组顺序表的位置。在转置前,先通过原矩阵M获取这两个数组,用于快速转换的计算。

PHP快速转置稀疏矩阵的源码如下:

<?php
//快速转置稀疏矩阵
//根据原标准三元数组获取每一列非零元个数及第一个非零元的位置
/* 输入要求
array(
         0=>array(0,1,33),
         1=>array(0,5,67),
         2=>array(1,2,66),
         3=>array(3,4,55)
)*/
function getAuxiliaryArray($arr){
         $num= array();//每一列非零元个数
         foreach($arras $key => $val){
                   $num[next($val)]++;//next($val)获取列值
         }
         ksort($num);//根据键对数组升序排列
         $row_position= 0;
         $cpot= array();
         foreach($numas $key => $val){
                   $cpot[$key]= $row_position;
                   $row_position= $row_position + $val;
         }
         returnarray('num'=>$num, 'cpot'=>$cpot);
}
//转置方法
function getReverse($arr, $num, $cpot){
         $arrResult= array();
         foreach($arras $key => $val){
                   $row= current($val);
                   $col= next($val);
                   $val= next($val);
                   $arrResult[$cpot[$col]]= array($col, $row, $val);
                   $cpot[$col]++;//用于存放同一列下一个值的位置
         }
         return$arrResult;
}
$arrPrev = array(
         0=>array(0,1,33),
         1=>array(0,5,67),
         2=>array(1,2,66),
         3=>array(2,2,69),
         4=>array(3,4,55)
);
$arrTemp = getAuxiliaryArray($arrPrev);
$arrAfter = getReverse($arrPrev,$arrTemp['num'], $arrTemp['cpot']);
print_r($arrAfter);
//输出Array ( [0] =>Array ( [0] => 1 [1] => 0 [2] => 33 ) [1] => Array ( [0] => 2[1] => 1 [2] => 66 ) [2] => Array ( [0] => 2 [1] => 2 [2] =>69 ) [3] => Array ( [0] => 4 [1] => 3 [2] => 55 ) [4] => Array ([0] => 5 [1] => 0 [2] => 67 ))

——written by linhxx 2017.06.23

相关阅读:

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-06-23

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏King_3的技术专栏

leetcode-54-螺旋矩阵

给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。

714
来自专栏liulun

Nim教程【十三】

类型转换 Nim支持显示类型转换和隐式类型转换 使用casts操作符完成显示类型转换工作, 显示类型转换工作是编译期完成的工作,是位模式的 隐式类型转换也是编译...

1776
来自专栏数据结构与算法

约瑟夫环 队列+链表

设有n个人依次围成一圈,从第1个人开始报数,数到第m个人出列,然后从出列的下一个人开始报数,数到第m个人又出列,…,如此反复到所有的人全部出列为止。设n个人的编...

3367
来自专栏CDA数据分析师

Python程序员鲜为人知但你应该知道的16个问题

这篇文章主要介绍了Python程序员代码编写时应该避免的16个“坑”,也可以说成Python程序员代码编写时应该避免的16个问题,需要的朋友可以参考。 1. ...

1727
来自专栏Python小屋

详解Python列表推导式

列表推导式可以使用非常简洁的方式对列表或其他可迭代对象的元素进行遍历和过滤,快速生成满足特定需求的列表,代码具有非常强的可读性,是Python程序开发时应用最多...

2934
来自专栏数据小魔方

左手用R右手Python系列7——排序

排序可能是日常数据清洗过程中比较高频的应用了,今天这一篇给大家介绍R语言和Python中最为常见的排序函数应用。 R语言: sort order rank ar...

2524
来自专栏zaking's

用js来实现那些数据结构03(数组篇03-排序及多维数组)

  终于,这是有关于数组的最后一篇,下一篇会真真切切给大家带来数据结构在js中的实现方式。那么这篇文章还是得啰嗦一下数组的相关知识,因为数组真的太重要了!不要怀...

2925
来自专栏web前端教室

[先行者周日课程-0305] web前端组件 之 拖动窗口

学习笔记如下: 今天的内容,是拖动窗口。 js的引用数据类型,基本数据类型。 js它有5种基本数据类型: undefined , null, Boolean,...

1798
来自专栏闻道于事

算法笔记(二)数据结构

1030
来自专栏小白的技术客栈

Python函数基础

函数基础 简单地说,一个函数就是一组Python语句的组合,它们可以在程序中运行一次或多次运行。Python中的函数在其他语言中也叫做过程或子例程,那么这些被包...

3475

扫描关注云+社区