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

Жесткая ссылка

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

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

$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 сек. ).

Итог

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

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

Comments 20

    +4
    Зачем понадобилось делать md5(id), если ключем в links может сразу быть id?
      0
      Обратил внимание на ваш комментарий, пересмотрел мой подход, и, да, очевидно что незачем было так делать, это лишняя нагрузка без смысла.
      +1
      Многие из нас сталкивались с такой задачей: необходимо получить искомый нами объект, из массива однотипных объектов. Безусловно, эта тривиальная задача, и она легко решается при помощи обычного цикла

      Задача надуманная. Покажите мне хотя бы один реальный пример, когда это действительно нужно (и при этом вы заранее знаете индексы объектов в массиве).
        0
        Массив данных берется из одной базы. Некие данные берутся из другой. К данным записей из первого массива нужно добавить некие данные из второго по некому соответствию полей и при этом сохранить порядок элементов в первом массиве.
          0
          Прекрасно, откуда вы возьмете массив ссылок для «массива данных из одной базы»? Посчитаете проходом по массиву? Ни что тогда мешает данные из второй базы сразу собрать в нужный хэш, а потом за один проход по массиву для каждого элемента выбрать данные из хэш-таблицы и привязать?

          (но вообще сочувствую людям, у которых в платформе нет операции join)
            0
            1. Да, массив ссылок я возьму проходом по массиву
            2. Помешает то, что данные из второго источника тоже массив, а значит его тоже надо пройти :) В любом случае получается пройти надо как первый массив, так и второй.
            3. В данном случае речь не о платформе, в которой нет join, он то как раз есть. Речь о ситуации когда различные данные берутся из различных источников (разные типы баз, разные сервера, и т.п.)
              0
              Да, массив ссылок я возьму проходом по массиву

              Значит, как минимум один проход по нему вам нужен все равно.

              Помешает то, что данные из второго источника тоже массив

              Почему это массив, а не хэш-таблица? Что мешает свернуть его в хэш-таблицу, раз уж вы не можете по каким-то причинам получить его хэш-таблицей?

              В любом случае получается пройти надо как первый массив, так и второй.

              Ну да, join иначе не реализуется. Вопрос в том, сколько раз вы будете проходить каждый массив. В решении с хэш-таблицами каждый массив проходится ровно один раз (т.е., не больше, чем в вашем решении), но при этом используются стандартные средства платформы.

              он то [join] как раз есть. Речь о ситуации когда различные данные берутся из различных источников (разные типы баз, разные сервера, и т.п.)

              Если бы у вас был join в платформе (а не на сервере БД), то вас бы не волновало, из каких источников берутся данные.
                0
                Почему это массив, а не хэш-таблица? Что мешает свернуть его в хэш-таблицу, раз уж вы не можете по каким-то причинам получить его хэш-таблицей?

                Потому что это например результать fetchall() из РСУБД, а он хоть как вернет массив.

                Вопрос в том, сколько раз вы будете проходить каждый массив.

                Аналогично. По одному разу на массив. Для свертки в хеш-таблицу эти проходы и нужны.

                Если бы у вас был join в платформе (а не на сервере БД), то вас бы не волновало, из каких источников берутся данные.

                Тогда я видимо не верно понимаю, что вы понимаете под словом «платформа».
                  0
                  Потому что это например результать fetchall() из РСУБД, а он хоть как вернет массив.

                  Ну и сверните его в хэш-таблицу.

                  Для свертки в хеш-таблицу эти проходы и нужны.

                  Ну и что вам мешает использовать стандартные хэш-таблицы, а не hardlinks? Зачем вам лишний уровень абстракции?

                  Тогда я видимо не верно понимаю, что вы понимаете под словом «платформа».

                  В вашем случае — PHP с используемыми вами библиотеками.
                    0
                    Ну и что вам мешает использовать стандартные хэш-таблицы, а не hardlinks? Зачем вам лишний уровень абстракции?

                    Мне ничего не мешает, собственно так и делаю, хоть это и не слишком ресурсо-оптимально.

                    В вашем случае — PHP с используемыми вами библиотеками.

                    Спасибо, но я пишу на пихтоне :) Я лишь привел пример, когда может понадобиться и массив и хеш-таблица.

                      0
                      Мне ничего не мешает, собственно так и делаю, хоть это и не слишком ресурсо-оптимально.

                      Какой способ, по-вашему, более оптимален?

                      Я лишь привел пример, когда может понадобиться и массив и хеш-таблица.

                      Вопрос был не о том, когда может понадобиться хеш-таблица, вопрос был о том, зачем использовать «жесткие ссылки» (хотя в доках это называется просто reference).
                        0
                        Какой способ, по-вашему, более оптимален?

                        Преобразование массива в хеш-таблицу на мой взгляд гораздо более читаемый, удобный и простой в реализации вариант. Им и пользуюсь. Однако при больших объемах данных момент преобразования массива элементов в хеш-таблицу ресурсо-затратный. Впрочем, этот фактор редко когда принимается в рассчет, если это не олимпиадная задача или программирование микроконтроллеров.

                        Вопрос был не о том, когда может понадобиться хеш-таблица, вопрос был о том, зачем использовать «жесткие ссылки» (хотя в доках это называется просто reference).

                        Хм… возможно тогда между нами вышло недопонимие в чем был вопрос, ибо я понял именно как первый вариант :)
                          0
                          Однако при больших объемах данных момент преобразования массива элементов в хеш-таблицу ресурсо-затратный.

                          Повторяю вопрос еще раз: какой способ более оптимален?
          0
          В данном случае индекс — образец для лучшего понимания. Я же использую поиск по системным именам.

          К примеру есть массив:

          Array
          (
          [0] => PAGE Object
          (
          [Status:PAGE:private] => 1
          [Id] => 1
          [SystemName] => root
          )

          [1] => PAGE Object
          (
          [Status:PAGE:private] => 1
          [Id] => 3
          [SystemName] => root_login
          )

          [2] => PAGE Object
          (
          [Status:PAGE:private] => 1
          [Id] => 4
          [SystemName] => root_admin
          )



          Так как этот массив собирается используя данные из базы, в котором ID страниц увеличивается по инкрименту, то ID неизвестен, и поиск ведется по уникальному системному имени. В этом случае его будет необходимо искать перебором массива, этим метода, или альтернативным методом.

          Это практический пример.

          (и при этом вы заранее знаете индексы объектов в массиве).
          В данном примере это не так, и тем самым задача усложняется. Этот метод решает проблему, как один из возможных быстрых вариантов решения.
            0
            В этом случае его будет необходимо искать перебором массива, этим метода, или альтернативным методом

            Так как вы будете его искать «этим методом»? Покажите конкретный код.
          0
          $Key = $SystemName;
          if( isset( self::$LINKS[$Key] ) == TRUE ) return self::$LINKS[$Key];

          К примеру, так. Об этом и идет речь в этом посте.
            +2
            if( isset( self::$LINKS[$Key] ) == TRUE ) return self::$LINKS[$Key];
            

            $LINKS заполняется святым духом?
              0
              if(isset( self::$LINKS[$Key] ) == TRUE)
              

              зачем сравнивать isset(...) с TRUE? Что за быдлокод?
              0
              Этот код у Вас для какой версии PHP?

              У меня в php 5.3.15 этот код:
              &$this->List[]
              

              вызывает parse error

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


                Откуда терминология?

                Only users with full accounts can post comments. Log in, please.