Комментарии 49
На самом деле, второй способ работает медленнее! Особенно это кажется не очевидным для тех, кто имеет опыт программирования на C и C++, где индекс массива — это простое смещение указателя.Даже на C и C++ эксперименты с видами цикла (даже не окружающим контекстом и не содержимым!) — это последнее что придёт в голову делать в плане оптимизации по скорости, а на php это вообще смешно.
+11
Хорошее исследование, но не даёт никакой практической пользы, т.к. время доступа к элементам массива составляет пренебрежимо малый процент от общего времени работы скриптов. Даже если всё переписать в соответствии с вашими наблюдениями, в результате никто ничего не заметит.
0
Я не предлагаю ничего переписывать. Конечно же, оно того не стоит!
Мне просто показалось любопытной такая особенность php и ей я поделился с сообществом.
Такие вещи лежат в основе хороших практик.
Например выбор двойных или одинарных кавычек для строк в php — еще менее существенная вещь в плане производительности, чем то, о чем я пишу. Однако, использование одинарных кавычек — хорошая практика. Код с
Мне просто показалось любопытной такая особенность php и ей я поделился с сообществом.
Такие вещи лежат в основе хороших практик.
Например выбор двойных или одинарных кавычек для строк в php — еще менее существенная вещь в плане производительности, чем то, о чем я пишу. Однако, использование одинарных кавычек — хорошая практика. Код с
foreach
часто выглядит элегантнее чем код с for
, а если знать что он еще и быстрее, то это ли не повод взять за правило использование foreach
как основного способа итерации.+20
Если оно несущественно, в чем смысл заострять на нём внимание? :)
Вы правы, выбор кавычек и for vs foreach в PHP после версии 3, если не ошибаюсь, не оказывают никакого влияния на производительность и темы исчерпали себя многократно много лет назад.
Полезнее темы в исходниках можно найти от обратного — от проблемы, а уже видя проблему, смотреть в исходники. Я так например в soap баги находил.
Вы правы, выбор кавычек и for vs foreach в PHP после версии 3, если не ошибаюсь, не оказывают никакого влияния на производительность и темы исчерпали себя многократно много лет назад.
Полезнее темы в исходниках можно найти от обратного — от проблемы, а уже видя проблему, смотреть в исходники. Я так например в soap баги находил.
0
> Код с foreach часто выглядит элегантнее чем код с for, а если знать что он еще и быстрее, то это ли не повод взять за правило использование foreach как основного способа итерации.
Выше описал, что «быстрее» оно только в специально подготовленной пробирке, да и то на громадных массивах и всё равно несущественное.
Так что рекомендовать что-то из for или foreach из соображений скорости — как-то не совсем оправдано.
Рекомендовать эти конструкции с современным движком PHP можно только из соображений удобства использования.
foreach — краткий синтаксис для перебора всех ключей со значениями; for — более длинный синтаксис, но можно использовать его не только для перебора. Смотря какую операцию хотите сделать. Перебрать — foreach. Сделать более хитрый цикл, нежели перебор — тогда for для вас. Вот всё, что сейчас можно порекомендовать.
Выше описал, что «быстрее» оно только в специально подготовленной пробирке, да и то на громадных массивах и всё равно несущественное.
Так что рекомендовать что-то из for или foreach из соображений скорости — как-то не совсем оправдано.
Рекомендовать эти конструкции с современным движком PHP можно только из соображений удобства использования.
foreach — краткий синтаксис для перебора всех ключей со значениями; for — более длинный синтаксис, но можно использовать его не только для перебора. Смотря какую операцию хотите сделать. Перебрать — foreach. Сделать более хитрый цикл, нежели перебор — тогда for для вас. Вот всё, что сейчас можно порекомендовать.
+3
Извините, что-то не уловил, какие средства может предоставить for для «большей хитрости», которые не может предоставить foreach?
0
Это тот самый случай, когда различие важно. Сложность алгоритмов — это такой интересный зверь, который любит выплывать на повторении операций. И если мы гипотетически решим перебрать трёхмерный массив, то тут он и вылезет в полной красе. В случае O(n) это будет O(n3), а в случае O(n2) — O(n6). В случае перебора элементов куба 20х20х20 — это соответственно 8к операций против 64кк операций. И это при том, что пхп ещё и сам по себе — весьма медленный язык.
+1
Можно ещё ускорить и сократить потребление памяти перебирая так: foreach($arr as $k => &$v ) {...} И лучше заметна разница на больших массивах…
+1
Какие ваши доказательства? PHP при присваивании создает ссылку на значение и только клонирует данные, если значение меняется. Т.е. так, например, можно передавать в фунцию хоть сколько угодно большие массивы и не думать о памяти (но только до тех пор пока мы в функции не начнем менять данные внутри этого массива).
Подозреваю, что ($arr as $k => &$v ) только добавит оверхеада.
Подозреваю, что ($arr as $k => &$v ) только добавит оверхеада.
+2
Вы правы, синтаксис foreach со ссылкой — это ещё одно наследие версий PHP, передававшееся от деда к внуку, и оно давно неактуально. Zend Engine постоянно оптимизируется и синтаксис без ссылки на сколько я помню где-то в четвертых версиях PHP не даёт скорости.
+1
А вы попробуйте потестить… И статейку почитайте habrahabr.ru/post/134784/
0
int zend_hash_index_find(const HashTable *ht, ulong h, void **pData)
{
uint nIndex;
Bucket *p;
nIndex = h & ht->nTableMask;
p = ht->arBuckets[nIndex];
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == 0)) {
*pData = p->pData;
return SUCCESS;
}
p = p->pNext;
}
return FAILURE;
}
Вот это вообще похоже на выборку из самой обычной-преобычной хэш-таблицы. Если это так, то в arBuckets хранится в среднем 1 элемент, и итоговая сложность выборки одного элемента по индексу — константная — O(1).
+3
Мне всегда казалось, что for() медленней foreach() просто потому, что при for() делается больше операций на стороне PHP — для foreach делается лишь привязка переменных (будем считать это одной базовой операцией для PHP), а при for, как правило, 3 операции — это $i++, сравнение $i с N, и присвоение значения массива какой-нибудь переменной:
Если всё же запустить бенчмарк, то получим следующие цифры на цикле без тела:
Добавив какую-нибудь полезную нагрузку (например, подсчёт $sum += $arr[$i] или $sum += $v в случае foreach), for вообще иногда выигрывает :)
Что лишь доказывает, что пользы от авторского топика никакой :))
<?php
$arr = range(0, 500000);
foreach ($arr as $i => $v);
$cnt = count($arr);
for ($i = 0; $i < $cnt; $i++) $v = $arr[$i];
Если всё же запустить бенчмарк, то получим следующие цифры на цикле без тела:
$ php --version
PHP 5.4.24 (cli) (built: Jan 19 2014 21:32:15)
Copyright (c) 1997-2013 The PHP Group
Zend Engine v2.4.0, Copyright (c) 1998-2013 Zend Technologies
$ php test.php
Foreach: 0.021 sec
For: 0.026 sec
Добавив какую-нибудь полезную нагрузку (например, подсчёт $sum += $arr[$i] или $sum += $v в случае foreach), for вообще иногда выигрывает :)
$ php test2.php
Foreach: 0.029 sec (sum=125000250000)
For: 0.027 sec (sum=125000250000)
Что лишь доказывает, что пользы от авторского топика никакой :))
+1
Продолжая идиотские изыскания, выходит, что я всё же немного был не прав по поводу того, что привязка переменной в foreach дается абсолютно бесплатно:
Вот какие результаты получаются:
Какой-то колоссальной разницы нет между этими вариантами, кроме array_sum, пожалуй :). Кажется, array_sum выигрывает за счёт того, что оббегает весь массив, но при этом не делает привязку переменных и прочей ерунды, и различия в способе хранения тут особо не при чём — основное время очевидно тратится на исполнение простейших PHP опкодов, а не на саму итерацию по массиву.
<?php
$arr = range(0, 500000);
$max = count($arr);
$sum = 0;
$start = microtime(true);
for($i = 0; $i < $max; $i++) $sum += $arr[$i];
echo "For took " . round(microtime(true) - $start, 3) . " sec\n";
$start = microtime(true);
foreach($arr as $i => $v) $sum += $v;
echo "Foreach_iv took " . round(microtime(true) - $start, 3) . " sec\n";
$start = microtime(true);
foreach($arr as $v) $sum += $v;
echo "Foreach_v took " . round(microtime(true) - $start, 3) . " sec\n";
$start = microtime(true);
$sum = array_sum($arr);
echo "Arrsum took " . round(microtime(true) - $start, 3) . " sec\n";
Вот какие результаты получаются:
$ php test.php
For took 0.028 sec
Foreach_iv took 0.026 sec
Foreach_v took 0.023 sec
Arrsum took 0.008 sec
Какой-то колоссальной разницы нет между этими вариантами, кроме array_sum, пожалуй :). Кажется, array_sum выигрывает за счёт того, что оббегает весь массив, но при этом не делает привязку переменных и прочей ерунды, и различия в способе хранения тут особо не при чём — основное время очевидно тратится на исполнение простейших PHP опкодов, а не на саму итерацию по массиву.
0
Я тут выше отвечал про foreach habrahabr.ru/post/216103/#comment_7412331
+1
Тут вопрос не в обвязке этих операций, а в алгоритмической сложности. Автор топика утверждает что сложность выборки из хэш-таблицы — O(n) что есть неправда.
0
Так. Давайте мою цитату, где я такое сказал.
Сложность перебора N элементов не может быть меньше O(N), а больше может. Про сложность выборки из хеш-таблицы я конкретно не говорил. Сказал про сложность выборки строковых ключей (последний абзац). целочисленный ключ может быть извлечен как за одну операцию, так и за несколько.
Сложность перебора N элементов не может быть меньше O(N), а больше может. Про сложность выборки из хеш-таблицы я конкретно не говорил. Сказал про сложность выборки строковых ключей (последний абзац). целочисленный ключ может быть извлечен как за одну операцию, так и за несколько.
0
Я конкретно вот про эту цитату:
На самом деле сложность тут будет O(n), а не O(n2) во всех случаях, потому что вряд ли разработчики PHP забили на качество хэширования и обычные числовые индексы имеют весьма слабую вероятность попасть в один bucket.
Ну т.е. не будет перебора даже части значений, потому что в bucket-е будет ровно один элемент. В этом и смысл хэш-таблицы.
for($i = 0; $i < $n; $i++ ){...}
На каждой итерации ищет индекс во внутренней хэш таблице.
Оценочно, сложность последней операции выражалась бы суммой арифметической прогрессии n*(n+1)/2 т.е. и имела бы порядок O(n2), если бы при поиске значения по индексу перебиралась бы вся хэш таблица. На самом деле, перебираются не все значения, а только часть их, поэтому сложность будет варьироваться от O(n) до O(n2). И для больших массивов, она будет ближе к, O(n). Но даже в этом случае, перебор массива с доступом по ключу — более ресурсоемкая операция.
На самом деле сложность тут будет O(n), а не O(n2) во всех случаях, потому что вряд ли разработчики PHP забили на качество хэширования и обычные числовые индексы имеют весьма слабую вероятность попасть в один bucket.
Ну т.е. не будет перебора даже части значений, потому что в bucket-е будет ровно один элемент. В этом и смысл хэш-таблицы.
0
Чтобы не повторяться, то дам ссылку на комментарий со ссылкой: habrahabr.ru/post/216103/#comment_7412085
+1
Ну так такие исследования надо начинать с того, что в php ЛЮБОЙ массив — хеш-таблица. А значит код с for и $i каждый раз означает получение элемента по этому самому $i, то есть дополнительное вычисление хеша, в то время как foreach это как раз перебор по всей хеш-таблице.
+1
Это никакое не исследование :) вы преувеличиваете статус моей заметки.
в php ЛЮБОЙ массив — хеш-таблицаСовершенно верно. Об этом и речь. Еще и двусвязный список. Я например не знал, что там внутри двусвязный список. И мне кажется это совсем не очевидно.
0
оО. Вы хотите сказать, что хеш-таблица двусвязный список? Может вы имеете ввиду разрешение коллизий?
Если второе — то это метод цепочек, второй вариант того же метода цепочек — бинарные деревья, но я не думаю что это дало бы прирост производительности большой
Если второе — то это метод цепочек, второй вариант того же метода цепочек — бинарные деревья, но я не думаю что это дало бы прирост производительности большой
0
Нет, он хочет сказать, что используется специальная модификация хеш-таблицы — прошитая хеш-таблица.
В Java она называется LinkedHashMap
В Java она называется LinkedHashMap
+1
Я ничего такого не говорил. Где вы такое увидели?
К вашему замечанию о том что php-массив является хэш таблицей, что действительно очевидно, я добавил уточнение, что помимо хэш таблицы там есть еще и двусвязный список.
Хранение массивов могло быть реализовано разными способами. Сама хеш таблица могла быть реализована разными способами.
Смысл поста не в том какие бывают хеш таблицы и как в них разрешаются коллизии, а в том как конкретно в php реализован массив.
Я думаю людям, практикующим программирование на php эта информация уж точно не повредит.
К вашему замечанию о том что php-массив является хэш таблицей, что действительно очевидно, я добавил уточнение, что помимо хэш таблицы там есть еще и двусвязный список.
Хранение массивов могло быть реализовано разными способами. Сама хеш таблица могла быть реализована разными способами.
Смысл поста не в том какие бывают хеш таблицы и как в них разрешаются коллизии, а в том как конкретно в php реализован массив.
Я думаю людям, практикующим программирование на php эта информация уж точно не повредит.
0
Я не пытался на вас наехать.
Просто я не знал о том, что хеш-таблицы реализуются через связные списки. Для меня смысл хеш-таблицы представляется в O(1) для вставки и получении элемента, за счет смещения по обычному массиву, а связные списки никак в это понятние не вписываются.
Помимо понимания что внутри массивов — хеш-таблица хорошо бы также понимать что за хеш таблица
Просто я не знал о том, что хеш-таблицы реализуются через связные списки. Для меня смысл хеш-таблицы представляется в O(1) для вставки и получении элемента, за счет смещения по обычному массиву, а связные списки никак в это понятние не вписываются.
Помимо понимания что внутри массивов — хеш-таблица хорошо бы также понимать что за хеш таблица
0
Для более глубокого понимания внутреннего устройства массивов в php советую статью Никиты Попова: Understanding PHP's internal array implementation.
+3
И для больших массивов, она будет ближе к, O(n)
Дело не в величине массива, а в том сколько будет совпадающих хэшей в хэштаблице: Supercolliding a PHP array
+2
НЛО прилетело и опубликовало эту надпись здесь
Да кто этим for-ом вообще пользуется?
0
А чего бы им не пользоваться-то?
0
Заглянул в свой последний немаленький проект и не нашел сходу ни одного for-а. Удел for-а — повторить некоторую операцию некоторое ограниченное число раз, т.е. те случаи, когда итерируемая переменная слабо связана с содержимым цикла. Такое редко надо. Использовать for для прохода по массиву странно.
0
Редко и странно, ага.
for ($i = 0; $i<$len; $i+=2) {
for ($j = $len - 1; $j >=0; $j--) {
for ($k = $j; $k >=0; $k--) {
// это всё вы тоже форичем делаете?
}
}
}
0
Насколько я понял вашего собеседника, ваш пример не о том.
Blumfontein как будто бы говорит о том, что for используется в основном в отрыве от перебираемого массива, т.е. когда не важны ключи, а foreach — наоборот, когда это важно.
Т.е. обратите внимание, что в вашем примере все индексы числовые — таким образом, ими можно манипулировать, не учитывая их смысл/значение.
Blumfontein как будто бы говорит о том, что for используется в основном в отрыве от перебираемого массива, т.е. когда не важны ключи, а foreach — наоборот, когда это важно.
Т.е. обратите внимание, что в вашем примере все индексы числовые — таким образом, ими можно манипулировать, не учитывая их смысл/значение.
0
/*
* это всё вы тоже форичем делаете?
*/
Нет. Я это всё ничем не делаю. У меня таких случаев не бывает.
* это всё вы тоже форичем делаете?
*/
Нет. Я это всё ничем не делаю. У меня таких случаев не бывает.
0
Вариант с for можно использовать только в том случае, если действительно все ключи массива $arr расположены в порядке возрастания без пропусков. И об этом не стоит забывать…
$arr = [0 => 'a', 1 => 'b', 3 => 'c'];
$n = count( $arr );
for($k = 0; $k < $n; $k++ ) {...}
0
Цикл for можно использовать гораздо шире. Даже относительно массивов. И в вашем примере тоже его тоже можно применить, если потребуется.
0
Надеюсь все тут понимают, что for и foreach совсем разные вещи? for перебирает в порядке следования индексов, foreach — в порядке следования значений. Массив [ 1=>1, 0=>0 ] эти циклы переберут по-разному.
+5
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Сравнение производительности перебора массивов в цикле через for() и foreach()