Обход циклов посредством жестких ссылок

в 9:50, , рубрики: php, Алгоритмы, оптимизация, Песочница, Программирование, производительность, ссылки, метки: , , , ,
Жесткая ссылка

Жесткая ссылка — переменная, представляющая собой синоним другой переменной, на которую она ссылается. Чтобы создать жесткую ссылку, перед переменной необходимо написать "&".

Пример объявления жесткой ссылки:

$a = 1      ; // Некоторая переменная
$b = &$a    ; // $b ссылается на $a
echo $b     ; // 1
По сабжу

Многие из нас сталкивались с такой задачей: необходимо получить искомый нами объект, из массива однотипных объектов. Безусловно, эта тривиальная задача, и она легко решается при помощи обычного цикла, но, предположим, что наш массив состоит из довольно большого количества элементов. В этом случае цикл губильно сказывается на производительности в общем. Кроме того, если эта задача будет выполняться неоднократно, это еще больше усугубит ситуацию.

Для решения этой задачи прекрасно подойдет массив-связка, содержащий жесткие ссылки, каждая из которых находится под своим уникальным ключом, полученным путем хеширования.

Наглядно, что представляет из себя это решение:

Наглядно

Скрипт для тестирования

Пропускаем, и смотрим код в целом, если не хочется читать процесс сборки кода

1. Собираем тестовый массив объектов.

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. Определяем функции поиска элемента по ID (циклом, и через ссылки).

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;  
    }

...

}

Стоит заметить, что алгоритм поиска элемента построен на генерируемых ключах, и следовательно, не зависит от размера массива, в котором ведется поиск элемента. Из этого следует вывод, что в процессе тестирования, этот алгоритм покажет идентичные результаты на всех этапах.

3. Допишем код для проведения теста


...

$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 />';
    
}

Этот код выполняет поиск каждого элемента исходного массива ( $Count раз ), используя эти две функции, считает время поиска для каждой, и выводит результат.

Код в целом

В итоге должен получиться вот такой код:

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 />';
    
}

Для тестирования нам достаточно запустить скрипт.

Тестирование

Запустив скрипт, были получены результаты о времени поиска элемента. Так как поиск каждого элемента производился 100 раз подряд (для получения реальных цифр), любое значение которое вы увидите ниже — стоит разделить на сто, для получения максимально реальной картины.

Результаты:

По вертикали на графиках — скорость поиска. По горизонтали — ID искомого объекта.

График к сожалению изображением, поэтому подергать-потыркать нельзя.

Поиск функцией Search_Cycle() — при помощи цикла.
Обход циклов посредством жестких ссылок

Поиск функцией Search_Link_Cycle() — при помощи жестких ссылок.
Обход циклов посредством жестких ссылок

Ключевой момент при исследовании этих графиков — поиск при помощи цикла работает быстрее, нежели ссылки, при количестве элементов менее 6 ( 0.002 сек. против 0.004 сек. ).

Итог

Очевидно, что работать с жесткими ссылками намного быстрее, потому что они не зависят от размера массива, и ссылаются напрямую на объект. Тем не менее, они проигрывают поиску опираясь на цикл, при небольшом размере массива (если не учитывать, что эта разница просто ничтожна).

Что использовать — каждый вправе выбирать сам, но используя именно этот метод при поиске в больших массивах, — вы значительно выйграете в производительности, и мгновенно найдете объект, независимо от размера массива.

Автор: Homkas_r

Источник

Поделиться

* - обязательные к заполнению поля