香港高速VIP云机房火爆上线啦!无需备案,开通即用!配套《巅云自助建站系统3.0》将带给您飞一般的可视化拖拽建站体验,欢迎免费体验。

PHP 巧用数组降低程序的时间复杂度

一佰互联网站制作(www.yinxi.net) 发布日期 2019-05-01 19:06:14 浏览数: 27

关于作者
王丹丹 , IBM 中国系统与技术中心软件工程师,自从 2006 年加入 IBM,一直从事 Web 系统设计和开发工作,有五年 PHP 应用程序设计开发经验。

通常开发人员在写程序的时候,往往是把已经设计好或者构思好的运算逻辑,直接用编程语言翻译出来。程序能顺利编译通过,那是很令人高兴的事情。如果此时程序的运行时间还能接受,就会沉浸在写代码的成就感当中,常常在这个过程中忽略代码的优化。只有当程序运行速度受到影响时,才回过头去考虑优化的事情。本文主要是介绍在 PHP的编程中,如何巧用数组来降低因多层循环而引起的时间复杂度的问题。特别是当程序需要多次与数据库交互时,用此方法来优化你的代码,将会带给意想不到的效果。
什么是算法的时间复杂度
时间复杂度是开发人员用来衡量应用程序算法优劣的主要因素。客观地说,算法的优劣除了和时间复杂度有关,还与空间复杂度密切相关。而随着设备硬件配置的不断提升,对中小型应用程序来说,对算法的空间复杂度的要求也宽松了不少。不过,在当今 Web2.0 时代,对应用程序的时间复杂度却有了更高的要求。
什么是算法的时间复杂度呢?概要来说,是指从算法中选取一个能代表算法的原操作,以原操作重复执行的次数作为算法的时间量度。影响时间复杂度的因素有两个:一是原操作的执行时间,二是原操作因控制结构引起的执行次数。要把算法的时间复杂度降下来,降低原操作的执行次数是较为容易的方法,也是主要方法。本文所讲述的方法,是通过巧用 PHP 的数组,降低原操作的执行次数,从而达到降低算法时间复杂度的需求,和大家分享。
算法的时间量度记作 T(n)=O(f(n)),它表示算法中基本操作重复执行的次数是问题规模 n 的某个函数 f(n),也就是说随着问题规模 n的增大,算法执行时间的增长率和 f(n)的增长率相同。多数情况下,我们把最深层循环内的语句作为原操作来讨论算法的时间复杂度,因为它的执行次数和包含它的语句的频度相同。一般情况下,对一个问题只需选择一种基本操作来讨论算法的时间复杂度即可。有时也需要同时考虑多种基本操作。
在 Web开发中,通常一个功能的执行时间或响应时间,不仅仅跟服务器的响应能力、处理能力有关,还涉及第三方工具的交互时间,如对数据库的链接时间和对数据进行存取的时间。因而在选定原操作是,需要综合考虑应用程序各方面的因素,以最大影响程序执行时间的操作为原操作,来衡量算法的时间复杂度。也就是说,需要程序员在编写代码的时候,对重要操作的执行时间能有基本的认识。





常见程序中的时间复杂度分析
我们先看一个例子,假设 Web 程序的开发语言是 PHP,后台采用 DB2 数据库,PHP 通过 PEAR::DB 数据抽象层来实现对数据库的访问。
实例
数据库中有学生表 STUDENTS(见表 1),班级表 CLASSES(见表 2),学生成绩表 SCORES(见表 3),需要在 Web 页面中显示出本次考试数学成绩超过 90 分的同学姓名和所在班级。
表 1. STUDENTS Table
列名
描述
SID
学号
STUNAME
姓名
GENDER
性别
AGE
年龄
CLASSID
班级号



表 2. CLASSES Table
列名
描述
CLASSID
班级号
CLASSNAME
班级名



表 3. SCORES Table
列名
描述
SID
学生学号
COURSE
学科
SCORE
成绩





根据个人编程习惯的不同,要解决这个问题,通常有两种做法(访问数据库的操作用 PEAR::DB 的方式表示),参看方法 1、2。
[ 方法 1 ]对 STUDENTS, CLASSES, SCORES 三个表做联合查询,一次获取满足条件的学生信息和班级信息。PHP 算法描述如下:

清单 1. 方法 1
复制代码 代码如下:
$querystr = "select distinct S.STUNAME as STUNAME,C.CLASSNAME as CLASSNAME ".
"from STUDENTS as S,CLASSES as C,SCORES as R ".
"where S.SID=R.SID and S.CLASSID=C.CLASSID and R.COURSE="Math" ".
"and R.SCORE>=90";
$result = $db2handle->query( $querystr ); //从数据库中获取数据
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//读取并显示数据
echo "StudentName=".$row["STUNAME"]." ClassName=".$row["CLASSNAME"]." ";
}//Done

[ 方法 2 ]从 SCORES 表中找出满足条件的学生学号,然后从 STUDENTS 表中查找学生的姓名和班级编码,最后在 CLASSES 表中获取班级的名称。PHP 算法描述如下:

清单 2. 方法 2
复制代码 代码如下:
$scorestr = "select distinct SID from SCORES where COURSE="Math" and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//从数据库中获取满足条件的学生学号
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//读取学生的学号,并在STUDENTS表中查找学生的姓名和班级编号
$studentstr = "select STUNAME,CLASSID from STUDENTS where SID="".$score["SID"].""";
$studata =$db2handle->query( $studentstr);
$stu=$studata->fetchRow(DB_FETCHMODE_ASSOC);
//显示学生的姓名
echo "StudentName=".$stu["STUNAME"]." ";
//读去学生的班级编号,并在CLASSES表中查找该学生所在班级名称
$classstr = "select CLASSNAME from CLASSES where CLASSID="".$stu["CLASSID"].""";
$classdata = $db2handle->query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//显示学生的班级
echo "CLASSNAME=".$class["CLASSNAME"]." ";
}//end while for getting each student"s ID. Done

对于这样的算法描述,相信大家会有似曾相识的感觉。这也是大多程序员广泛使用的算法。因为已经习惯了将思维中的算法逻辑直接译成代码,而往往没有时间和心思来斟酌算法的优劣。这里来分析一下这两种算法的时间复杂度。
因Web 服务器读取并显示数据的时间相对较小,一般在 10ms 的数量级,而从 DB2 数据库里查询并获取数据的时间数量级会是 100ms的数量级,并且随查询数据量的增加而增加。所以查询数据库的操作可作为量度时间复杂度的原操作,以 STUDENTS 表和 SCORES表中的数据量作为问题规模 n( 通常情况下,CLASSES 表的数据量较小且相对稳定 )。
对于方法 1,随着问题规模n 的增大,访问数据库的次数为常量 1。因而,时间复杂度为 T(n)=O(1)。对于方法 2,假设 SCORES 表中满足条件的记录有 m个,则原操作的执行次数为 m+1。也就是说随着数据规模 n 的增大,原操作的执行次数成线性增长。可见时间复杂度为T(n)=O(n)。可见,方法 1 的时间复杂度低。
那么方法 1 的问题在哪里?主要因为方法 1会增大数据库负载,也就是原操作的执行时间受问题规模 n 的影响比较大。假设 STUDENTS,CLASSES,SCORES 的记录数分别为X, Y, Z。那么在执行联合查询操作时,在数据库中会形成一个记录数为 X*Y*Z的矩阵,然后在这个矩阵中查找满足条件的记录数,最后获取记录的 STUNAME 信息和CLASSNAME。这样,任何一个表中的数据增加,都会造成矩阵表中记录的成倍增加。


用数组来优化算法
主要思路 :在所需数据中存在相对简单且数据量稳定的情况下,利用 PHP 数组 (Array) 的下标 (Index) 可以为字符串 (String)的特点,巧妙的将数据临时存放到数组中。这样可以通过下标 (Index) 快速获取所需值,从而降低对数据库的查询次数,进而降低算法的时间复杂度。
[ 方法 3 ]从CLASSES 表中获取 CLASSID 和 CLASSNAME 的对应关系存放到 ClassArray 一维数组中,从 STUDENTS表中获取 SID 和 STUNAME 以及 CLASSID 的对应关系存放到 StuArray 二维数组中。之后从 SCORES表中找出满足条件的学生学号,从 StuArray 数组中读取学生的姓名和班级编号,从 ClassArray 中读取班级的名称。PHP算法描述如下:

清单 3. 方法 3
复制代码 代码如下:
$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生成ClassArray数组,下标Index以CLASSID命名,对应的值为CLASSNAME
$ClassArray[$class["CLASSID"]] = $class["CLASSNAME"];
}//end while $ClassArray
$stustr="select SID,STUNAME,CLASSID from STUDENTS";
$studata = $db2handle->query( $stustr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生成StuArray数组,下标Index以SID命名,对应的值为STUNAME和CLASSID
$StuArray[$stu ["SID"]]["STUNAME"] = $stu["STUNAME"];
$StuArray[$stu ["SID"]]["CLASSID"] = $stu["CLASSID"];
}//end while $StuArray
$scorestr = "select distinct SID from SCORES where COURSE="Math" and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//从数据库中获取满足条件的学生学号
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//读取学生的学号,并从StuArray中读取学生的姓名,从ClassArray中读取班级名称
echo "StudentName=".$StuArray[ $score["SID"] ]["STUNAME"]." ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score["SID"] ]["CLASSID"] ]." ";
}//end while for getting each student"s ID. Done

改进后方法的时间复杂度仍为 T(n)=O(1)。和方法 1 相比,方法 3 不必担心因某一个表中的记录增加而引起的数据库查询代价的成倍增加。和方法 2 相比,时间复杂度降低的同时,也没有影响算法空间复杂度。可谓一举两得。
虽然此优化方法简单易用,但并不是说它是万能的。使用时需要考虑“度”的问题。假设 STUDENTS 表的数据量很大,那么生成 StuArray的时候对系统内存的消耗就增加,这样算法的空间复杂度就会受到影响。另外,当数据量足够大时,影响算法执行时间的主要因素就发生了变化,需要重新选择原操作。针对 STUDENTS 表记录数大,CLASSES表记录少且稳定的情景,可以考虑用嵌套查询和数组相结合的方式,对算法进行优化。这里给出方法 4,以供参考。
[ 方法 4 ]从CLASSES 表中获取 CLASSID 和 CLASSNAME 的对应关系存放到 ClassArray 一维数组中。从 SCORES表中查询满足条件的学生学号,作为查询 STUDENTS 表的查询条件,获取学生的 STUNAME 和 CLASSID。之后从ClassArray 中读取班级的名称。PHP 算法描述如下:

清单 4. 方法 4


复制代码 代码如下:
$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//生成ClassArray数组,下标Index以CLASSID命名,对应的值为CLASSNAME
$ClassArray[$class["CLASSID"]] = $class["CLASSNAME"];
}//end while $ClassArray
$stustr = "select STUNAME,CLASSID from STUDENTS where SID in ".
"(select distinct SID from SCORES where COURSE="M" and SCORE>=90)";
$studata = $db2handle->query( $stustr);
//从数据库中获取满足条件的学生姓名和班级编号
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//读取学生的姓名,并从ClassArray中读取班级名称
echo "StudentName=".$stu ["STUNAME"]." ";
echo "CLASSNAME=".$ClassArray[ $stu ["CLASSID"] ]." ";
}//end while for getting each student"s Info. Done


总结
方法 3 和方法 4中引用了数组这个小技巧,巧妙地降低了算法的时间复杂度。在实际应用程序中,算法逻辑要复杂得多,对算法的优化需要综合考虑多方面的因素。需要提出的是,本文所述的方法不仅适用于 PHP应用程序。如果编程语言的数组支持以字符串作为下标,就可以考虑采用本文提出的方法:巧用数组的下标来降低算法的时间复杂度。对于不支持字符串做数组下标的编程语言,可以考虑使用建立哈希表来达到同样的效果。
一佰互联是全国知名建站品牌服务商,我们有九年网站建设、网站制作、网页设计、php开发和域名注册及虚拟主机服务经验,提供的自助建站服务更是全国有名。近年来还整合团队优势自主开发了可视化多用户”巅云建站系统“3.0平台版,拖拽排版网站制作设计,轻松实现pc站、手机微网站、小程序、APP一体化全网营销网站建设 ,已成功的为全国上百家网络公司提供自助建站平台搭建服务。

相关新闻more

03
05月
百度加V认证是什么意思?百度加V认证需要什么

前段时间在SEO论坛看到有人提到过这个问题,本来想早点写这篇文章,但一直抽不出时间,今天正好有空,下面SEO天空就跟大家分享下百度加V认证是... >>详情

03
05月
浅谈中小企业该如何更好的推广自己的网站

中小企业为了能够跟上信息化时代的趋势,必然会建设中小企业网站,而且如今建设中小企业网站的难度并不是很大,花个几千元就能够制作相当专业的企业... >>详情

26
04月
php实现购物车功能(以大苹果购物网为例)

首先是几个简单的登录页面<body><form action="chuli.php" method="post"> ... >>详情

01
04月
深圳文科园林股份有限公司关于公司 以集中竞价

简介:证券代码:002775 证券简称:文科园林 公告编号:2018-067深圳文科园林股份有限公司关于公司以集中竞价交易方式回购股份预案的... >>详情

营业执照. cdn加速服务 备案系统认证 网络安全协会 我们的支付方式AAA认证
上海 北京 深圳 广州 天津 杭州 南京 武汉 成都 沈阳 大连 长沙 济南 青岛 苏州 福州 无锡 哈尔滨 宁波 重庆 大庆 厦门 西安 长春 珠海 郑州 海口 昆明 太原 石家庄 温州 合肥 乌鲁木齐 南宁 南通 合肥 兰州 呼和浩特 贵阳 烟台 秦皇岛 包头 唐山 银川 汕头 连云港 威海 西宁 湛江 北海 万州 涪陵 长寿 黔江 永川 丰都 忠县 江津 南川 开县 云阳 万盛 梁平 垫江 巫山 城口 建站宝盒 免费建站 门户网站建设 微信网站 手机网站 门户网站制作

7x24小时服务电话:18581389571 传真:023-85725751 免费建站交流群:236412099 139947842(自助建站交流) E-Mail:post@yinxi.net 网站投诉:
重庆楚捷科技有限公司 一佰互联©版权所有 自助建站(www.yinxi.net,Inc.) 2001-2020 All Rights Reserved 本站程序受法律保护,网站法律顾问:ITLAW-庄毅雄律师
中华人民共和国信息产业部网站备案号:渝ICP备12000592号