PHP USES arrays to reduce the time complexity of a program

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.

< img Alt = "" border = 0 height = 4 SRC =" http://www.ibm.com/i/c.gif "width =" 100% ">

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.

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] Make a joint query on the three tables of STUDENTS, CLASSES and SCORES to obtain the information of STUDENTS and CLASSES that meet the requirements at one time. The description of PHP algorithm is as follows:

$querystr = "select distinct s.sitame as STUNAME, c.cacassname as CLASSNAME ". "From STUDENTS as S,CLASSES as C,SCORES as R ". "Where s.sidney = r.sidney and s.lassid = c.lassid and r.sideline ='Math'" "And R.S CORE> = 90 "; $result = $db2handle - > The 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 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:

$scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE> = 90 "; $scoredata = $db2handle - > The query ($scorestr); // get the student id 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 - > The query ($studentstr); $stu = $studata - > FetchRow (DB_FETCHMODE_ASSOC); // show the name of the student 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 - > The query ($classstr); $class = $classdata - > FetchRow (DB_FETCHMODE_ASSOC); // shows the classes 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.

< img Alt = "" border = 0 height = 4 SRC =" http://www.ibm.com/i/c.gif "width =" 100% ">

Main ideas: 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] Get the correspondence between CLASSID and CLASSNAME from the CLASSES table to store in the ClassArray one-dimensional array, and SID and STUNAME and CLASSID from the STUDENTS table to store 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:

$ClassArray = Array (); $StuArray = Array (); $classstr = "select CLASSID,CLASSNAME from CLASSES"; $classdata = $db2handle - > The query ($classstr); While ($class = $classdata - > FetchRow (DB_FETCHMODE_ASSOC)) { // generates a ClassArray array with Index named CLASSID and the corresponding value CLASSNAME [$$ClassArray class [' every ']] = $class [' CLASSNAME ']; } / / end while $ClassArray $stustr = "select the SID, STUNAME, every from STUDENTS"; $studata = $db2handle - > The query ($stustr); While ($stu = $studata - > FetchRow (DB_FETCHMODE_ASSOC)) { // generates the StuArray array with the Index named after SID and the corresponding values STUNAME and CLASSID [$$StuArray stu [' SID ']] [' STUNAME] = $stu [' STUNAME]; [$$StuArray stu [' SID ']] [' every '] = $stu [' every ']. } / / end while $StuArray $scorestr = "select distinct SID from SCORES where COURSE='Math' and SCORE> = 90 "; $scoredata = $db2handle - > The query ($scorestr); // get the student id that meets the requirements from the database While ($score = $scoredata - > FetchRow (DB_FETCHMODE_ASSOC)) { // reads the student's student number, reads the student's name from StuArray, and reads the class name from ClassArray Echo "StudentName =". $StuArray [$score [' SID ']] [' STUNAME]. "\ t"; Echo "CLASSNAME =". $ClassArray [$StuArray [$score [' SID ']] [' every ']]. "\ 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] Get the correspondence between CLASSID and CLASSNAME from the CLASSES table and store 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:

$ClassArray = Array (); $classstr = "select CLASSID,CLASSNAME from CLASSES"; $classdata = $db2handle - > The query ($classstr); While ($class = $classdata - > FetchRow (DB_FETCHMODE_ASSOC)) { // generates a ClassArray array with Index named CLASSID and the corresponding value CLASSNAME [$$ClassArray class [' every ']] = $class [' CLASSNAME ']; } / / end while $ClassArray $stustr = "select STUNAME,CLASSID from STUDENTS where SID in ". "(select distinct SID from SCORES where COURSE='M' and SCORES > = 90) "; $studata = $db2handle - > The query ($stustr); // get the name and class number of the student who meets the criteria from the database While ($stu = $studata - > FetchRow (DB_FETCHMODE_ASSOC)) { // reads the student's name and the class name from the ClassArray Echo "StudentName =". $stu [' STUNAME]. "\ t"; Echo "CLASSNAME =". $ClassArray [$stu [' every ']]. "\ n"; }//end while for getting each student's info.done < img Alt = "" border = 0 height = 4 SRC =" http://www.ibm.com/i/c.gif "width =" 100% ">