В проектировании любой системы ключевую роль играет выбор структуры данных. Сейчас мы с вами попытаемся разобраться с двумя структурами данных, а так же подчеркнем плюсы и минусы каждой. Так же сделаем замеры по памяти.
Big-O cheat sheet - поможет вам выбрать структуру данных.
Для любителей работать с массивом по индексу статья будет не интересна! Вам для оптимизации ВОЗМОЖНО пригодится SplFixedArray.
Далее фраза "Массив" - будет использована как упрощение. Массив в PHP на самом деле является упорядоченной картой. (Возможно статья должна называться "Связанный список лучше хеш таблицы или нет?")
Почему массив и "Связанный список" разные вещи?
Если рассматривать относительно PHP, мы сравниваем HashMap с LinkedList.
Если относительно организации хранения данных, то связанный список хранит ссылку на следующий элемент. Чего не должен делать обычный классический массив.
На сколько хороши или плохи связанные списки, фирма Apple использует их достаточно часто, но без PHP.
С чего начнем (Постановка задачи)
Нужно обработать список сущностей. Сама по себе сущность (для простоты) представляет собой модель (объект) в которой всего одно свойство "value".
Model( value: int )
Решение через массив + stdClass
Многие разработчики сразу подумают "если мне нужно обработать список моделей мне нужен массив". Массив самая простая структура данных (На мой взгляд).
Для решения данной проблемы нам подойдет следующий код:
$count = 100;
$list = [];
for ($index = 0; $index <= $count; $index++) {
$model = new stdClass(); // создаем обьект (модель)
$model->value = $index; // указываем значение
$list[$index] = $model; // вносим новую модель в массив
}Мы не будем использовать очевидную оптимизацию кода ниже, так как (выше написано) мы будем хранить структуру (Модель).
$arr = [];
for($i = 1; $i <= $count; $i++) {
$arr[] = $i; // Удобно но к нашему иследованию не имеет отношение
}В чем же плюсы:
Проще (мало кода) - чем проще тем лучше скажут многие.
Минусы:
Ох уж этот stdClass. Мало того что нет интерфейса взаимодействия, так еще возможны утечки памяти. (В этой статье описаны его минусы).
Потребляет памяти больше чем ожидалось. В 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); // вносим новую модель в массив
}Какие плюсы:
Код прост.
Есть интерфейс взаимодействия с моделью.
В виду отсутствия stdClass меньше потребляет памяти.
Какие минусы:
Чуть усложняется работа с массивом (например фильтр возможно потребует нового метода в модель).
В 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);Какие плюсы:
Есть интерфейс взаимодействия
Меньшее потребление памяти (если не использовать модель)
Многие будущие операции возможно будут выполнятся быстрее (смотря как напишет программист)
Какие минусы:
Отсутствие доступа по index (или добавления метода)
Создается впечатление что данных меньше (из за того, что не используем класс модели)
Чуть усложняется работа с данными так как структура другая фильтр будет работать по другому.
В том числе за счёт распределённости в памяти, список из большого числа элементов будет проигрывать по скорости банально из-за кеша.
Решение через связанный список + Model class
$count = 100;
class Model {
protected int $value; // значение модели
public function __construct(int $value)
{
$this->value = $value;
}
}
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(new Model(0)); // связаный список
for($index = 1; $index <= $count; $index++) {
$node = ($node ?? $root)->add(new Node($new Model()));
}
unset($node);Какие плюсы:
Есть интерфейс взаимодействия
Многие будущие операции возможно будут выполнятся быстрее (смотря как напишет программист)
Какие минусы:
Отсутствие доступа по index (или добавления метода)
Теперь он кушает больше чем массив
Чуть усложняется работа с данными так как структура другая фильтр будет работать по другому.
В том числе за счёт распределённости в памяти, список из большого числа элементов будет проигрывать по скорости банально из-за кеша.
Тесты
Наш тест будет происходить на платформе OnlinePHP.io (Можно стразу зайти и проверить результаты)
Вариант решения PHP 8.2 |
RAM USAGE |
AFTER UNSET |
8'112.00 B |
32.00 B |
|
13'768.00 B |
32.00 B |
|
8'272.00 B |
0.00 B |
|
44'632.00 B |
416.00 B |
Вариант решения PHP 8.1 |
RAM USAGE |
AFTER UNSET |
8'112.00 B |
32.00 B |
|
13'768.00 B |
32.00 B |
|
13'904.00 B |
0.0 B |
|
50'264.00 B |
416.00 B |
Вариант решения PHP 8.0 - 7.4 |
RAM USAGE |
AFTER UNSET |
8'080.00 B |
40.00 B |
|
13'696.00 B |
40.00 B |
|
13'904.00 B |
0.0 B |
|
50'264.00 B |
416.00 B |
Вывод
В тесте мы использовали 100 элементов, но думаю даже на них видно какой объем памяти занимал тот или иной вариант решения. Почему так мало элементов? (Для простоты)
Возможно "Связанный список" будет отличным решением для той или иной задачи. Важно понимать как будет происходить чтение, запись, очистка.
Но самое главное избегайте stdClass.
Полный скрипт (для самостоятельных тестов)
Этот код был написан только для ознакомительных целей (Не используйте его в своих проектах). Прошу Вас не ругать выбранный вариант тестирования.
$count = 100;
class LinkedList {
protected $value;
protected ?LinkedList $next = null;
public function __construct($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 'list + model before - ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage ) . "\n";
$root = new LinkedList(new Model(0));
for($i = 1; $i <= $count; $i++) {
$next = ($next ?? $root)->add(new LinkedList(new Model($i)));
}
unset($next);
echo 'list + model set ---- ' . sprintf( '%.2f B', memory_get_usage() - $memory_get_usage) . "\n";
unset($root);
echo 'list + model 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";
Ответы на вопросы
А если нужен доступ к элементу по индексу? Связный список сразу проиграет.
Действительно, я не учел что есть люди которым нужен доступ по индексу. Решение для вас: Если вы каким либо образом знаете индекс не используйте связанный список. Вам нужна другая структура данных. В статье нет упоминания что это панацея. Если нужно читать объекты по порядку например foreach то ни какой проблемы нет (итератор). По мне так foreach выгоднее и удобнее.
А ты прям хардкодишь и знаешь что нужное значение под индексом 3?
Для того что бы было понятно что происходит в 3 пункте нужно прочитать 1 и 2
В решении через связанный список отсутствует Model вовсе, что даёт ложное ощущение экономности по памяти.
Список по определению требует памяти больше, чем массив. В том числе за счёт распределённости в памяти, список из большого числа элементов будет проигрывать по скорости банально из-за кеша.
Для простоты сделал так. Согласен с тем что после добавления модели обьем памяти увеличивается.
Комментарии (64)
shasoftX
03.08.2023 16:09+12А если нужен доступ к элементу по индексу? Связный список сразу проиграет.
adideas Автор
03.08.2023 16:09Это не будет проблемой если использовать итератор или если расширить класс (добавить метод getFromIndex)
FanatPHP
03.08.2023 16:09Метод добавить можно, но предыдущий оратор говорит не об этом, а о том, что этот метод будет работать по алгоритму Шлёмы-маляра
А итератор тут совсем не при чем
dronperminov
03.08.2023 16:09+11В решении через связанный список отсутствует Model вовсе, что даёт ложное ощущение экономности по памяти.
Список по определению требует памяти больше, чем массив. В том числе за счёт распределённости в памяти, список из большого числа элементов будет проигрывать по скорости банально из-за кеша.
FanatPHP
03.08.2023 16:09+4Ну, справедливости ради, он просто заменяет Model на LinkedList.
Другое дело, что в 8.2 потребление памяти практически сравнялось, и этот аргумент уже просто становится ничтожным. И автору бы здесь остановиться и либо признать, что статья потеряла актуальность, или привести другие доводы за использование списка.У меня несколько раз была как раз такая ситуация — новая версия РНР ставила крест на статье или докладе.
BetsuNo
03.08.2023 16:09+2Всё зависит от решаемой задачи, а не от абстрактного «Если ваш продукт работает с большим количеством данных». Big-O cheat sheet вам в помощь.
ColdPhoenix
03.08.2023 16:09+11Вот из-за таких "профи" сайты часто и скачут по памяти...потому что грузим все сразу в память.
Учим итераторы, а ещё раз мы знаем размер массива, то есть ещё SplFixedArray.
ToRcH2565
03.08.2023 16:09А давно в пхп завезли массивы? хэш таблицы помню, массивов - не помню. (а это очень разные вещи в плане устройства внутри и получаемых плюсов\ минусов производительности)
SerafimArts
03.08.2023 16:09А чем обычная строка — это не массив? ;)
GospodinKolhoznik
03.08.2023 16:09-2Всё же скорее список. Вы можете в этой строке найти элемент с произвольным индексом за O(1) операций? Я не могу. А найти следующий элемент, после любого символа в этой строке - легко.
arokettu
03.08.2023 16:09Строка в PHP определена как массив байтов, произвольный байт как раз находится за O(1)
GospodinKolhoznik
03.08.2023 16:09-2Я говорил про обычную строку текста, безотносительно какого либо ЯП. Чтобы определиться чем является строка в реальном мире и какая из структур данных описывает ее ближе к реальности - массив или связанный список.
arokettu
03.08.2023 16:09Статья и тред - про PHP
GospodinKolhoznik
03.08.2023 16:09Связанные списки и массивы в PHP отличаются от связанных списков и массовив в других ЯП?
hello_my_name_is_dany
03.08.2023 16:09+1Структуры данных придуманы не для описания реального мира, а для эффективной работы с данными.
Для описания реальности есть различные парадигмы программирования
SerafimArts
03.08.2023 16:09+1Вы можете в этой строке найти элемент с произвольным индексом за O(1) операций?
Можно конечно. Берётся указатель на строку и прибавляется к нему сдвиг. Вот и элемент.
Грубо говоря:
$array = '1234'; echo $array[2]; // 3 // ^^^^^^^^^ вот это и есть 0(1)И есть подозрение, что в PHP разыменование у строки — это интринсик (после JIT), вместо FETCH_DIM_R, который делает это всё за O(n). Но нужно смотреть уже асм сгенерированный, а я там ни бум-бум, так что не гарантирую.
Для примера, у меня есть пакет, который это всё реализует: https://github.com/SerafimArts/PackedArray Но это чисто по-фану и не для продакшн использования. И естественно он потребляет на порядки меньше оперативы, т.к. строка — это просто zval с массивом внутри, а не хеш-мапа, как array в PHP.
GospodinKolhoznik
03.08.2023 16:09-2Так для этого вам потребовалось сначала скопировать написанную мной строку в некоторый массив, что займет явно больше O(1). А с самой строкой исходной (которую вы видите глазами) вы этого сделать не смогли бы. А найти следующий элемент для любого элемента строки вы и глазами легко можете сделать, без помощи компьютера. Поэтому строка в реальном мире ближе к связанному списку, т.к. имеет с ним схожий интерфейс взаимодействия.
SerafimArts
03.08.2023 16:09+2Ничего не понял.
Связанный список — это связанный список. Структура данных, где предыдущий элемент содержит указатель на последующий. Физически это выглядит как граф с одним ребром:
class Item { public function __construct( public int $value, public ?Item $next = null, ) {} } $list = new Item( value: 42, next: new Item( value: 23, next: new Item( value: 0xDEAD_BEEF, ), ), );Про копирование — тоже ничего не понял. Любое копирование одной памяти в другую — это memcpy, если тупо адрес нужно скопировать (для массива, например), то memset.
А массив — это просто упорядоченный набор байтиков с указателем на первый элемент. Каждый последующий будет получаться через формулу: "адрес + размер_типа * номер_элемента" (поэтому почти везде подсчёт массива ведётся от нуля, т.к. адрес первого символа будет складываться с нулём, что вернёт адрес первого элемента).
И памяти он занимает ровно столько, сколько требуется. Если нужно 42 байта, то займёт 42 байта (в рамках PHP добавится ещё структура zend_string внутри zval, в которой будет указатель на этот самый массив байтиков).
Поэтому я и написал, что в PHP строки — классические массивы, ровно такие же, как в C/C++ (и в других языках, где строки являются лоу-левельными, без локализации и прочей инфы). Т.к. с точки зрения структуры данных пакуются точно так же, как любой другой массив и занимают столько памяти, сколько байт в строке (+ враппер с метаданными)
GospodinKolhoznik
03.08.2023 16:09Я писал про строку, а вы упорно пишите не про строку, а про представление строки в памяти компьютера. Из за этого и не можете понять.
arokettu
03.08.2023 16:09Строка это тип данных, тип данных это описание представления в памяти компьютера. Нельзя отделить строку и ее представление
FanatPHP
03.08.2023 16:09+1Так для этого вам потребовалось сначала скопировать написанную мной строку в некоторый массив
Я думаю, вы что-то путаете. Здесь нет никакого копирования.
GospodinKolhoznik
03.08.2023 16:09-2Ок, откройте книгу А.С. Пушкина "Евгений Онегин". Можете найти в ней 5000й символ без того, чтобы предварительно скопировать всю книгу в память компьютера? Вам для этого потребуется 5000 операций. При этом вы можете наугад тыкнуть на любой странице в любой символ и сразу найти следующий за ним.
Так понятней? Я писал именно про строку, а не про её представление в памяти компьютера.
FanatPHP
03.08.2023 16:09+2Вы тупите совершенно безбожно. Речь о книге, которая УЖЕ в памяти компьютера. Попробуйте вспомнить свои собственные слова, без литературных реминисценций:
Вы можете в этой строке найти элемент с произвольным индексом за O(1) операций?
Да, могу.
для этого вам потребовалось сначала скопировать написанную мной строку в некоторый массив
Копировать её никуда не надо. Потому что это УЖЕ массив. С произвольным доступом.
Если вам вдруг померещилось, что строки в РНР — это не byte arrays, а некие "связанные списки", то потрудитесь привести хоть какой-то источник, подтверждающий эту идею.
GospodinKolhoznik
03.08.2023 16:09-2А до вас постепенно начинает доходить. Пройдет ещё пару дней и может быть дойдёт окончательно, но это не точно.
Как вы работаете в отрасли с такой задумчевой соображалкой? Пока я совсем всё не разжевал до вас не доходило.
Hardcoin
03.08.2023 16:09-1Можно конечно.
К сожалению нет, если строка utf8. Php конечно позволит обратиться по индексу, но там будет далеко не O(1)
SerafimArts
03.08.2023 16:09+3В PHP нет понятий "utf8 строка" или какой-то другой (бинарные строки, вида
$str = b'string';из языка удалили). Любая строка в PHP (как и в любом языке, где low-level строки) — это набор байт. Как этот набор байтиков сохранится редактором — так и будет.В том случае, если требуется брать больше одного байта, то берётся больше одного байта:
$bytes = '...'; $char = $bytes[0]; $uint8 = ord($bytes[0]); $uint16le = ord($bytes[0]) | ord($bytes[1]) << 8; $uint16be = ord($bytes[1]) | ord($bytes[0]) << 8; // .... $uint48le = ord($bytes[0]) | ord($bytes[1]) << 8 | ... | ord($bytes[5]) << 40;Фактическое отличие от ЯП с массивами в том, что в PHP операции разыменования работает всегда с uint8, т.е. любая строка априори
uint8[](илиchar[]), а получениеuint16[]и других происходит через пару байтuint8[x] + uint8[x + 1](в случае с little endian), которые следует объединить в одинuint16для использования в качестве числа (а можно этого и не делать, работая отдельно с байтиками).Так что строки — это массивы. Просто оператор разыменования умеет работать только с 1 байтом за операцию.
*P.S. Возможно многие путаются, из-за того, что в PHP строка — это отдельный тип данных, который преобразовывается в числа иначе, чем это сделано в более низкоуровневых языках, но фактически "внутри" оно выглядит так:
$string = "PANKAJ"; // На уровне внутреннего представления: char string[] = ['P', 'A', 'N', 'K', 'A', 'J', '\0']; // Что фактически эквивалентно: uint8_t string[] = [80, 65, 78, 75, 65, 74, 0]; // Что хранится в оперативке примерно так (адрес + значение): 0x0001 80 0x0002 65 0x0003 78 ... 0x0007 00 // И получение в PHP всегда по одному байту: 0x0001 80 // char[0] -> 'P' 0x0002 65 // char[1] -> 'A' // В отличие от некоторых других языков, // где можно получить сразу два байта: 0x0001 + 0x0002 // wchar_t[0] -> "PA" // Или в другом виде: 0x0001 + 0x0002 // uint16_t[0] -> "80 | 65 << 8" -> 16720 // Для этого и существуют функции pack/unpack, // которые могут оперировать сразу несколькими // байтами строки и сразу же кастовать их в другой вид: echo unpack('v', 'PA')[1]; // 16720И оба этих массива содержат идентичные данные. Это всего лишь вопрос репрезентации (отображения на экране компьютера). В формате "из циферок" или в формате "из буковок". Данные не меняются. А utf8 всего лишь один из вариантов отображения тех же самых циферок в другом виде и всё.
P.P.S. С таким же успехом можно взять 4 байта
$string = [0xf0, 0x9f, 0x98, 0x8a];, применить для них chr (т.е. скастовать каждый байт к типу строки), объединить в одну и получить смайлик????, если отрисовать в юникоде.// 'cccc' означает, что каждый аргумент - это 1 байт (char) echo pack('cccc', 0xf0, 0x9f, 0x98, 0x8a); // '????' // Так же и получение первого байта из 4х echo '0x' . dechex(ord('????'[0])); // 0xf0P.P.P.S.
1) Преобразование для "c" + "C": https://github.com/php/php-src/blob/633e7455e55cb734acea13a14d73b8e976ad2158/ext/standard/pack.c#L1020-L1021
2) И для сравнения получение сразу двух байт: https://github.com/php/php-src/blob/633e7455e55cb734acea13a14d73b8e976ad2158/ext/standard/pack.c#L1033 + там чуть ниже каст значения к (u)int16 чтоб запихнуть его в пхпшный инт (который имеет размер int32/int64).Hardcoin
03.08.2023 16:09-1Спасибо за подробный комментарий с примерами. Возражений, что строка - это массив, у меня не было. Вы так же правы, что php не хранит в строке данные о кодировке.
Однако если у вас есть массив utf8-символов (не байт) и строка, которую вы интерпретируете как utf8, поиск N-го символа (не байта) будет существенно отличаться. Во втором случае за O(1) найти не получится.
SerafimArts
03.08.2023 16:09Поиск как раз будет за О(1), а чтение всех данных за О(2).
FanatPHP
03.08.2023 16:09+1Не, не. Не будет там О(1). Смещение определенного символа заранее неизвестно. Скажем, у второго это может быть и 1, и 2 и 3. Это же utf-8, с переменной длиной символа. Без чтения и интерпретации всех предыдущих найти искомый не получится.
Но блин вопрос вообще не в этом. Не нужно разыгрывать его карту. То, как именно кодируется информация в строке, здесь в принципе не при чем.
SerafimArts
03.08.2023 16:09А, ну если прям поиск подстроки в строке, то да, нигде невозможно за
O(1). Это в любом случае будетO(n), а в пыхе просто[от O(n) до O(n*4-3)](но это не точно).А про утф… Ну да, не касается тезиса. Потому что это вопрос интерпретации, а не структуры данных, которая используется для хранения данных. Но почему нет?
FanatPHP
03.08.2023 16:09+2Да блин, не про поиск подстроки речь. Поиск подстроки это немного другое (хотя по механике будет похоже, да).
Вопрос (который тут оффтопик) — про поиск символа по индексу.
Такое ощущение, что я один тут держу в голове весь контекст :)Смотри, чувак тут решил всем открыть страшную тайну, что обращение по индексу для строк, содержащих многобайтные символы, не сработает. И в этом контексте совершено правильно заявляет, что
Во втором (utf-8) случае за O(1) найти не получится.
Чтобы найти символ по индексу, UTF-8 строку надо перебирать с самого начала по одному-два байта, и считать найденные символы. Он говорит об этом. И только об этом. И тут спорить не с чем по сути. И не нужно. Потому что он уводит разговор в сторону. Вопрос не о декодировании информации в строке, а является ли строка в РНР массивом байт.
В итоге:
- изначально речь шла про то, являются ли строки в пыхе массивами, или, с какого-то бодуна взятыми господином колхозником "связанными списками"
- тут влез господин твердый жетон чтобы показать всем свою эрудицию, и оставил с нерелевантный комментарий про утф.
- тут уже ты ступил, сказав что поиск в utf-8 будет за О(1).
- а потом еще раз, решив что речь про поиск подстроки
Вот в этом как раз и вред таких уводов в сторону :)
В чем он, наверное, прав — это в том, что синтаксический сахар с $string[1] не стоит приводить в качестве аргумента. Тут скорее докажет бенчмарк, который покажет одинаковое время и для десятого, и для стотысячного байта.
SerafimArts
03.08.2023 16:09тут уже ты ступил, сказав что поиск в utf-8 будет за О(1).
А вот как раз таки и нет))) Всё зависит от того, как хранятся данные. Например в том случае, если это стандартный вариант с wchar_t, которым оперирует почти что любое ПО, то будет как раз таки O(1), так как каждый чар, даже которому это не нужно — подгоняется под 16/32 байт. Кейс верхними + нижними суррогатами можно тоже в этом случае проигнорировать (в случае винды, где whar_t 16 байт), т.к. это обычный ифчик с проверкой суррогата, что даёт в конце всё равно константное время.
а потом еще раз, решив что речь про поиск подстроки
А в случае тезиса с "подстроком подстроки в строке" — используется не обычное представление из whar_t, а запакованный формат с произвольным размером. Так как понял, что человек не знает как работает ПО с юникодом, а только лишь как передаётся в запакованном виде и пытается на этом подловить.
FanatPHP
03.08.2023 16:09Всё зависит от того, как хранятся данные.
Интересно, не знал. Но в данном случае мы говорим про пхп, а в пыхе, соответственно, О(1) невозможно.
SerafimArts
03.08.2023 16:09Но в данном случае мы говорим про пхп
Потому что в PHP нет никаких "utf-8 строк", о чём я в самом начале и написал.
А там где есть такое, вполне возможно выровненное хранение, где на 1 буковку приходится строго 4 байта (например utf8mb4 в maria/mysql) добитые нулями (но это, кстати, тоже не точно, нужно сырцы БД потрошить). Потому что кейс с вариативным размером — это уже практическая задача с декодированием и должна была звучать как "За какую алгоритмическую сложность можно декодировать utf-8" и в этом случае уже проще почитать всякие статьи: https://habr.com/ru/articles/138173/
Но ты прав в том, что вопрос ушёл вообще в другую сторону, а я повёлся)))
Hardcoin
03.08.2023 16:09+1чтение всех данных за О(2).
Вы абьюзите big-O нотацию :). O(2) эквивалентно O(1)
Про O(1) вам уже ниже ответили. К сожалению символ из utf8 строки с единичной сложностью не прочитаешь. Если нужна ссылка, то вот вопрос на стаковерфлоу
SerafimArts
03.08.2023 16:09- Я: Строка — это массив
- Оппонент: Нет, из неё нельзя прочитать за O(1)
- Я: Можно, т.к. любое разыменование — это O(1)
- Вы: Нет, нельзя, так как из массива int8 невозможно за O(1) прочитать int32.
Осталось понять причём тут вообще чтение значения int32 из массива из int8? Попытка натянуть сову на глобус? Вы бы ещё написали: "Нет, нельзя прочитать за O(1), потому что нельзя отсортировать за О(1)" или "нет нельзя, потому что оно не выводит числа Фибоначчи за O(1)". Причём тут вообще это?
То что вы там пытаетесь прочитать сразу 4 байта из массива байт — это сугубо ваша практическая задача. Она никак к тезису не относится.
Hardcoin
03.08.2023 16:09Во-первых, прочитать int32 из массива int8 за O(1) возможно. Во-вторых, действительно, при чём тут int32? Неужели вы путаете utf8 и int32? Может с utf32 перепутали? В utf8 переменное количество бит на символ. Не 8 и не 32, а разное, в зависимости от символа.
Для корректных аргументов вам следует глубже изучить и big-O нотацию и utf8.
Вы можете сказать, что я не прав, если хотите, но цитировать тут документацию не хочется. Достаточно базовые же вещи, легко гуглятся.
SerafimArts
03.08.2023 16:09Во-первых, прочитать int32 из массива int8 за O(1) возможно.
Это в C возможно. А вы, походу пропустили комментарий, где я раз сто написал, что оператор разыменования в PHP работает только с int8. И даже привёл в пример код на C из исходников PHP, где оно за одну операцию считывает больше одного байта за операцию.
Во-вторых, действительно, при чём тут int32?
Потому что это пограничный случай с максимальной длиной одного символа.
В utf8 переменное количество бит на символ. Не 8 и не 32, а разное, в зависимости от символа.
Тем более. Это ещё больше усугубляет проблему, т.к. вы пытаетесь подогнать практическую задачу с кучей пограничных условий под тезис.
Причём я так и не услышал вопрос — причём тут вообще utf-8? И как это относится к изначальному тезису о том, что операция разыменования — это O(1)?
Hardcoin
03.08.2023 16:09оператор разыменования в PHP работает только с int8
Сделайте 4 операции чтения. Это всё ещё O(1).
(Но пожалуйста, проверьте по документации, прежде чем возражать).
вы пытаетесь подогнать практическую задачу
Никакими кодировками кроме utf8 сейчас уже почти не пользуются.
Это не подгонка под тезис. Это опровержение тезиса примером. Вы можете прочитать из строки байт за O(1). Но вы не всегда можете прочитать символ.
То, что множество людей будут называть строкой вы НЕ можете интерпретировать как массив, несмотря на то, что под капотом это просто набор байт. Если вы будете пытаться работать с utf8, как с массивом, оценивать производительность как при работе с массивом, выставлять требования к железу, как при работе с массивом - у вас будут проблемы.
Однако под капотом, вы правы, это кусок памяти, в котором можно адресовать по смещению. Пользы только не будет, но формально можно, я согласен.
SerafimArts
03.08.2023 16:09Сделайте 4 операции чтения. Это всё ещё O(1).
Я это и с первого вашего комментария понял, что накосячил)
Никакими кодировками кроме utf8 сейчас уже почти не пользуются. Это не подгонка под тезис.
Как раз таки подгонка. Эти проблемы с доступом возникают лишь потому, что эта строка так запакована. Проблемы запаковки — это исключительно проблемы декодера utf-8 и того, как он декодирует и отдаёт данные. Никто не мешает хранить utf-8 в whar_t с выровненным (добитым нулями) доступом. Как, например, это делают некоторые БД для ускорения поиска. В этом случае поиск буковки в такой строке будет константный всегда.
Hardcoin
03.08.2023 16:09проблемы декодера
Я бы согласился, если бы мы обсуждали абстрактно, а не конкретно php. В нем есть набор функций для работы utf8, никакой особой выровненной упаковки они не делают.
Формально можно и связанный список в массиве хранить, а всё остальное поручить декодеру. Да и любую структуру данных. Да и массив - это просто кусок памяти с произвольным доступом (если только мы специально не делаем особый формат хранения).
SerafimArts
03.08.2023 16:09+1Я бы согласился, если бы мы обсуждали абстрактно, а не конкретно php. В нем есть набор функций для работы utf8, никакой особой выровненной упаковки они не делают.
Для начала, ещё раз повторюсь, что в PHP нет никаких utf-8 строк. А функции на то и функции, что реализуют алгоритмы поиска, декодирования и прочих манипуляций с данными. Никто при этом не мешает хранить utf-8 строку в UCS формате и искать в ней символы за константное время, а потом обратно запаковывать. Так же как никто не мешает распаковывать в памяти RLE-сжатие, находить в нём за константное время нужный элемент, а потом опять сжимать. Это лишь вопрос реализации декодера, а не вопрос разыменования элемента из массива.
Да и массив — это просто кусок памяти с произвольным доступом
Нет, массив — это упорядоченный в памяти кусок данных у которых есть указатель на первый элемент (а каждый последующий берётся за константное время через сдвиг адреса).
Вопрос был про то, что в PHP массивов нет. Мой ответ был про то, что в PHP массивы есть (строки), потому что они хранятся в памяти как упорядоченный и неразрывный кусок памяти. И доступ к элементам этого массива всегда константный, даже на уровне кода ядра PHP.
Не надо, пожалуйста, сравнивать тёплое с мягким.
Hardcoin
03.08.2023 16:09Для начала, ещё раз повторюсь, что в PHP нет никаких utf-8 строк.
Так и связанных списков в php нет, в чем тогда суть спора?
это упорядоченный в памяти кусок
Конечно упорядоченный. Как вы неупорядоченный кусок памяти сделаете?
упорядоченный и неразрывный кусок памяти
Float тоже так хранится. Упорядоченный и неразрывный кусок памяти. Только размером меньше. Подходит под ваше определение массива? Желаете педантичности, идите до конца.
Не надо, пожалуйста, сравнивать тёплое с мягким.
Так вы начали, я вам просто контрпримеры привожу.
SerafimArts
03.08.2023 16:09+1Так и связанных списков в php нет, в чем тогда суть спора?
1) Зато есть двухсвязные из коробки.
2) Их можно реализовать и технически они в памяти будут располагаться также, как и на С. И все обращения будут идентичными.Конечно упорядоченный. Как вы неупорядоченный кусок памяти сделаете?
Любой список как раз и выделяет память в случайных участках памяти, в отличие от массивов.
Array в PHP как раз и не является массивом, т.к. может выделить непоследовательный участок памяти, хотя в подавляющем большинстве случаев делает это последовательно:
Гифка с примером аллокаций памяти для массивовFloat тоже так хранится. Упорядоченный и неразрывный кусок памяти. Только размером меньше. Подходит под ваше определение массива? Желаете педантичности, идите до конца.
Не вижу противоречий. Float — это 1 байт, т.е. вполне себе массив из одного float или одного int8, или одного char, или двух int4 (если мы будем использовать lo + hi, как это сделано в некоторых системных апи). А ещё это может быть структурой:
<?php $float = FFI::new('float'); $float->cdata = 0.42; var_dump(FFI::cast('float[1]', $float));Или мы можем взять uint32 и это будет массив из 4х uint8:
<?php $uint32 = FFI::new('uint32_t'); $uint32->cdata = 0b0000111100001111; var_dump(FFI::cast('uint8_t[4]', $uint32));Опять же, вопрос репрезентации и способа работы: Либо воспринимать как одно число, либо как массив из чисел.
А вот списки уже нет, т.к. там нет никакой гарантии упорядоченности и целостности памяти.
Hardcoin
03.08.2023 16:09выделяет память в случайных участках памяти,
Так это не кусок, а несколько разных кусков. Вы же говорили про кусок.
Float — это 1 байт
Смотрю на ваш код и вы вроде разбираетесь. А потом вы пишете что-то типа этого и становится не ясно. Как так? Вы не проверяете, что пишете или просто придумываете, если не знаете?
Float - не один байт. Обычно 8, но не всегда.
https://www.php.net/manual/en/language.types.float.php#:~:text=The%20size%20of%20a%20float,the%2064%20bit%20IEEE%20format).
SerafimArts
03.08.2023 16:09Так это не кусок, а несколько разных кусков. Вы же говорили про кусок.
Это когда я говорил, что список — это один большой кусок? о_0
Float — не один байт. Обычно 8, но не всегда.
Блин, очепятался конечно же)
Hardcoin
03.08.2023 16:09Это когда я говорил, что список — это один большой кусок? о_0
Список - нигде, конечно. Речь про массив была. Мы обсуждали массив и вы переключились на список.
SerafimArts
03.08.2023 16:09И в чём тогда претензии? Массивы выделяются одним куском, да. А в пыхе такой кусок выделяется только для строк. Что не так-то?
FanatPHP
03.08.2023 16:09Вы здесь потеряли контекст, как это часто бывает, когда обращаешь внимание на отдельный комментарий в середине обсуждения.
Речь шла про строки как тип данных, а не сами данные и их интерпретацию. UTF там, или, скажем — CSV, нам, в данном случае, без разницы. То, что вы вы можете получить невалидный с точки зрения UTF-8 симвал — это вопрос исключительно интерпретации.Hardcoin
03.08.2023 16:09Не сказал бы, что потерял контекст. Скорее расширил его. Получить байт по индексу действительно можно, вы правы. Если ваша задача - получить байт, то всё сработает.
Однако получить именно символ за O(1) не получится. В огромном количестве реальных задач это важно. "Исключительно интерпретация" исключительно важна при решении любой задачи, кроме академической.
FanatPHP
03.08.2023 16:09+1Не "расширили" а ушли совсем не в ту сторону. Вы не поняли контекст обсуждения, и просто решили прокомментировать знакомое слово, которое случайно увидели в тексте. Такие дурацкие ответвления — это рак любых обсуждений, и на Хабре в том числе, когда исходная тема забалтывается не относящиимся к ней комментариями.
"Исключительно интерпретация" исключительно важна при решении любой задачи, кроме академической — все верно, возьмите с полки пирожок за высказывание столь же истинной, сколь и банальной сентенции. И постарайтесь впредь сначала понять обсуждаемый вопрос, а потом уже бежать добавлять свои 5 копеек.
Hardcoin
03.08.2023 16:09Грубо, настойчиво, но необоснованно. Просьба аргументировать свою позицию, а не просто называть собеседника дураком.
Вы не поняли, на что я отвечал, влезли в контекст и стали говорить, что именно я его не понял. Слишком самоуверенно вы пытаетесь "починить" чужой разговор. Хотите участвовать - участвуйте.
FanatPHP
03.08.2023 16:09+1Тут проблема не в аргументации, а в спеси. Синдроме непризнанного гения. Хотели бы — давно бы все поняли, вам два человека по очереди пытались объяснить. И поэтому "просьба аргументировать" выглядит троллингом. Вы все равно не собираетесь даже рассматривать аргументы.
К вопросу, является ли строка в РНР массивом или связанным списком, ваши банальные рассуждения про utf-8 ни имеют ни малейшего отношения. И столь же релевантны, как и заявление, что в csv строке нельзя найти искомый элемент за О(1). Да, нельзя. Но разговор не про CSV. И не про UTF-8.
Hardcoin
03.08.2023 16:09Тут проблема не в аргументации, а в спеси.
И в аргументации проблема и в спеси. Может и в синдроме, но вам лучше не со мной обсуждать. Может вам и так нормально.
Вы все равно не собираетесь даже рассматривать аргументы.
Чтение мыслей не делает ваши рассуждения убедительнее. Так же как и Ad hominem.
является ли строка в РНР массивом или связанным списком,
Вы любую область памяти можете рассматривать как массив. Связанный список, объект - плевать, вы же можете получить байт по смещению, значит массив. А то, что в итоге получите бессмыслицу - не важно, байт-то вышло получить.
Вот суть вашей аргументации "строка - это массив".
tsukasa_mixer
03.08.2023 16:09Таки в пыхе и то и то, но зависит от того как использовать, покрайней мере в старых версиях если мы добавляем в массив неразрывно элементы по автоиндексации, то потребление памяти меньше и массив работает как массив, но стоит разорвать порядок элементов, как массив переходит на хеш таблицу, еще раз повтррюсь, что данное поведение наблюдалось в старых версиях php и как оно щас работает, надо посмотреть
SerafimArts
03.08.2023 16:09+1Сейчас всё тоже самое. У массива есть флаг HASH_FLAG_PACKED, который оптимизирует такие массивы. А сочетание HASH_FLAG_PACKED + проверка на "дырки" в массиве вынесена в юзерленд-функцию array_is_list
GospodinKolhoznik
03.08.2023 16:09+6Я не побоюсь написать этот банальный штамп: аффтор, вы просто жжоте своим заголовком! Это же надо такое выдать. Это даже круче, чем Linux лучше чем Windows или ЦСКА лучше чем Спартак.
Связанные списки лучше чем массивы. - Чем? - Чем массивы!
adideas Автор
03.08.2023 16:09Прошу держать себя в руках. Связанный список не массив пхп. Прошу прочитать об этом хотя бы в официальной документации к PHP. Употребления фразы массив законно так как описывает поведение (Все давно уже знают что это хеш таблицы.)
Если для Вас запорожец и трактор это машина... то почему на поле работают только тракторы? Быть может есть достаточно важные факторы заставляющие нас отличать эти две структуры.
Ksoo
03.08.2023 16:09А зачем вот это все? если не хватает десятков гигабайт оперативной памяти чтобы сделать что то на php, то надо либо алгоритм поменять, либо выбрать другой инструмент. Грузите в БД, пусть она думает как обработать это все и не упасть.
Viacheslav01
03.08.2023 16:09Тесты на основе которых сделаны выводы ужасны:
1) В первом тесте все сжирает stdClass и массив тут не причем.
2) В ПХП нет массивов, а есть динамические массивы, они же списки.
3) Я не знаю реализацию списков на ПХП но думаю там все по классике, а значит при переполнении идет удвоение размера. Тесты получаются размеро зависимые.
4) Выделение памяти, инициализация, уборка мусора за каждой нодой, это все стоит не бесплатно.В реальности не встречал кейсов где есть реальный плюс от использоваия связанных списков, тем более в управляемых средах.
pudovMaxim
03.08.2023 16:091) Да, оверхед от массива 3032 (44 632 - 41 600)
Если извращаемся с stdClass-ом, так и не понял зачем, то автор не учел самый очевидный способ "оптимизации":
$arr = []; for($i = 1; $i <= $count; $i++) { $arr[] = $i; }Также мы же говорим об оптимизации на больших значениях, а значит выигрыш в пару сотен байт от 100 элементов - это экономия даже не на спичках.
Если увеличить кол-во элементов до 10к, то происходит очень интересное:
list set ---- 922 992.00 B array + model set ---- 826 352.00 B
FanatPHP
Ну, справедливости ради, он просто заменяет Model на LinkedList.
Другое дело, что в 8.2 потребление памяти практически сравнялось, и этот аргумент уже просто становится ничтожным. И автору бы здесь остановиться и либо признать, что статья потеряла актуальность, или привести другие доводы за использование списка.
У меня несколько раз была как раз такая ситуация — новая версия РНР ставила крест на статье или докладе.