Comments 43
Проблема здесь в том, что обыкновенных массивов в PHP нет как понятия.
То, что вы там видите как нумерованный массив — на самом деле хранится в памяти в виде
Поэтому любое обращение «по индексу» в общем случае будет обращением по ключу и требует поиска пары ключ-значение в списке.
Насколько я понимаю их текущую реализацию, только при переходе от предыдущего элемента списка к следующему не надо ничего искать(вспоминаем списки из С).
Отсюда почти все «загадочности» с работой массивов в PHP.
И да, PHP — не для обработки больших данных :)
То, что вы там видите как нумерованный массив — на самом деле хранится в памяти в виде
[0=>'z_val',1=>'f_val',2=>'s_val']
['z_val','f_val','s_val']
Поэтому любое обращение «по индексу» в общем случае будет обращением по ключу и требует поиска пары ключ-значение в списке.
Насколько я понимаю их текущую реализацию, только при переходе от предыдущего элемента списка к следующему не надо ничего искать(вспоминаем списки из С).
Отсюда почти все «загадочности» с работой массивов в PHP.
И да, PHP — не для обработки больших данных :)
На самом деле массив в PHP — это упорядоченное отображение, которое устанавливает соответствие между значением и ключом. Этот тип оптимизирован в нескольких направлениях, поэтому вы можете использовать его как собственно массив, список (вектор), хэш-таблицу (являющуюся реализацией карты), словарь, коллекцию, стэк, очередь и, возможно, что-то еще. Так как значением массива может быть другой массив PHP, можно также создавать деревья и многомерные массивы.
Из их документации
Может возникнуть вопрос:
«А нафига?»
Так вот ответ, имхо, таков:
«Т.к. PHP язык для фронта, Ему зачастую приходится работать с данными со сложной ветвистой изменчивой структурой данных, что довольно удобно делать применяя встроенные функции и встроенный же функционал массивов, которые не совсем массивы.
А вот обработка большущих массивов однотипных данных в вашей страничке из фронта явно говорит о том, что вы что-то делаете не так, поэтому эффективностью такого варианта можно пожертвовать.»
«А нафига?»
Так вот ответ, имхо, таков:
«Т.к. PHP язык для фронта, Ему зачастую приходится работать с данными со сложной ветвистой изменчивой структурой данных, что довольно удобно делать применяя встроенные функции и встроенный же функционал массивов, которые не совсем массивы.
А вот обработка большущих массивов однотипных данных в вашей страничке из фронта явно говорит о том, что вы что-то делаете не так, поэтому эффективностью такого варианта можно пожертвовать.»
Проблема здесь в том, что обыкновенных массивов в PHP нет как понятия.
SplFixedArray? За исключением строгой типизации — классический массив с ОО интерфейсом.
Уже заметно лучше, но все еще не массив значений ) Индексы в нем явно в виде ссылок, иначе вот так
<?php
// Initialize the array with a fixed length
$array = new SplFixedArray(5);
$array[1] = 2;
$array[4] = "foo";
var_dump($array[0]); // NULL
var_dump($array[1]); // int(2)
var_dump($array["4"]); // string(3) "foo"
Ну это скорее уже поведение интерпретатора — он ожидает число в индексе, вот и конвертит автоматом строку в число при получении индекса.
нет, речь о том, что в классическом массиве невозможно хранить пременные переменной длины(проивольные строки хранить вообще никак). Только одинаковые блоки ) А в SplArray конвертируется любой php массив, так что это массив ссылок, но не значений.
Ну так я сразу же это и написал:
За исключением строгой типизации
Но ведь это принципиально разные массивы.
В классическом массиве доступ к произвольному элементу состоит из двух шагов:
1) прибавить к адресу начала масссива индекс * размер элемента(фиксированный)
2) считать данные из этого адреса в памяти
А в ссылочном:
1) прибавить к адресу начала массива адресов элементов индекс * размер ссылки на элемент(фиксированный)
2) считать по этому адресу адрес реального расположения данных
3) считать данные из их реального адреса.
В итоге — в полтора раза больше действий
В классическом массиве доступ к произвольному элементу состоит из двух шагов:
1) прибавить к адресу начала масссива индекс * размер элемента(фиксированный)
2) считать данные из этого адреса в памяти
А в ссылочном:
1) прибавить к адресу начала массива адресов элементов индекс * размер ссылки на элемент(фиксированный)
2) считать по этому адресу адрес реального расположения данных
3) считать данные из их реального адреса.
В итоге — в полтора раза больше действий
Попробую сегодня заменить обычный массив на SplFixedArray. О результата сообщу.
Вы смешиваете в одно список и хеш (то что вы представили в коде). Это разные структуры данных. В одной нет доступа по ключу, а другая даже не иметь такого понятия как «следующий элемент».
В коде я представил лишь схематичный вариант, чтобы показать что индексы хранятся точно так же как и сами значения.
Вы смешиваете в одно список и хеш.
Как и разработчики PHP, которых я, кстати, процитировал :)
ps минуснул не я
Вы смешиваете в одно список и хеш.
Как и разработчики PHP, которых я, кстати, процитировал :)
ps минуснул не я
Не понял, что вы имеете в виду под храняться точно так же.
Надеюсь, что разработчики PHP ничего не путают. Надеюсь, что они все таки понимают, что просто предоставляют структуру с интерфейсом массива и другими интерфейсами и стараются сделать ее удовлетворительно работающей для разных вариантов использования.
Надеюсь, что разработчики PHP ничего не путают. Надеюсь, что они все таки понимают, что просто предоставляют структуру с интерфейсом массива и другими интерфейсами и стараются сделать ее удовлетворительно работающей для разных вариантов использования.
Имею в виду то, что классические нативные массивы в РНР не представлены.
И хранится нечто вроде
Поэтому даже если вы объявите массив как набор однотипных значений, цифровой индекс каждого элемента будет храниться в качестве ключа.
И хранится нечто вроде
$array=[];
struct KeyValue{
void* key;
void* value;
KeyValue* prev;
KeyValue* next;
}
struct KeyValue* array;
Поэтому даже если вы объявите массив как набор однотипных значений, цифровой индекс каждого элемента будет храниться в качестве ключа.
А вы смешиваете хеш и словарь.
Словарь можно реализовать и на списках.
Словарь можно реализовать и на списках.
Хеш или точнее хеш-таблица — это одна из возможных реализаций словаря, она более на слуху, поэтому я использовал ее. Да, словарь можно реализовать на списках, как и любую структуру данных с использованием любой другой. Вопрос будет только в характеристиках такой реализации.
Ну вот в PHP массив (которых на самом деле словарь) реализован на списках. Ну это же очевидно, в самом деле :)
У вас же функция вставки одинаковая для всех вариантов? Так как же она может влиять на разницу в результатах?
Вообще вот тут habrahabr.ru/post/216103/ пишут, что массивы реализованы в виде двусвязных списков. Так что простой проход действительно дает лучшие варианты. Но вот для вставки можно использовать array_splice. ( stackoverflow.com/questions/3797239/insert-new-item-in-array-on-any-position-in-php ) В отличие от комбинации из трех функций в вашем первоначальном он осуществляет один проход.
Кстати времена 57 и 15 хорошо согласуются с 4мя и 1 проходами по массиву.
Вывод — алгоритмы и профилирование надо знать, но в инструменте тоже разбираться надо.
Вообще вот тут habrahabr.ru/post/216103/ пишут, что массивы реализованы в виде двусвязных списков. Так что простой проход действительно дает лучшие варианты. Но вот для вставки можно использовать array_splice. ( stackoverflow.com/questions/3797239/insert-new-item-in-array-on-any-position-in-php ) В отличие от комбинации из трех функций в вашем первоначальном он осуществляет один проход.
Кстати времена 57 и 15 хорошо согласуются с 4мя и 1 проходами по массиву.
Вывод — алгоритмы и профилирование надо знать, но в инструменте тоже разбираться надо.
Протестируйте, пожалуйста, на вашей конфигурации вариант с предварительным поиском позиции (ваши три способа), а затем вставкой с помощью array_splice:
array_splice($array, $position, 0, array($value));Попробовал заменить функцию вставки на
Так и правда быстрее. Но тем не менее найденный вариант с одним проходом остался лидером, но уже не с таки большим преимуществом.
Ну а статья собственно о том, что не всегда предположения и знания об алгоритмах на практике срабатывают. В данном случае изначально неверным было предположение, что главное найти позицию.
array_splice($array, $position, 0, array($value));
Так и правда быстрее. Но тем не менее найденный вариант с одним проходом остался лидером, но уже не с таки большим преимуществом.
insertBruteForce: 0.0020
insertBinary: 0.0028
insertInterpolation: 0.0027
insertDown: 0.0015
Ну а статья собственно о том, что не всегда предположения и знания об алгоритмах на практике срабатывают. В данном случае изначально неверным было предположение, что главное найти позицию.
Полагаю, что массив в 10 000 элементов недостаточно большой, чтобы хорошо увидеть разницу в скорости алгоритмов поиска места для вставки. Думаю, что будь массив на порядок-другой поболее — мы бы увидели более ожидаемые результаты.
Пробовал увеличить. Это на 100 тыс.:
Как по мне, результат еще менее ожидаемый.
insertBruteForce: 0.0260
insertBinary: 0.0412
insertInterpolation: 0.0413
insertDown: 0.0218
Как по мне, результат еще менее ожидаемый.
Похоже, у вас ошибка в методе insertBruteForce — цикл всегда выходит на первой итерации (при условии, что массив упорядочен по возрастанию). Если поменять "<" на ">" и использовать массив хотя бы на 100 000 записей, то результат уже выправляется.
Действительно допустил ошибку. Видимо когда заменял for на foreach. Исправил. Завтра поправлю еще результаты тестов. После исправления результат таков:
Как ни странно, мало что изменилось. Хотя «странность» немного уменьшилась.
insertBruteForce: 0.0369
insertBinary: 0.0427
insertInterpolation: 0.0423
insertDown: 0.0228
Как ни странно, мало что изменилось. Хотя «странность» немного уменьшилась.
можете, кстати, для insertBruteForce
поменять на
и удивиться еще раз =)
foreach($array as $position => $test) {
if ($test >= $value) {
поменять на
for($i=0;$i<count($array);$i++) {
if ($test >= $array[$i]) {
и удивиться еще раз =)
Рекомендую к ознакомлению вторую главу (Анализ) из книги Problem Solving with Algorithms and Data Structures, перевод которой мелькал на Хабре. В ней доходчиво объясняется понятие сложности алгоритмов. Соответственно перед тем, как сделать для себя открытие о том, что в конкретном языке, конкретная операция над конкретной структурой данных работает не так быстро\медленно как того ожидает разработчик, не мешало бы разузнать как именно реализованы данные операции в конкретном случае.
Сегодня обновлю текст с учетом всех выявленных ошибок, особенностей и новых результатов.
А какая скорость если вставить в конец и пересортировать встроенной функцией?
Можете выложить где-нибудь исходники бенчмарка, чтобы другие тоже могли поиграться?
Ещё я не увидел упоминания версии php.
Ещё я не увидел упоминания версии php.
Результаты вполне ожидаемые. На таком большом массиве вставка — самая медленная операция потому, что вы не можете просто «вставить» элемент в массив. Вам сначала нужно «подвинуть вправо на одну позицию» все элементы после индекса куда вы будете вставлять — а это N-index операций. Я тут опускаю, что впринципе и сам массив надо пересоздавать, т.к. изменился его размер — возможно в реализации PHP есть какие-то оптимизации для этого. При этом сам поиск позиции это всего лишь log2(N) операций (т.е. если мы вставляем в середину это 5000 и ~13 операций соответственно на 10к элементах).
Если вам нужна быстрая вставка и упорядоченные данные, то почему не использовать односвязный список? Вы так же перебором будете приходить к месту вставки, но сама вставка будет «бесплатная». Единственное преимущество массива перед другими структурами данных — это бесплатный доступ к элементу по индексу. Если вы не используете это, то я рекомендовал бы вам отказаться от массива в пользу списка.
Если вам нужна быстрая вставка и упорядоченные данные, то почему не использовать односвязный список? Вы так же перебором будете приходить к месту вставки, но сама вставка будет «бесплатная». Единственное преимущество массива перед другими структурами данных — это бесплатный доступ к элементу по индексу. Если вы не используете это, то я рекомендовал бы вам отказаться от массива в пользу списка.
На последнем опубликованном варианте есть такой интересный эффект: сначала быстрым алгоритмом найти позицию, а затем перебором выполнить сдвиг, быстрее чем искать нужную позицию во время выполнения сдвига — операции сравнения на каждой итерации дают о себе знать.
Всеобщее заблуждение про массивы РНР. Открою небольшой секрет — это вовсе не массивы, в том понимании, как мы понимаем: последовательный набор одинаковых элементов. Это хештаблицы. Отсюда и большинство сюрпризов со скоростями алгоритмов.
Кстати, если не нужна возможность обращение по индексу, то очень хорошо подходит SplMinHeap. В таком случае задача тривиальна
$array->insert($value)
Sign up to leave a comment.
Оптимизация для начинающих, или о пользе профилирования