Clever use of arrays in PHP to reduce program time complexity

Time complexity is the main factor used by developers to measure the merits of application algorithms. 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 times the basic operations in the algorithm are repeated is a function f(n) of the problem size n, that is to say, as the problem As the 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 power, but also involves the interaction time of third-party tools, such as the link time to the database and the access time to the data. time. 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.

Let’s first look at an example. Assume that the development language of the Web program is PHP, and the DB2 database is used in the background. PHP implements access to the database through the PEAR::DB data abstraction layer.

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. It is necessary to display on the Web page that the math score of this test exceeds 90 points. The names and classes of classmates.

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

Name Description

SID Student number

COURSE Subject

SCORE Score

…

Based on personal programming Depending on your habits, there are usually two ways to solve this problem (the operation of accessing the database is expressed in PEAR::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:

$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 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 the student number that meets the conditions from the SCORES table, and then find the student's name from the STUDENTS table and class code, and finally get the name of the class in the CLASSES table. The PHP algorithm is described as follows:

$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 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 students' 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 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 be familiar with it a feeling of. 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 X*Y*Z records will be formed in the database, and then the number of records that meet the conditions is searched in this matrix, and finally the STUNAME information and CLASSNAME of the record are obtained. In this way, the increase in data in any table will cause the number of records in the matrix table to increase exponentially

The main idea: When the required data is relatively simple and the amount of data is stable, use PHP array (Array) The subscript (Index) can be a character string (String), which cleverly stores 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] Get the corresponding relationship between CLASSID and CLASSNAME from the CLASSES table and store it in the ClassArray one-dimensional array. Get the corresponding relationship between SID and STUNAME and CLASSID from the STUDENTS table and store it in the StuArray two-dimensional array. Then find out 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:

$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( $stustr);
while( $stu=$studata ->fetchRow(DB_FETCHMODE_ASSOC) ){
//Generate StuArray array, the subscript Index is 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 );
//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:

$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 students’ names, 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
​​

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.