PHP cleverly uses arrays to reduce the time complexity of programs_PHP tutorial

About the author
Wang Dandan, a software engineer at IBM China System and Technology Center, has been engaged in Web system design and development since joining IBM in 2006, and has five years of experience in PHP application design and development.

Usually when developers write programs, they often translate the already designed or conceived computing logic directly into a programming language. It is very gratifying that the program can be successfully compiled and passed. If the running time of the program is still acceptable at this time, you will be immersed in the sense of accomplishment of writing code, and often ignore the optimization of the code in the process. Only when the running speed of the program is affected will we go back and consider optimization. This article mainly introduces how to use arrays skillfully to reduce the time complexity caused by multi-level loops in PHP programming. Especially when the program needs to interact with the database multiple times, using this method to optimize your code will bring unexpected results.
What is the time complexity of an algorithm?
Time complexity is the main factor used by developers to measure the quality of an application algorithm. Objectively speaking, the quality of an algorithm is not only related to time complexity, but also closely related to space complexity. With the continuous improvement of device hardware configurations, the space complexity requirements of algorithms have become much looser for small and medium-sized applications. However, in today's Web2.0 era, there are higher requirements for the time complexity of applications.
What is the time complexity of the algorithm? In summary, it refers to selecting an original operation from the algorithm that can represent the algorithm, and using the number of times the original operation is repeated as the time measurement of the algorithm. There are two factors that affect the time complexity: one is the execution time of the original operation, and the other is the number of executions of the original operation caused by the control structure. To reduce the time complexity of the algorithm, reducing the number of executions of the original operation is an easier and main method. The method described in this article is to reduce the number of executions of the original operation by cleverly using PHP arrays, thereby achieving the need to reduce the time complexity of the algorithm, and share it with everyone.
The time measurement of the algorithm is recorded as T(n)=O(f(n)), which means that the number of repeated executions of the basic operations in the algorithm is a function f(n) of the problem size n, that is to say, as As the problem size n increases, the growth rate of the algorithm execution time is the same as the growth rate of f(n). In most cases, we use the statement in the deepest loop as the original operation to discuss the time complexity of the algorithm, because the number of times it is executed is the same as the frequency of the statements containing it. In general, for a problem, you only need to choose a basic operation to discuss the time complexity of the algorithm. Sometimes multiple basic operations need to be considered simultaneously.
In web development, usually the execution time or response time of a function is not only related to the server's response capability and processing capabilities, but also involves the interaction time of third-party tools, such as the link time to the database and the storage of data. The time taken. Therefore, when selecting the original operation, it is necessary to comprehensively consider all aspects of the application, and use the operation that has the greatest impact on the program execution time as the original operation to measure the time complexity of the algorithm. In other words, programmers need to have a basic understanding of the execution time of important operations when writing code.





Time complexity analysis in common programs
Let’s look at an example first. Assume that the development language of the Web program is PHP, and the background uses DB2 database. PHP Access to the database is achieved through the PEAR::DB data abstraction layer.
Example
There are student table STUDENTS (see Table 1), class table CLASSES (see Table 2), and student performance table SCORES (see Table 3) in the database. The mathematics scores of this exam need to be displayed on the Web page. The names and classes of students who scored more than 90 points.
Table 1. STUDENTS Table
Column Name
Description
SID
Student Number
STUNAME
Name
GENDER
Gender
AGE
Age
CLASSID
Class number
…


Table 2. CLASSES Table
Column name
Description
CLASSID
Class number
CLASSNAME
Class Name
…


Table 3. SCORES Table
Column Name
Description
SID
Student ID
COURSE
Discipline
SCORE
Score
…




According to different personal programming habits, there are usually two ways to solve this problem (use PEAR to access the database ::DB), see methods 1 and 2.
[Method 1] Perform a joint query on the three tables STUDENTS, CLASSES, and SCORES to obtain student information and class information that meet the conditions at one time. The PHP algorithm is described as follows:

List 1. Method 1

Copy code The code is as follows:

$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 ); //From the database Get data
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//Read and display data
echo "StudentName=".$row['STUNAME']."t ClassName=".$row['CLASSNAME']."n";
}//Done

[Method 2] Find the student number that meets the conditions from the SCORES table, then find the student's name and class code from the STUDENTS table, and finally get the name of the class from the CLASSES table. The PHP algorithm is described as follows:

List 2. Method 2

Copy code The code is as follows:

$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//Get students who meet the conditions from the database Student ID
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//Read the student’s student ID and find the student’s name and class number in the STUDENTS table
$studentstr = "select STUNAME,CLASSID from STUDENTS where SID='".$score['SID']."'";
$studata =$db2handle->query( $studentstr);
$stu=$ studata->fetchRow(DB_FETCHMODE_ASSOC);
//Display the student’s name
echo "StudentName=".$stu['STUNAME']."t ";
//Read the student’s class number , and find the class name of the student in the CLASSES table
$classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
$classdata = $db2handle- >query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//Display the student’s class
echo "CLASSNAME=".$class['CLASSNAME']. "n";
}//end while for getting each student's ID. Done

For such an algorithm description, I believe everyone will feel familiar. This is also an algorithm widely used by most programmers. Because I have become accustomed to directly translating the algorithmic logic in my thinking into code, I often do not have the time and thought to consider the pros and cons of the algorithm. Here we analyze the time complexity of these two algorithms.
Because the time it takes for the Web server to read and display data is relatively small, generally on the order of 10ms, the time it takes to query and obtain data from the DB2 database will be on the order of 100ms, and will increase as the amount of query data increases. . Therefore, the operation of querying the database can be used as the original operation to measure the time complexity, and the data volume in the STUDENTS table and SCORES table is used as the problem size n (usually, the data volume of the CLASSES table is small and relatively stable).
For method 1, as the problem size n increases, the number of database accesses is a constant 1. Therefore, the time complexity is T(n)=O(1). For method 2, assuming that there are m records in the SCORES table that meet the conditions, the number of executions of the original operation is m+1. That is to say, as the data size n increases, the number of execution times of the original operation increases linearly. It can be seen that the time complexity is T(n)=O(n). It can be seen that the time complexity of method 1 is low.
So what’s the problem with method 1? The main reason is that method 1 will increase the database load, that is, the execution time of the original operation is greatly affected by the problem size n. Assume that the number of records in STUDENTS, CLASSES, and SCORES are X, Y, and Z respectively. Then when performing a joint query operation, a matrix with a record number of In this way, the increase in data in any table will cause the number of records in the matrix table to increase exponentially.


Use arrays to optimize algorithms
Main idea: When the required data is relatively simple and the amount of data is stable, the subscript (Index) of the PHP array (Array) can be The characteristics of string (String) cleverly store data temporarily into an array. In this way, the required value can be quickly obtained through the index, thereby reducing the number of queries to the database and thus reducing the time complexity of the algorithm.
[Method 3] Obtain the corresponding relationship between CLASSID and CLASSNAME from the CLASSES table and store it in the ClassArray one-dimensional array. Obtain the corresponding relationship between SID and STUNAME and CLASSID from the STUDENTS table and store it in the StuArray two-dimensional array. Then find the student ID number that meets the conditions from the SCORES table, read the student's name and class number from the StuArray array, and read the name of the class from the ClassArray. The PHP algorithm is described as follows:

List 3. Method 3

Copy code The code is as follows:

$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query ( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generate a ClassArray array, the subscript Index is named after CLASSID, and the corresponding value is CLASSNAME
$ClassArray [$class['CLASSID']] = $class['CLASSNAME'];
}//end while $ClassArray
$stustr="select SID,STUNAME,CLASSID from STUDENTS";
$studata = $db2handle->query( $stusstr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generate StuArray array, the subscript Index is named after SID, and the corresponding value For STUNAME and 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 );
//Get the student ID number that meets the conditions from the database
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
/ /Read the student's student number, read the student's name from StuArray, and read the class name from ClassArray
echo "StudentName=".$StuArray[ $score['SID'] ]['STUNAME'] ."t ";
echo "CLASSNAME=".$ClassArray[ $StuArray[ $score['SID'] ]['CLASSID'] ]."n";
}//end while for getting each student's ID. Done

The time complexity of the improved method is still T(n)=O(1). Compared with method 1, method 3 does not have to worry about the doubling of database query costs caused by the increase in records in a certain table. Compared with method 2, while the time complexity is reduced, it does not affect the algorithm space complexity. It can be said that it kills two birds with one stone.
Although this optimization method is simple and easy to use, it does not mean that it is omnipotent. You need to consider the issue of "degree" when using it. Assuming that the amount of data in the STUDENTS table is large, the system memory consumption will increase when generating StuArray, which will affect the space complexity of the algorithm. In addition, when the amount of data is large enough, the main factors affecting the execution time of the algorithm change, and the original operation needs to be reselected. For scenarios where the STUDENTS table has a large number of records and the CLASSES table has few and stable records, you can consider using a combination of nested queries and arrays to optimize the algorithm. Method 4 is given here for reference.
[Method 4] Obtain the corresponding relationship between CLASSID and CLASSNAME from the CLASSES table and store it in the ClassArray one-dimensional array. Query the student ID number that meets the conditions from the SCORES table, and use it as the query condition for querying the STUDENTS table to obtain the student's STUNAME and CLASSID. Then read the name of the class from the ClassArray. The PHP algorithm is described as follows:

Listing 4. Method 4

Copy the code The code is as follows:

$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class =$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generate a ClassArray array, the subscript Index is named after CLASSID, and the corresponding value is 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);
//Get the names and class numbers of students who meet the conditions from the database
while( $stu= $studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Read the student's name and read the class name from ClassArray
echo "StudentName=".$stu ['STUNAME']."t " ;
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."n";
}//end while for getting each student's Info. Done

Summary
Methods 3 and 4 use the small trick of arrays, which cleverly reduces the time complexity of the algorithm. In actual applications, the algorithm logic is much more complex, and the optimization of the algorithm requires comprehensive consideration of many factors. It should be mentioned that the method described in this article does not only apply to PHP applications. If the array of the programming language supports using strings as subscripts, you can consider using the method proposed in this article: cleverly use the subscripts of the array to reduce the time complexity of the algorithm. For programming languages ​​that do not support strings as array subscripts, you can consider using a hash table to achieve the same effect.

http://www.bkjia.com/PHPjc/321045.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/321045.htmlTechArticleAbout the author Wang Dandan, a software engineer at IBM China System and Technology Center, has been engaged in Web system design since joining IBM in 2006 And development work, five years of PHP application design and development...