Bypassing cycles through hard links

Hard link

A hard link is a variable that is a synonym for another variable to which it refers. To create a hard link, you must write "&" in front of the variable.

Example of a hard link ad:

$a = 1 ; //   $b = &$a ; // $b   $a echo $b ; // 1 

By sabzh

Many of us faced such a task: it is necessary to obtain the object we are looking for, from an array of objects of the same type. Of course, this is a trivial task, and it can be easily solved with the help of a regular loop, but suppose that our array consists of a fairly large number of elements. In this case, the cycle has a detrimental effect on performance in general. In addition, if this task is carried out repeatedly, it will further aggravate the situation.



To solve this problem, an array-bundle containing hard links, each of which is under its own unique key obtained by hashing, is perfect.

')

It is clear what this decision is:

Script for testing

We skip and look at the code as a whole, if you don’t want to read the code building process

1. Build a test array of objects.

 class Main { public $List = Array(); //     public $Links = Array(); //      public $Count = NULL ; //    public function Fill() //   { for( $i=0; $i < $this->Count; $i++ ) { $Obj = &$this->List[]; //    $Obj = new Obj($i); $Key = md5($i); $this->Links[$Key] = &$Obj; //     } } } class Obj //   { public $Id = NULL; public function __construct( $Id ) { $this->Id = $Id; } } $Main = new Main(); $Main->Count = 1000; //  ,      $Main->Fill(); /*   , print_r( $Main->List ): Array ( [0] => Obj Object ( [Id] => 0 ) [1] => Obj Object ( [Id] => 1 ) [2] => Obj Object ( [Id] => 2 ) ... ) */ 

1. We determine the search function of the element by ID (cycle, and through links).

 class Main { ... public function Search_Cycle( $Id ) { $Limit = count( $this->List ); for( $i=0; $i < $Limit; $i++ ) if( $this->List[$i]->Id == $Id ) return $this->List[$i]; return NULL; } public function Search_Link( $Id ) { $Key = md5($i); if( isset( $this->Links[$Key] ) == TRUE ) return $this->Links[$Key]; return NULL; } ... } 

It is worth noting that the element search algorithm is built on the generated keys, and therefore does not depend on the size of the array in which the element is searched. From this it follows that in the process of testing, this algorithm will show identical results at all stages.

3. We will add the code for the test

 ... $Count = 100 ; //        //     10  for( $t=0; $t < $Main->Count; $t++ ) { echo 'Test with ID: ' . $t . ' - started.'; //   ,      $Start = microtime( TRUE ); for( $i=0; $i < $Count; $i++ ) $Main->Search_Cycle( $t ); $Time = round( microtime( TRUE ) - $Start , 4 ); echo '<br />Search_Cycle() time: ' . $Time; //   ,      $Start = microtime( TRUE ); for( $i=0; $i < $Count; $i++ ) $Main->Search_Link( $t ); $Time = round( microtime( TRUE ) - $Start , 4 ); echo '<br /> Search_Link() time: ' . $Time; echo '<br /><br />'; } 

This code searches each element of the source array ( $ Count times) using these two functions, counts the search time for each, and displays the result.

Code in general

As a result, you should get this code:

 class Main { public $List = Array(); //     public $Links = Array(); //      public $Count = NULL ; //    public function Fill() //   { for( $i=0; $i < $this->Count; $i++ ) { $Obj = &$this->List[]; //    $Obj = new Obj($i); $Key = md5($i); $this->Links[$Key] = &$Obj; //     } } public function Search_Cycle( $Id ) { $Limit = count( $this->List ); for( $i=0; $i < $Limit; $i++ ) if( $this->List[$i]->Id == $Id ) return $this->List[$i]; return NULL; } public function Search_Link( $Id ) { $Key = md5($Id); if( isset( $this->Links[$Key] ) == TRUE ) return $this->Links[$Key]; return NULL; } } class Obj //   { public $Id = NULL; public function __construct( $Id ) { $this->Id = $Id; } } $Main = new Main(); $Main->Count = 1000; //  ,      $Main->Fill(); /*   , print_r( $Main->List ): Array ( [0] => Obj Object ( [Id] => 0 ) [1] => Obj Object ( [Id] => 1 ) [2] => Obj Object ( [Id] => 2 ) ... ) */ $Count = 100 ; //        //     10  for( $t=0; $t < $Main->Count; $t++ ) { echo 'Test with ID: ' . $t . ' - started.'; //   ,      $Start = microtime( TRUE ); for( $i=0; $i < $Count; $i++ ) $Main->Search_Cycle( $t ); $Time = round( microtime( TRUE ) - $Start , 4 ); echo '<br />Search_Cycle() time: ' . $Time; //   ,      $Start = microtime( TRUE ); for( $i=0; $i < $Count; $i++ ) $Main->Search_Link( $t ); $Time = round( microtime( TRUE ) - $Start , 4 ); echo '<br /> Search_Link() time: ' . $Time; echo '<br /><br />'; } 

For testing, we just need to run the script.

Testing

Running the script, we obtained results about the time of the search element. Since the search for each element was performed 100 times in a row (to get real numbers), any value that you see below is divided by one hundred, to get the most realistic picture.

Results:

Vertically on the charts - search speed. Horizontal - ID of the desired object.



The graph is unfortunately an image, so you can not pull-poke.



Search function Search_Cycle () - using the loop.





Search function Search_Link_Cycle () - with the help of hard links.





The key point in the study of these graphs is that a search with a cycle works faster than links, with the number of elements less than 6 (0.002 sec. Against 0.004 sec.).

Total

Obviously, working with hard links is much faster, because they do not depend on the size of the array, and are referenced directly to the object. However, they lose the search based on the cycle, with a small array size (if you do not take into account that this difference is simply insignificant).



What to use - everyone has the right to choose himself, but using this method when searching in large arrays - you will significantly win performance and instantly find the object, regardless of the size of the array.