PHP cleverly USES arrays to reduce program time complexity
- 2020-03-31 20:18:01
- OfStack
About the author
Dandan wang is a software engineer at IBM China system and technology center. Since joining IBM in 2006, he has been engaged in Web system design and development. He has five years of experience in PHP application design and development.
Usually, when developers write programs, they usually translate the logic that has been designed or conceived directly into the programming language. It is a pleasure that the program compiles well. If the running time of the program is acceptable at this point, you will be immersed in the sense of accomplishment of writing code, often ignoring the optimization of the code in the process. Only when the speed of the program is affected do you go back and think about optimization. This article mainly introduces how to skillfully use arrays to reduce the time complexity caused by multi-layer loops in PHP programming. This method of optimizing your code, especially if your program needs to interact with the database multiple times, can have unexpected effects.
What is the time complexity of an algorithm
Time complexity is a major factor that developers use to evaluate the performance of an application's algorithms. Objectively speaking, the advantages and disadvantages of the algorithm are not only related to the time complexity, but also closely related to the space complexity. With the continuous improvement of device hardware configuration, the spatial complexity requirements of the algorithm for small and medium-sized applications have been relaxed. However, in today's Web2.0 era, the time complexity of applications is much higher.
What is the time complexity of an algorithm? In summary, it refers to selecting an original operation representing the algorithm from the algorithm, and taking the number of times the original operation is repeated as the time measure 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 execution times of the original operation caused by the control structure. To reduce the time complexity of the algorithm, it is relatively easy to reduce the number of original operations, is also the main method. The method described in this article is to reduce the number of times the original operation is executed by clever use of PHP array, so as to reduce the need of algorithm time complexity, to share with you.
The time measure of the algorithm is denoted as T(n)=O(f(n)), which indicates that the number of basic operations repeated in the algorithm is a function of problem size n, f(n), that is, with the increase of problem size n, the growth rate of algorithm execution time is the same as that of f(n). In most cases, the statement in the deepest loop is treated as the original operation to discuss the time complexity of the algorithm, because it is executed the same number of times as the statement containing it. In general, you only need to select one basic operation to discuss the time complexity of the algorithm for a problem. There are also times when multiple basic operations need to be considered at the same time.
In Web development, usually the execution time or response time of a function is related not only to the responsiveness and processing power of the server, but also to the interaction time of third-party tools, such as the time to link to the database and the time to access the data. Therefore, when selecting the original operation, it is necessary to comprehensively consider all aspects of the application, and take the operation that has the greatest impact on the execution time of the program 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 take a look at an example first. Suppose the development language of the Web program is PHP, the background USES DB2 database, and PHP accesses the database through PEAR::DB data abstraction layer.
The instance
There are STUDENTS table (see table 1), CLASSES table (see table 2) and SCORES table (see table 3) in the database. The names and CLASSES of STUDENTS whose math SCORES in this exam exceed 90 points should be displayed on the Web page.
Table 1. The STUDENTS Table
The column name
describe
SID
Student id
STUNAME
The name
GENDER
gender
The AGE
age
every
Class no.
...
Table 2. CLASSES Table
The column name
describe
every
Class no.
The CLASSNAME
The class name
...
Table 3. The SCORES Table
The column name
describe
SID
Student student id
COURSE
discipline
SCORE
results
...
Depending on your programming habits, there are two common approaches to this problem (access to the database is represented as PEAR::DB), see methods 1, 2.
[method 1] a joint query was made on the three tables of STUDENTS, CLASSES and SCORES to obtain the information of STUDENTS and CLASSES meeting the requirements at one time. The description of PHP algorithm is as follows:
Listing 1. Method 1
[method 2] find out the student number that meets the requirements from the SCORES table, then look up the student's name and class code from the STUDENTS table, and finally get the class name from the CLASSES table. The description of PHP algorithm is as follows:
Listing 2. Method 2
For such an algorithm description, I believe you will have a sense of deja vu. This is an algorithm that most programmers use extensively. Because has been used to thinking of the algorithm logic directly into the code, and often do not have the time and attention to consider the merits of the algorithm. Here we analyze the time complexity of these two algorithms.
Because the time it takes a Web server to read and display data is relatively small, typically in the order of 10ms, the time it takes to query and retrieve data from a DB2 database is in the order of 100ms, and increases with the amount of data being queried. Therefore, the operation of query database can be used as the original operation to measure the time complexity, and the data quantity in the STUDENTS table and SCORES table can be used as the problem size n(usually, the data quantity in the CLASSES table is small and relatively stable).
For method 1, the number of database accesses is constant 1 as the problem size n increases. Therefore, the time complexity is T(n)=O(1). For method 2, assuming that there are m records satisfying the conditions in the SCORES table, the number of execution of the original operation is m+1. In other words, as the data size n increases, the number of original operations increases linearly. So the time complexity is T(n)=O(n). As you can see, method 1 has a low time complexity.
So what's the problem with method 1? Mainly because method 1 will increase the database load, that is, the execution time of the original operation is more affected by the problem size n. Assume that the records of STUDENTS, CLASSES and SCORES are X, Y and Z, respectively. Then, when performing the joint query operation, a matrix with the number of records X*Y*Z will be formed in the database, and then the number of records that meet the criteria will be found in this matrix, and finally the STUNAME information and CLASSNAME of the records will be obtained. Thus, an increase in the data in any table results in a multiplication of the records in the matrix table.
Use arrays to optimize the algorithm
Main idea: in the case that the required data is relatively simple and the data volume is stable, the Index of the PHP Array can be used as a String to temporarily store the data in the Array. In this way, the required value can be obtained quickly by Index, so as to reduce the number of queries to the database and thus reduce the time complexity of the algorithm.
[method 3] gets the correspondence between CLASSID and CLASSNAME from the CLASSES table and stores it in the ClassArray one-dimensional array, and SID and STUNAME and CLASSID from the STUDENTS table and stores it in the StuArray two-dimensional array. Then, the student number meeting the requirements is found from the SCORES table, the student name and class number are read from the StuArray array, and the class name is read from the ClassArray. The description of PHP algorithm is as follows:
Listing 3. Method 3
The time complexity of the improved method is still T(n)=O(1). Compared to method 1, method 3 does not have to worry about doubling the cost of a database query due to an increase in the number of records in a table. Compared with method 2, the time complexity is reduced without affecting the algorithm space complexity. You can kill two birds with one stone.
Although this optimization method is easy to use, it is by no means universal. You need to consider the "degree" when using. Assuming that the STUDENTS table has a large amount of data, the system memory consumption will increase when generating StuArray, so the spatial complexity of the algorithm will be affected. 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 selected again. In the case that the STUDENTS table records are large and the CLASSES table records are small and stable, the algorithm can be optimized by combining nested query and array. Method 4 is given here for reference.
[method 4] gets the correspondence between CLASSID and CLASSNAME from the CLASSES table and stores it in a one-dimensional ClassArray. STUDENTS 'STUNAME and CLASSID can be obtained by querying the student number satisfying the requirements in the SCORES table as the querying condition of the STUDENTS table. The class name is then read from the ClassArray. The description of PHP algorithm is as follows:
Listing 4. Method 4
conclusion
Methods 3 and 4 refer to arrays as a trick, which cleverly reduces the time complexity of the algorithm. In practical applications, the algorithm logic is much more complex, and the optimization of the algorithm needs to consider many factors. It is important to note that the approach described in this article applies to more than just PHP applications. If an array in a programming language supports strings as subscripts, you might consider adopting the method proposed in this article: clever subscripts of arrays to reduce the time complexity of the algorithm. For programming languages that do not support strings as array subscripts, consider using a hash table to achieve the same effect.
Dandan wang is a software engineer at IBM China system and technology center. Since joining IBM in 2006, he has been engaged in Web system design and development. He has five years of experience in PHP application design and development.
Usually, when developers write programs, they usually translate the logic that has been designed or conceived directly into the programming language. It is a pleasure that the program compiles well. If the running time of the program is acceptable at this point, you will be immersed in the sense of accomplishment of writing code, often ignoring the optimization of the code in the process. Only when the speed of the program is affected do you go back and think about optimization. This article mainly introduces how to skillfully use arrays to reduce the time complexity caused by multi-layer loops in PHP programming. This method of optimizing your code, especially if your program needs to interact with the database multiple times, can have unexpected effects.
What is the time complexity of an algorithm
Time complexity is a major factor that developers use to evaluate the performance of an application's algorithms. Objectively speaking, the advantages and disadvantages of the algorithm are not only related to the time complexity, but also closely related to the space complexity. With the continuous improvement of device hardware configuration, the spatial complexity requirements of the algorithm for small and medium-sized applications have been relaxed. However, in today's Web2.0 era, the time complexity of applications is much higher.
What is the time complexity of an algorithm? In summary, it refers to selecting an original operation representing the algorithm from the algorithm, and taking the number of times the original operation is repeated as the time measure 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 execution times of the original operation caused by the control structure. To reduce the time complexity of the algorithm, it is relatively easy to reduce the number of original operations, is also the main method. The method described in this article is to reduce the number of times the original operation is executed by clever use of PHP array, so as to reduce the need of algorithm time complexity, to share with you.
The time measure of the algorithm is denoted as T(n)=O(f(n)), which indicates that the number of basic operations repeated in the algorithm is a function of problem size n, f(n), that is, with the increase of problem size n, the growth rate of algorithm execution time is the same as that of f(n). In most cases, the statement in the deepest loop is treated as the original operation to discuss the time complexity of the algorithm, because it is executed the same number of times as the statement containing it. In general, you only need to select one basic operation to discuss the time complexity of the algorithm for a problem. There are also times when multiple basic operations need to be considered at the same time.
In Web development, usually the execution time or response time of a function is related not only to the responsiveness and processing power of the server, but also to the interaction time of third-party tools, such as the time to link to the database and the time to access the data. Therefore, when selecting the original operation, it is necessary to comprehensively consider all aspects of the application, and take the operation that has the greatest impact on the execution time of the program 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 take a look at an example first. Suppose the development language of the Web program is PHP, the background USES DB2 database, and PHP accesses the database through PEAR::DB data abstraction layer.
The instance
There are STUDENTS table (see table 1), CLASSES table (see table 2) and SCORES table (see table 3) in the database. The names and CLASSES of STUDENTS whose math SCORES in this exam exceed 90 points should be displayed on the Web page.
Table 1. The STUDENTS Table
The column name
describe
SID
Student id
STUNAME
The name
GENDER
gender
The AGE
age
every
Class no.
...
Table 2. CLASSES Table
The column name
describe
every
Class no.
The CLASSNAME
The class name
...
Table 3. The SCORES Table
The column name
describe
SID
Student student id
COURSE
discipline
SCORE
results
...
Depending on your programming habits, there are two common approaches to this problem (access to the database is represented as PEAR::DB), see methods 1, 2.
[method 1] a joint query was made on the three tables of STUDENTS, CLASSES and SCORES to obtain the information of STUDENTS and CLASSES meeting the requirements at one time. The description of PHP algorithm is as follows:
Listing 1. Method 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 ); //Get the data from the database
while( $row=$result->fetchRow(DB_FETCHMODE_ASSOC) ){
//Read and display data
echo "StudentName=".$row['STUNAME']."t ClassName=".$row['CLASSNAME']."n";
}//Done
[method 2] find out the student number that meets the requirements from the SCORES table, then look up the student's name and class code from the STUDENTS table, and finally get the class name from the CLASSES table. The description of PHP algorithm is as follows:
Listing 2. Method 2
$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE>=90";
$scoredata = $db2handle->query( $scorestr );
//Obtain the student number that meets the requirements from the database
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//Read the student's student number and look up 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);
//Show the student's name
echo "StudentName=".$stu['STUNAME']."t ";
//Read the student's class number and look up the class name in the CLASSES table
$classstr = "select CLASSNAME from CLASSES where CLASSID='".$stu['CLASSID']."'";
$classdata = $db2handle->query( $classstr);
$class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC);
//Show the class of the students
echo "CLASSNAME=".$class['CLASSNAME']."n";
}//end while for getting each student's ID. Done
For such an algorithm description, I believe you will have a sense of deja vu. This is an algorithm that most programmers use extensively. Because has been used to thinking of the algorithm logic directly into the code, and often do not have the time and attention to consider the merits of the algorithm. Here we analyze the time complexity of these two algorithms.
Because the time it takes a Web server to read and display data is relatively small, typically in the order of 10ms, the time it takes to query and retrieve data from a DB2 database is in the order of 100ms, and increases with the amount of data being queried. Therefore, the operation of query database can be used as the original operation to measure the time complexity, and the data quantity in the STUDENTS table and SCORES table can be used as the problem size n(usually, the data quantity in the CLASSES table is small and relatively stable).
For method 1, the number of database accesses is constant 1 as the problem size n increases. Therefore, the time complexity is T(n)=O(1). For method 2, assuming that there are m records satisfying the conditions in the SCORES table, the number of execution of the original operation is m+1. In other words, as the data size n increases, the number of original operations increases linearly. So the time complexity is T(n)=O(n). As you can see, method 1 has a low time complexity.
So what's the problem with method 1? Mainly because method 1 will increase the database load, that is, the execution time of the original operation is more affected by the problem size n. Assume that the records of STUDENTS, CLASSES and SCORES are X, Y and Z, respectively. Then, when performing the joint query operation, a matrix with the number of records X*Y*Z will be formed in the database, and then the number of records that meet the criteria will be found in this matrix, and finally the STUNAME information and CLASSNAME of the records will be obtained. Thus, an increase in the data in any table results in a multiplication of the records in the matrix table.
Use arrays to optimize the algorithm
Main idea: in the case that the required data is relatively simple and the data volume is stable, the Index of the PHP Array can be used as a String to temporarily store the data in the Array. In this way, the required value can be obtained quickly by Index, so as to reduce the number of queries to the database and thus reduce the time complexity of the algorithm.
[method 3] gets the correspondence between CLASSID and CLASSNAME from the CLASSES table and stores it in the ClassArray one-dimensional array, and SID and STUNAME and CLASSID from the STUDENTS table and stores it in the StuArray two-dimensional array. Then, the student number meeting the requirements is found from the SCORES table, the student name and class number are read from the StuArray array, and the class name is read from the ClassArray. The description of PHP algorithm is as follows:
Listing 3. Method 3
$ClassArray = Array();
$StuArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generate the ClassArray array with the Index named CLASSID and the corresponding value 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) ){
//Generate the StuArray array with Index named after SID and the corresponding values are 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 );
//Obtain the student number that meets the requirements from the database
while( $score=$scoredata->fetchRow(DB_FETCHMODE_ASSOC) ){
//The student's student number is read, and the student's name is read from StuArray, and the class name is read 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 to method 1, method 3 does not have to worry about doubling the cost of a database query due to an increase in the number of records in a table. Compared with method 2, the time complexity is reduced without affecting the algorithm space complexity. You can kill two birds with one stone.
Although this optimization method is easy to use, it is by no means universal. You need to consider the "degree" when using. Assuming that the STUDENTS table has a large amount of data, the system memory consumption will increase when generating StuArray, so the spatial complexity of the algorithm will be affected. 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 selected again. In the case that the STUDENTS table records are large and the CLASSES table records are small and stable, the algorithm can be optimized by combining nested query and array. Method 4 is given here for reference.
[method 4] gets the correspondence between CLASSID and CLASSNAME from the CLASSES table and stores it in a one-dimensional ClassArray. STUDENTS 'STUNAME and CLASSID can be obtained by querying the student number satisfying the requirements in the SCORES table as the querying condition of the STUDENTS table. The class name is then read from the ClassArray. The description of PHP algorithm is as follows:
Listing 4. Method 4
$ClassArray = Array();
$classstr = "select CLASSID,CLASSNAME from CLASSES";
$classdata = $db2handle->query( $classstr);
while( $class=$classdata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generate the ClassArray array with the Index named CLASSID and the corresponding value 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 student name and class number that meet the criteria from the database
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//The student's name is read and the class name is read from the ClassArray
echo "StudentName=".$stu ['STUNAME']."t ";
echo "CLASSNAME=".$ClassArray[ $stu ['CLASSID'] ]."n";
}//end while for getting each student's Info. Done
conclusion
Methods 3 and 4 refer to arrays as a trick, which cleverly reduces the time complexity of the algorithm. In practical applications, the algorithm logic is much more complex, and the optimization of the algorithm needs to consider many factors. It is important to note that the approach described in this article applies to more than just PHP applications. If an array in a programming language supports strings as subscripts, you might consider adopting the method proposed in this article: clever subscripts of arrays to reduce the time complexity of the algorithm. For programming languages that do not support strings as array subscripts, consider using a hash table to achieve the same effect.