Почему связанный список лучше массива

В проектировании любой системы ключевую роль играет выбор структуры данных. Сейчас мы с вами попытаемся разобраться с двумя структурами данных, а так же подчеркнем плюсы и минусы каждой. Так же сделаем замеры по памяти.

С чего начнем (Постановка задачи)

Нужно обработать список сущностей. Сама по себе сущность (для простоты) представляет собой модель (объект) в которой всего одно свойство «value».

Model( value: int )

Решение через массив + stdClass

Многие разработчики сразу подумают «если мне нужно обработать список моделей мне нужен массив». Массив самая простая структура данных (На мой взгляд).

Для решения данной проблемы нам подойдет следующий код:

$count = 100; $list = [];  for ($index = 0; $index <= $count; $index++) {   $model = new stdClass(); // создаем обьект (модель)   $model->value = $index;  // указываем значение      $list[$index] = $model;  // вносим новую модель в массив }

В чем же плюсы:

1. Проще (мало кода) — чем проще тем лучше скажут многие.

Минусы:

1. Ох уж этот stdClass. Мало того что нет интерфейса взаимодействия, так еще возможны утечки памяти. (В этой статье описаны его минусы).

2. Потребляет памяти больше чем ожидалось. В PHP массивы не самые экономные так еще и stdClass кушает больше чем ожидалось.

Решение через массив + Model class

Текущее решение похоже на (Решение через массив + stdClass). Единственное и важное отличие это создание интерфейса (класса модели)

$count = 100; $list = [];  class Model {   protected int $value;         // значение модели   public function __construct(int $value)   {     $this->value = $value;   } }  for ($index = 0; $index <= $count; $index++) {     $list[$index] = new Model($index);  // вносим новую модель в массив }

Какие плюсы:

1. Код прост.

2. Есть интерфейс взаимодействия с моделью.

3. В виду отсутствия stdClass меньше потребляет памяти.

Какие минусы:

1. Чуть усложняется работа с массивом (например фильтр возможно потребует нового метода в модель).

2. В PHP массивы не самые экономные по памяти.

Решение через связанный список

Не многие (в основном профи) могут подумать а может стоит использовать связанный список?

$count = 100;  class LinkedList {   protected int $value;         // значение модели   protected ?LinkedList $next = null; // следующий элемент    public function __construct(int $value)   {     $this->value = $value;   }    // добавление следующего элемента    public function add(LinkedList $next): LinkedList   {     $this->next = $next;     return $next;   } }  $root = new Node(0); // связаный список  for($index = 1; $index <= $count; $index++) { $node = ($node ?? $root)->add(new Node($index)); } unset($node);

Какие плюсы:

1. Есть интерфейс взаимодействия

2. Меньшее потребление памяти

3. Многие будущие операции будут выполнятся быстрее (смотря как напишет программист)

Какие минусы:

1. Чуть усложняется работа с данными так как структура другая фильтр будет работать по другому.

Тесты

Наш тест будет происходить на платформе OnlinePHP.io (Можно стразу зайти и проверить результаты)

Вывод

Хоть мы тестили на 100 элементах, даже на них видно какой объем памяти занимал тот или иной вариант решения.

Если ваш продукт работает с большим количеством данных, то самый лучший вариант для вас это «Связанный список». Если ваш продукт еще не работает с большим количеством данных, то мой совет не используйте stdClass.

Полный скрипт (для самостоятельных тестов)

Этот код был написан только для ознакомительных целей (Не используйте его в своих проектах).

$count = 100;  class LinkedList { protected int $value; protected ?LinkedList $next = null; public function __construct(int $value) { $this->value = $value; } public function add(LinkedList $next): LinkedList { $this->next = $next; return $next; } }  class Model { protected int $value; public function __construct(int $value) { $this->value = $value; } }  // ----------------------------------- // -----------------------------------  $memory_get_usage = memory_get_usage();  echo 'list before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage ) . "\n";  $root = new LinkedList(0);  for($i = 1; $i <= $count; $i++) { $next = ($next ?? $root)->add(new LinkedList($i)); } unset($next);  echo 'list set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";  unset($root); echo 'list after -- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n\n";  // ----------------------------------- // -----------------------------------  $memory_get_usage = memory_get_usage();  echo 'array + model before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n"; $list = []; for($index = 0; $index <= $count; $index++) { $list[$index] = new Model($index); } echo 'array + model set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n"; $list = []; unset($list); echo 'array + model after -- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n\n";  // ----------------------------------- // -----------------------------------  $memory_get_usage = memory_get_usage();  echo 'array + stdClass before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n"; $list = []; for($index = 0; $index <= $count; $index++) { $model = new stdClass(); $model->value = $index; $list[$index] = $model; } echo 'array + stdClass set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n"; $list = []; unset($list); echo 'array + stdClass after -- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n\n";