rotor 17 мар 2014 в 14:35

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

3 мин

31K

PHP *

+22

Комментарии 49

andrew_tch 17 мар 2014 в 14:58

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

barker 17 мар 2014 в 15:35

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

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

NikolasSumrak 18 мар 2014 в 06:36

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

Rhaps107 17 мар 2014 в 16:10

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

rotor 17 мар 2014 в 17:08

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

Rhaps107 17 мар 2014 в 19:30

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

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

Rhaps107 17 мар 2014 в 19:59

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

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

Funcraft 18 мар 2014 в 06:49

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

knagaev 18 мар 2014 в 07:49

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

Zibx 17 мар 2014 в 20:33

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

mayorovp 18 мар 2014 в 15:01

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

webportal 17 мар 2014 в 17:23

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

tenitski 17 мар 2014 в 19:20

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

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

Rhaps107 17 мар 2014 в 19:54

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

webportal 18 мар 2014 в 06:58

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

tenitski 18 мар 2014 в 18:49

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

MuLLtiQ 17 мар 2014 в 17: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 17 мар 2014 в 22: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 17 мар 2014 в 22: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 18 мар 2014 в 20:36

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

MuLLtiQ 18 мар 2014 в 06:05

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

rotor 18 мар 2014 в 22:12

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

MuLLtiQ 19 мар 2014 в 04: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 19 мар 2014 в 05:18

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

hell0w0rd 17 мар 2014 в 18:20

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

rotor 17 мар 2014 в 18:55

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

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

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

hell0w0rd 17 мар 2014 в 19:10

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

mayorovp 17 мар 2014 в 19:59

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

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

rotor 17 мар 2014 в 20:11

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

hell0w0rd 17 мар 2014 в 20:18

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

Sayonji 17 мар 2014 в 23:16

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

MuLLtiQ 17 мар 2014 в 19:44

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

symbix 18 мар 2014 в 00:47

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

НЛО прилетело и опубликовало эту надпись здесь

ainu 18 мар 2014 в 06:04

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

НЛО прилетело и опубликовало эту надпись здесь

rotor 18 мар 2014 в 07:52

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

sectus 18 мар 2014 в 04:49

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

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

НЛО прилетело и опубликовало эту надпись здесь

Blumfontein 18 мар 2014 в 05:21

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

bolk 18 мар 2014 в 05:33

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

Blumfontein 18 мар 2014 в 05:43

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

bolk 18 мар 2014 в 06:45

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

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

Funcraft 18 мар 2014 в 07:01

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

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

Blumfontein 18 мар 2014 в 15:36

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

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

Agel_Nash 18 мар 2014 в 07:23

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

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

sectus 18 мар 2014 в 08:14

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

Agel_Nash 18 мар 2014 в 09:32

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

bolk 18 мар 2014 в 17:21

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий