Комментарии 43
Проблема здесь в том, что обыкновенных массивов в PHP нет как понятия.
То, что вы там видите как нумерованный массив — на самом деле хранится в памяти в виде
Поэтому любое обращение «по индексу» в общем случае будет обращением по ключу и требует поиска пары ключ-значение в списке.
Насколько я понимаю их текущую реализацию, только при переходе от предыдущего элемента списка к следующему не надо ничего искать(вспоминаем списки из С).
Отсюда почти все «загадочности» с работой массивов в PHP.
И да, PHP — не для обработки больших данных :)
То, что вы там видите как нумерованный массив — на самом деле хранится в памяти в виде
[0=>'z_val',1=>'f_val',2=>'s_val']
, а не ['z_val','f_val','s_val']
Поэтому любое обращение «по индексу» в общем случае будет обращением по ключу и требует поиска пары ключ-значение в списке.
Насколько я понимаю их текущую реализацию, только при переходе от предыдущего элемента списка к следующему не надо ничего искать(вспоминаем списки из С).
Отсюда почти все «загадочности» с работой массивов в PHP.
И да, PHP — не для обработки больших данных :)
+8
На самом деле массив в PHP — это упорядоченное отображение, которое устанавливает соответствие между значением и ключом. Этот тип оптимизирован в нескольких направлениях, поэтому вы можете использовать его как собственно массив, список (вектор), хэш-таблицу (являющуюся реализацией карты), словарь, коллекцию, стэк, очередь и, возможно, что-то еще. Так как значением массива может быть другой массив PHP, можно также создавать деревья и многомерные массивы.
Из их документации
+1
Может возникнуть вопрос:
«А нафига?»
Так вот ответ, имхо, таков:
«Т.к. PHP язык для фронта, Ему зачастую приходится работать с данными со сложной ветвистой изменчивой структурой данных, что довольно удобно делать применяя встроенные функции и встроенный же функционал массивов, которые не совсем массивы.
А вот обработка большущих массивов однотипных данных в вашей страничке из фронта явно говорит о том, что вы что-то делаете не так, поэтому эффективностью такого варианта можно пожертвовать.»
«А нафига?»
Так вот ответ, имхо, таков:
«Т.к. PHP язык для фронта, Ему зачастую приходится работать с данными со сложной ветвистой изменчивой структурой данных, что довольно удобно делать применяя встроенные функции и встроенный же функционал массивов, которые не совсем массивы.
А вот обработка большущих массивов однотипных данных в вашей страничке из фронта явно говорит о том, что вы что-то делаете не так, поэтому эффективностью такого варианта можно пожертвовать.»
+1
Проблема здесь в том, что обыкновенных массивов в PHP нет как понятия.
SplFixedArray? За исключением строгой типизации — классический массив с ОО интерфейсом.
+1
Уже заметно лучше, но все еще не массив значений ) Индексы в нем явно в виде ссылок, иначе вот так
<?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"
нельзя было бы сделать. Ну и речь шла о базовых массивах, а не о надстройках :)0
Ну это скорее уже поведение интерпретатора — он ожидает число в индексе, вот и конвертит автоматом строку в число при получении индекса.
0
нет, речь о том, что в классическом массиве невозможно хранить пременные переменной длины(проивольные строки хранить вообще никак). Только одинаковые блоки ) А в SplArray конвертируется любой php массив, так что это массив ссылок, но не значений.
0
Ну так я сразу же это и написал:
За исключением строгой типизации
0
Но ведь это принципиально разные массивы.
В классическом массиве доступ к произвольному элементу состоит из двух шагов:
1) прибавить к адресу начала масссива индекс * размер элемента(фиксированный)
2) считать данные из этого адреса в памяти
А в ссылочном:
1) прибавить к адресу начала массива адресов элементов индекс * размер ссылки на элемент(фиксированный)
2) считать по этому адресу адрес реального расположения данных
3) считать данные из их реального адреса.
В итоге — в полтора раза больше действий
В классическом массиве доступ к произвольному элементу состоит из двух шагов:
1) прибавить к адресу начала масссива индекс * размер элемента(фиксированный)
2) считать данные из этого адреса в памяти
А в ссылочном:
1) прибавить к адресу начала массива адресов элементов индекс * размер ссылки на элемент(фиксированный)
2) считать по этому адресу адрес реального расположения данных
3) считать данные из их реального адреса.
В итоге — в полтора раза больше действий
-1
Попробую сегодня заменить обычный массив на SplFixedArray. О результата сообщу.
0
Вы смешиваете в одно список и хеш (то что вы представили в коде). Это разные структуры данных. В одной нет доступа по ключу, а другая даже не иметь такого понятия как «следующий элемент».
0
В коде я представил лишь схематичный вариант, чтобы показать что индексы хранятся точно так же как и сами значения.
Вы смешиваете в одно список и хеш.
Как и разработчики PHP, которых я, кстати, процитировал :)
ps минуснул не я
Вы смешиваете в одно список и хеш.
Как и разработчики PHP, которых я, кстати, процитировал :)
ps минуснул не я
0
Не понял, что вы имеете в виду под храняться точно так же.
Надеюсь, что разработчики PHP ничего не путают. Надеюсь, что они все таки понимают, что просто предоставляют структуру с интерфейсом массива и другими интерфейсами и стараются сделать ее удовлетворительно работающей для разных вариантов использования.
Надеюсь, что разработчики PHP ничего не путают. Надеюсь, что они все таки понимают, что просто предоставляют структуру с интерфейсом массива и другими интерфейсами и стараются сделать ее удовлетворительно работающей для разных вариантов использования.
0
Имею в виду то, что классические нативные массивы в РНР не представлены.
И хранится нечто вроде
Поэтому даже если вы объявите массив как набор однотипных значений, цифровой индекс каждого элемента будет храниться в качестве ключа.
И хранится нечто вроде
$array=[];
будет, если совсем упростить, в виде:struct KeyValue{
void* key;
void* value;
KeyValue* prev;
KeyValue* next;
}
struct KeyValue* array;
Поэтому даже если вы объявите массив как набор однотипных значений, цифровой индекс каждого элемента будет храниться в качестве ключа.
0
А вы смешиваете хеш и словарь.
Словарь можно реализовать и на списках.
Словарь можно реализовать и на списках.
0
Хеш или точнее хеш-таблица — это одна из возможных реализаций словаря, она более на слуху, поэтому я использовал ее. Да, словарь можно реализовать на списках, как и любую структуру данных с использованием любой другой. Вопрос будет только в характеристиках такой реализации.
0
Ну вот в PHP массив (которых на самом деле словарь) реализован на списках. Ну это же очевидно, в самом деле :)
0
У вас же функция вставки одинаковая для всех вариантов? Так как же она может влиять на разницу в результатах?
Вообще вот тут 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 проходами по массиву.
Вывод — алгоритмы и профилирование надо знать, но в инструменте тоже разбираться надо.
+3
Протестируйте, пожалуйста, на вашей конфигурации вариант с предварительным поиском позиции (ваши три способа), а затем вставкой с помощью array_splice:
array_splice($array, $position, 0, array($value));
+2
Попробовал заменить функцию вставки на
Так и правда быстрее. Но тем не менее найденный вариант с одним проходом остался лидером, но уже не с таки большим преимуществом.
Ну а статья собственно о том, что не всегда предположения и знания об алгоритмах на практике срабатывают. В данном случае изначально неверным было предположение, что главное найти позицию.
array_splice($array, $position, 0, array($value));
Так и правда быстрее. Но тем не менее найденный вариант с одним проходом остался лидером, но уже не с таки большим преимуществом.
insertBruteForce: 0.0020
insertBinary: 0.0028
insertInterpolation: 0.0027
insertDown: 0.0015
Ну а статья собственно о том, что не всегда предположения и знания об алгоритмах на практике срабатывают. В данном случае изначально неверным было предположение, что главное найти позицию.
0
Полагаю, что массив в 10 000 элементов недостаточно большой, чтобы хорошо увидеть разницу в скорости алгоритмов поиска места для вставки. Думаю, что будь массив на порядок-другой поболее — мы бы увидели более ожидаемые результаты.
0
Пробовал увеличить. Это на 100 тыс.:
Как по мне, результат еще менее ожидаемый.
insertBruteForce: 0.0260
insertBinary: 0.0412
insertInterpolation: 0.0413
insertDown: 0.0218
Как по мне, результат еще менее ожидаемый.
0
Похоже, у вас ошибка в методе insertBruteForce — цикл всегда выходит на первой итерации (при условии, что массив упорядочен по возрастанию). Если поменять "<" на ">" и использовать массив хотя бы на 100 000 записей, то результат уже выправляется.
0
Действительно допустил ошибку. Видимо когда заменял for на foreach. Исправил. Завтра поправлю еще результаты тестов. После исправления результат таков:
Как ни странно, мало что изменилось. Хотя «странность» немного уменьшилась.
insertBruteForce: 0.0369
insertBinary: 0.0427
insertInterpolation: 0.0423
insertDown: 0.0228
Как ни странно, мало что изменилось. Хотя «странность» немного уменьшилась.
0
можете, кстати, для insertBruteForce
поменять на
и удивиться еще раз =)
foreach($array as $position => $test) {
if ($test >= $value) {
поменять на
for($i=0;$i<count($array);$i++) {
if ($test >= $array[$i]) {
и удивиться еще раз =)
0
*конечно же
if($array[$i] >=$value)
0
Я слышал о том, что for работает быстрее, но личные эксперименты в этом примере показали что это не так. При использовании for перебор начинает заметно проигрывать.
0
Рекомендую к ознакомлению вторую главу (Анализ) из книги Problem Solving with Algorithms and Data Structures, перевод которой мелькал на Хабре. В ней доходчиво объясняется понятие сложности алгоритмов. Соответственно перед тем, как сделать для себя открытие о том, что в конкретном языке, конкретная операция над конкретной структурой данных работает не так быстро\медленно как того ожидает разработчик, не мешало бы разузнать как именно реализованы данные операции в конкретном случае.
+2
Сегодня обновлю текст с учетом всех выявленных ошибок, особенностей и новых результатов.
0
А какая скорость если вставить в конец и пересортировать встроенной функцией?
+1
Можете выложить где-нибудь исходники бенчмарка, чтобы другие тоже могли поиграться?
Ещё я не увидел упоминания версии php.
Ещё я не увидел упоминания версии php.
+1
Результаты вполне ожидаемые. На таком большом массиве вставка — самая медленная операция потому, что вы не можете просто «вставить» элемент в массив. Вам сначала нужно «подвинуть вправо на одну позицию» все элементы после индекса куда вы будете вставлять — а это N-index операций. Я тут опускаю, что впринципе и сам массив надо пересоздавать, т.к. изменился его размер — возможно в реализации PHP есть какие-то оптимизации для этого. При этом сам поиск позиции это всего лишь log2(N) операций (т.е. если мы вставляем в середину это 5000 и ~13 операций соответственно на 10к элементах).
Если вам нужна быстрая вставка и упорядоченные данные, то почему не использовать односвязный список? Вы так же перебором будете приходить к месту вставки, но сама вставка будет «бесплатная». Единственное преимущество массива перед другими структурами данных — это бесплатный доступ к элементу по индексу. Если вы не используете это, то я рекомендовал бы вам отказаться от массива в пользу списка.
Если вам нужна быстрая вставка и упорядоченные данные, то почему не использовать односвязный список? Вы так же перебором будете приходить к месту вставки, но сама вставка будет «бесплатная». Единственное преимущество массива перед другими структурами данных — это бесплатный доступ к элементу по индексу. Если вы не используете это, то я рекомендовал бы вам отказаться от массива в пользу списка.
0
На последнем опубликованном варианте есть такой интересный эффект: сначала быстрым алгоритмом найти позицию, а затем перебором выполнить сдвиг, быстрее чем искать нужную позицию во время выполнения сдвига — операции сравнения на каждой итерации дают о себе знать.
0
Всеобщее заблуждение про массивы РНР. Открою небольшой секрет — это вовсе не массивы, в том понимании, как мы понимаем: последовательный набор одинаковых элементов. Это хештаблицы. Отсюда и большинство сюрпризов со скоростями алгоритмов.
0
Кстати, если не нужна возможность обращение по индексу, то очень хорошо подходит SplMinHeap. В таком случае задача тривиальна
$array->insert($value)
а скорость даже не получается замерить.+4
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Оптимизация для начинающих, или о пользе профилирования