rotor Mar 17 2014 at 18:35

Сравнение производительности перебора массивов в цикле через for() и foreach()

3 min

31K

PHP*

+23

Comments 49

andrew_tch Mar 17 2014 at 18:58

fabien.potencier.org/article/8/print-vs-echo-which-one-is-faster простите :)

barker Mar 17 2014 at 19:35

На самом деле, второй способ работает медленнее! Особенно это кажется не очевидным для тех, кто имеет опыт программирования на C и C++, где индекс массива — это простое смещение указателя.

Даже на C и C++ эксперименты с видами цикла (даже не окружающим контекстом и не содержимым!) — это последнее что придёт в голову делать в плане оптимизации по скорости, а на php это вообще смешно.

NikolasSumrak Mar 18 2014 at 10:36

Экономия на спичках.

Rhaps107 Mar 17 2014 at 20:10

Хорошее исследование, но не даёт никакой практической пользы, т.к. время доступа к элементам массива составляет пренебрежимо малый процент от общего времени работы скриптов. Даже если всё переписать в соответствии с вашими наблюдениями, в результате никто ничего не заметит.

rotor Mar 17 2014 at 21:08

Я не предлагаю ничего переписывать. Конечно же, оно того не стоит!
Мне просто показалось любопытной такая особенность php и ей я поделился с сообществом.
Такие вещи лежат в основе хороших практик.
Например выбор двойных или одинарных кавычек для строк в php — еще менее существенная вещь в плане производительности, чем то, о чем я пишу. Однако, использование одинарных кавычек — хорошая практика. Код с foreach часто выглядит элегантнее чем код с for, а если знать что он еще и быстрее, то это ли не повод взять за правило использование foreach как основного способа итерации.

Rhaps107 Mar 17 2014 at 23:30

Если оно несущественно, в чем смысл заострять на нём внимание? :)
Вы правы, выбор кавычек и for vs foreach в PHP после версии 3, если не ошибаюсь, не оказывают никакого влияния на производительность и темы исчерпали себя многократно много лет назад.

Полезнее темы в исходниках можно найти от обратного — от проблемы, а уже видя проблему, смотреть в исходники. Я так например в soap баги находил.

Rhaps107 Mar 17 2014 at 23:59

> Код с foreach часто выглядит элегантнее чем код с for, а если знать что он еще и быстрее, то это ли не повод взять за правило использование foreach как основного способа итерации.

Выше описал, что «быстрее» оно только в специально подготовленной пробирке, да и то на громадных массивах и всё равно несущественное.
Так что рекомендовать что-то из for или foreach из соображений скорости — как-то не совсем оправдано.
Рекомендовать эти конструкции с современным движком PHP можно только из соображений удобства использования.
foreach — краткий синтаксис для перебора всех ключей со значениями; for — более длинный синтаксис, но можно использовать его не только для перебора. Смотря какую операцию хотите сделать. Перебрать — foreach. Сделать более хитрый цикл, нежели перебор — тогда for для вас. Вот всё, что сейчас можно порекомендовать.

Funcraft Mar 18 2014 at 10:49

Извините, что-то не уловил, какие средства может предоставить for для «большей хитрости», которые не может предоставить foreach?

knagaev Mar 18 2014 at 11:49

Да хотя бы просто пройти только по четным индексам, или по каждому десятому, или по числам Фибоначчи.
Или сделать бесконечный цикл.
Или выйти из цикла при нарушении инварианта более хитрого, чем «не конец контейнера».
И т.д. и т.п.

Zibx Mar 18 2014 at 00:33

Это тот самый случай, когда различие важно. Сложность алгоритмов — это такой интересный зверь, который любит выплывать на повторении операций. И если мы гипотетически решим перебрать трёхмерный массив, то тут он и вылезет в полной красе. В случае O(n) это будет O(n³), а в случае O(n²) — O(n⁶). В случае перебора элементов куба 20х20х20 — это соответственно 8к операций против 64кк операций. И это при том, что пхп ещё и сам по себе — весьма медленный язык.

mayorovp Mar 18 2014 at 19:01

Оба способа дают O(n), где вы квадрат нашли? Ниже в комментариях уже объяснили, почему никакого квадрата тут нет.

webportal Mar 17 2014 at 21:23

Можно ещё ускорить и сократить потребление памяти перебирая так: foreach($arr as $k => &$v ) {...} И лучше заметна разница на больших массивах…

tenitski Mar 17 2014 at 23:20

Какие ваши доказательства? PHP при присваивании создает ссылку на значение и только клонирует данные, если значение меняется. Т.е. так, например, можно передавать в фунцию хоть сколько угодно большие массивы и не думать о памяти (но только до тех пор пока мы в функции не начнем менять данные внутри этого массива).

Подозреваю, что ($arr as $k => &$v ) только добавит оверхеада.

Rhaps107 Mar 17 2014 at 23:54

Вы правы, синтаксис foreach со ссылкой — это ещё одно наследие версий PHP, передававшееся от деда к внуку, и оно давно неактуально. Zend Engine постоянно оптимизируется и синтаксис без ссылки на сколько я помню где-то в четвертых версиях PHP не даёт скорости.

webportal Mar 18 2014 at 10:58

А вы попробуйте потестить… И статейку почитайте habrahabr.ru/post/134784/

tenitski Mar 18 2014 at 22:49

Потестил и оказалось, что для массивов так и есть (изза создания копии массива). Может когда-нибудь пригодится

MuLLtiQ Mar 17 2014 at 21:29

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).

youROCK Mar 18 2014 at 02:01

Мне всегда казалось, что for() медленней foreach() просто потому, что при for() делается больше операций на стороне PHP — для foreach делается лишь привязка переменных (будем считать это одной базовой операцией для PHP), а при for, как правило, 3 операции — это $i++, сравнение $i с N, и присвоение значения массива какой-нибудь переменной:

<?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)

Что лишь доказывает, что пользы от авторского топика никакой :))

youROCK Mar 18 2014 at 02:23

Продолжая идиотские изыскания, выходит, что я всё же немного был не прав по поводу того, что привязка переменной в foreach дается абсолютно бесплатно:

<?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 опкодов, а не на саму итерацию по массиву.

webportal Mar 19 2014 at 00:36

Я тут выше отвечал про foreach habrahabr.ru/post/216103/#comment_7412331

MuLLtiQ Mar 18 2014 at 10:05

Тут вопрос не в обвязке этих операций, а в алгоритмической сложности. Автор топика утверждает что сложность выборки из хэш-таблицы — O(n) что есть неправда.

rotor Mar 19 2014 at 02:12

Так. Давайте мою цитату, где я такое сказал.
Сложность перебора N элементов не может быть меньше O(N), а больше может. Про сложность выборки из хеш-таблицы я конкретно не говорил. Сказал про сложность выборки строковых ключей (последний абзац). целочисленный ключ может быть извлечен как за одну операцию, так и за несколько.

MuLLtiQ Mar 19 2014 at 08:58

Я конкретно вот про эту цитату:

for($i = 0; $i < $n; $i++ ){...}
На каждой итерации ищет индекс во внутренней хэш таблице.

Оценочно, сложность последней операции выражалась бы суммой арифметической прогрессии n*(n+1)/2 т.е. и имела бы порядок O(n2), если бы при поиске значения по индексу перебиралась бы вся хэш таблица. На самом деле, перебираются не все значения, а только часть их, поэтому сложность будет варьироваться от O(n) до O(n2). И для больших массивов, она будет ближе к, O(n). Но даже в этом случае, перебор массива с доступом по ключу — более ресурсоемкая операция.

На самом деле сложность тут будет O(n), а не O(n²) во всех случаях, потому что вряд ли разработчики PHP забили на качество хэширования и обычные числовые индексы имеют весьма слабую вероятность попасть в один bucket.
Ну т.е. не будет перебора даже части значений, потому что в bucket-е будет ровно один элемент. В этом и смысл хэш-таблицы.

sectus Mar 19 2014 at 09:18

Чтобы не повторяться, то дам ссылку на комментарий со ссылкой: habrahabr.ru/post/216103/#comment_7412085

hell0w0rd Mar 17 2014 at 22:20

Ну так такие исследования надо начинать с того, что в php ЛЮБОЙ массив — хеш-таблица. А значит код с for и $i каждый раз означает получение элемента по этому самому $i, то есть дополнительное вычисление хеша, в то время как foreach это как раз перебор по всей хеш-таблице.

rotor Mar 17 2014 at 22:55

Это никакое не исследование :) вы преувеличиваете статус моей заметки.

в php ЛЮБОЙ массив — хеш-таблица

Совершенно верно. Об этом и речь. Еще и двусвязный список. Я например не знал, что там внутри двусвязный список. И мне кажется это совсем не очевидно.

hell0w0rd Mar 17 2014 at 23:10

оО. Вы хотите сказать, что хеш-таблица двусвязный список? Может вы имеете ввиду разрешение коллизий?
Если второе — то это метод цепочек, второй вариант того же метода цепочек — бинарные деревья, но я не думаю что это дало бы прирост производительности большой

mayorovp Mar 17 2014 at 23:59

Нет, он хочет сказать, что используется специальная модификация хеш-таблицы — прошитая хеш-таблица.

В Java она называется LinkedHashMap

rotor Mar 18 2014 at 00:11

Я ничего такого не говорил. Где вы такое увидели?
К вашему замечанию о том что php-массив является хэш таблицей, что действительно очевидно, я добавил уточнение, что помимо хэш таблицы там есть еще и двусвязный список.
Хранение массивов могло быть реализовано разными способами. Сама хеш таблица могла быть реализована разными способами.
Смысл поста не в том какие бывают хеш таблицы и как в них разрешаются коллизии, а в том как конкретно в php реализован массив.
Я думаю людям, практикующим программирование на php эта информация уж точно не повредит.

hell0w0rd Mar 18 2014 at 00:18

Я не пытался на вас наехать.
Просто я не знал о том, что хеш-таблицы реализуются через связные списки. Для меня смысл хеш-таблицы представляется в O(1) для вставки и получении элемента, за счет смещения по обычному массиву, а связные списки никак в это понятние не вписываются.
Помимо понимания что внутри массивов — хеш-таблица хорошо бы также понимать что за хеш таблица

Sayonji Mar 18 2014 at 03:16

Она, по-видимому, и не реализовывается через них. Это обычная хеш таблица, в которой вместе со значением еще хранится указатель на предыдущий положенный элемент, и на следующий. Специально для того, чтобы итерироваться, ибо в обычной хеш-таблице это невозможно.

MuLLtiQ Mar 17 2014 at 23:44

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

symbix Mar 18 2014 at 04:47

Для более глубокого понимания внутреннего устройства массивов в php советую статью Никиты Попова: Understanding PHP's internal array implementation.

UFO just landed and posted this here

ainu Mar 18 2014 at 10:04

Нет, это более крутой Попов.

UFO just landed and posted this here

rotor Mar 18 2014 at 11:52

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

sectus Mar 18 2014 at 08:49

И для больших массивов, она будет ближе к, O(n)

Дело не в величине массива, а в том сколько будет совпадающих хэшей в хэштаблице: Supercolliding a PHP array

UFO just landed and posted this here

Blumfontein Mar 18 2014 at 09:21

Да кто этим for-ом вообще пользуется?

bolk Mar 18 2014 at 09:33

А чего бы им не пользоваться-то?

Blumfontein Mar 18 2014 at 09:43

Заглянул в свой последний немаленький проект и не нашел сходу ни одного for-а. Удел for-а — повторить некоторую операцию некоторое ограниченное число раз, т.е. те случаи, когда итерируемая переменная слабо связана с содержимым цикла. Такое редко надо. Использовать for для прохода по массиву странно.

bolk Mar 18 2014 at 10:45

Редко и странно, ага.

for ($i = 0; $i<$len; $i+=2) {
    for ($j = $len - 1; $j >=0; $j--) {
        for ($k = $j; $k >=0; $k--) {
             // это всё вы тоже форичем делаете?
       }
    }
}

Funcraft Mar 18 2014 at 11:01

Насколько я понял вашего собеседника, ваш пример не о том.
Blumfontein как будто бы говорит о том, что for используется в основном в отрыве от перебираемого массива, т.е. когда не важны ключи, а foreach — наоборот, когда это важно.

Т.е. обратите внимание, что в вашем примере все индексы числовые — таким образом, ими можно манипулировать, не учитывая их смысл/значение.

Blumfontein Mar 18 2014 at 19:36

/*
* это всё вы тоже форичем делаете?
*/

Нет. Я это всё ничем не делаю. У меня таких случаев не бывает.

Agel_Nash Mar 18 2014 at 11:23

Вариант с for можно использовать только в том случае, если действительно все ключи массива $arr расположены в порядке возрастания без пропусков. И об этом не стоит забывать…

$arr = [0 => 'a', 1 => 'b', 3 => 'c'];
$n = count( $arr );
for($k = 0; $k < $n; $k++ ) {...}

sectus Mar 18 2014 at 12:14

Цикл for можно использовать гораздо шире. Даже относительно массивов. И в вашем примере тоже его тоже можно применить, если потребуется.

Agel_Nash Mar 18 2014 at 13:32

Конечно можно — допустим определить «есть ли дырки». Но в данном случае речь идет о банальном переборе всех элементов массива, а не каких-либо других экзотических обработках массивов.

bolk Mar 18 2014 at 21:21

Надеюсь все тут понимают, что for и foreach совсем разные вещи? for перебирает в порядке следования индексов, foreach — в порядке следования значений. Массив [ 1=>1, 0=>0 ] эти циклы переберут по-разному.