Сравнение производительности перебора массивов в цикле через for() и foreach()
Кажется вполне очевидным, что второй способ должен быть, если и не быстрее, то уж точно не медленнее.
Давайте разберемся.
— Нет. Никаких бенчмарков. Только код!
На самом деле, второй способ работает медленнее! Особенно это кажется не очевидным для тех, кто имеет опыт программирования на C и C++ , где индекс массива — это простое смещение указателя.
Я обнаружил эту особенность довольно давно, но все ни как не доходили руки посмотреть с чем это связано
Итак, почему так происходит
Давайте посмотрим на внутренне устройство массива в php.
Внутренне, в ядре Zend, массив представлен несколькими взаимосвязанными структурами:
Структура Bucket описывает «указатель» на текущую позицию массива
typedef struct bucket < ulong h; // целочисленное значение индекса // (если индекс целочисленный) uint nKeyLength; // длина строки (строкового ключа) void *pData; // значение элемента массива // [ извлечь можно так: (zval **)pos->pData ] void *pDataPtr; struct bucket *pListNext; // Указатель на следующий элемент массива struct bucket *pListLast; // Указатель на предыдущий элемент массива struct bucket *pNext; // используется для внутренних операций с arBuckets struct bucket *pLast; // используется для внутренних операций с arBuckets const char *arKey; // строковое представление ключа, если ключ строковой > Bucket; typedef Bucket* HashPosition; typedef struct _hashtable < uint nTableSize; uint nTableMask; uint nNumOfElements; // количество элементов в массиве ulong nNextFreeElement; Bucket *pInternalPointer; Bucket *pListHead; // Указатель на первый элемент массива Bucket *pListTail; // Указатель на последний элемент массива Bucket **arBuckets; // собственно, сама ХэшТаблица. // Используется для индексации как строковых // так и целочисленных ключей dtor_func_t pDestructor; zend_bool persistent; unsigned char nApplyCount; zend_bool bApplyProtection; >HashTable; Даже представленной уже информации достаточно, что бы понять причину. Массивы реализованы в виде двусвязных списков.
Двусвязные списки позволяют осуществлять быструю вставку, достаточно быстрый перебор, но произвольный доступ в них — медленная операция.
Давайте посмотрим как, все-таки, Zend осуществляет итерацию элементов массива
// Переход к следующему элементу массива. int zend_hash_move_forward_ex(HashTable *ht, HashPosition *pos) < HashPosition *current = pos ? pos : &ht->pInternalPointer; if (*current) < *current = (*current)->pListNext; return SUCCESS; > else return FAILURE; > // Переход к предыдущему элементу массива. // В php нет обратной итерации, но она поддерживается Zend // и может быть использована при написании расширений. int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos) < HashPosition *current = pos ? pos : &ht->pInternalPointer; if (*current) < *current = (*current)->pListLast; return SUCCESS; > else return FAILURE; > Здесь, я думаю, все понятно без дополнительных объяснений — указатель на текущий элемент заменяется указателем на следующий элемент, ссылка на который хранится в текущем.
Теперь посмотрим как осуществляется доступ по индексу.
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 ( C массив из HashPosition — указателей на Bucket ).
Скажу только, что здесь осуществляется последовательный перебор части внутренней хэш таблицы arBuckets до поиска нужного значения.
Выводы
Достаточно быстро перебирает все элементы массива, получая их один за другим. Сложность этой операции O(n).
На каждой итерации ищет индекс во внутренней хэш таблице.
Оценочно, сложность последней операции выражалась бы суммой арифметической прогрессии n*(n+1)/2 т.е. и имела бы порядок O(n 2 ), если бы при поиске значения по индексу перебиралась бы вся хэш таблица. На самом деле, перебираются не все значения, а только часть их, поэтому сложность будет варьироваться от O(n) до O(n 2 ). И для больших массивов, она будет ближе к, O(n). Но даже в этом случае, перебор массива с доступом по ключу — более ресурсоемкая операция.
Что касается массивов со строковыми ключами (или смешанными — целочисленными и строковыми).
Все вышесказанное справедливо и для них с той разницей, что скорость доступа к строковому ключу в среднем в 8 (максимум в 16) раз больше чем к целочисленному
php, большой массив, как с ним работать?
Есть большой массив, примерно 640.000 строк, если в файле, то 15Мб информации. Как работать с таким массивом не перегружая сервер? В основном надо рандомно выбирать данные из него, порядка 2.000 строк за раз, при этом удаляя то, что было выбрано, т.е. уменьшая сам массив.
Парсинг прайс-листов, наполнение интернет-магазина товаром. (https://humbert.ru) Любая CMS (Битрикс, OpenCart, Prestashop и даже Woo Commerce )
humbert, при всей моей нелюбви, должен сказать, что здесь, как-раз, задача для мускула. Файл перегнать в БД и пользовать. Если есть желание остаться с файлом, то не мудрить, а читать файл построчно, одновременно записывая новый (без удаленных строк). Работать будет чуть медленнее, но зато не перегружая сервак.
От воздержания пока никто не умер. Хотя никто и не родился! Prototype.js был написан теми, кто не знает JavaScript, для тех, кто не знает JavaScript (Richard Cornford)
Проблема в том, что таких массивов может быть и 100 и 1000 P.s. в мускул загонял, вес одного массива 20мб в таблице.
Критичен размер базы? На самом деле есть потеря в дисковом пространстве при размещении подобной информации в базе. Но при работе с массивами вы сталкиваетесь с некоторыми сложностями, а именно: — во первых этой громадиной в памяти работать не совсем удобно. — быстрое удаление из массива в php при таких размерах становится достаточно нетривиальной задачей. Так что смотрите все-таки в сторону БД. Я обрабатываю таблицы с количеством записей в 4-5 млн. (основная операция — выборка случайных строк из таблицы). При желании можно воспользоваться стандартной функцией MySQL — rand (ORDER BY RAND). Ну или по старинке, ручками по id-шникам. Пы.Сы. Текст перемешиваешь , да ? 😉
humbert, я бы прошелся по файлу и «заметил» начала строк и их длину, создал индексный файл, он бы получился под 100кб отсилы я думаю и юзал его для своих задач. открыть файл, оффсетнуть в место и считать пусть даже 5000 байт — милисекунды, при этом не надо насиловать бд, память, проц, файловую систему. по похожему принципу работает моя одна штучка — гео бибилотека, так у нее скорость разрешения страны для IP — 40 000 ip в СЕКУНДУ на моем ноутбуке. ни один мускуль сервер столько не сделает, поверьте 😉 проверял, даже рядом не стоит. когда я ее написал, была самая быстрая библиотека на питоне (или перле, точно не помню), там была скорость 5000 в секунду)
akaplenko:
Так что смотрите все-таки в сторону БД. Я обрабатываю таблицы с количеством записей в 4-5 млн. (основная операция — выборка случайных строк из таблицы). При желании можно воспользоваться стандартной функцией MySQL — rand (ORDER BY RAND).
Очень странно. order by rand() жутко тормозная штука, которая при работе выбирает все записи из таблицы, потом их сортирует и часть (нужную) возвращает. Использовать ее при большом количестве записей это садизм. А Вы при4-5млн записей ее используете?
humbert:
Есть большой массив, примерно 640.000 строк, если в файле, то 15Мб информации.
Как работать с таким массивом не перегружая сервер? В основном надо рандомно выбирать данные из него, порядка 2.000 строк за раз, при этом удаляя то, что было выбрано, т.е. уменьшая сам массив.
1) Если строки ограниченного и небольшого размера, то можно упорядочить структуру, конвертнуть файл в файл со строками одного размера и с ними работать. 2) Загнать все-таки в базу. Неужели так велика разница между 15Мб в файлах и 20Мб в базе? Если еще важна скорость, то memory table могут неслабо помочь. 3) Вариант 2, только в sqllite загнать, что бы с мускулом не городить и с файлами по сути работать. 4) Можно сделать как предложил bearmen, его вариант это по сути создание своей простой БД, единственное преимущество которого в простоте. Но для простоты опять же годится sqllite
Разработка крупных и средних проектов. Можно с криптой. Разумные цены. Хорошее качество. Адекватный подход. Продаем lenovo legion в спб, дешевле магазинов, новые, запечатанные. Есть разные. skype: edogssoft
edogs:
Очень странно. order by rand() жутко тормозная штука, которая при работе выбирает все записи из таблицы, потом их сортирует и часть (нужную) возвращает. Использовать ее при большом количестве записей это садизм. А Вы при4-5млн записей ее используете?
тоже заметил да не стал коментировать) причем сортировка (всегда? вопрос к edogs. я не знаю метода сортировать по рандому без темп тейбла и order by rand(), когда приходится — ухищряюсь через селфжойн айди таблички сортированой, при больших таблицах конечно заметно, но всеже не order * by rand ))) чере темп тейбл
Как работать с большими массивами?
Добрый день, интересует как правильно разбить большой массив на под масивы, или как сделать правильно, скажем формирование файла, на основании одного большого массива который формируется на основании 30 тыс товаров. И из него нужно взять id товара и код. Я использовал цикл foreach но оно занимает большое количество времени. Слышал, что есть такая штука как разбивка массивов на под массивы, что дает возможность уменьшить нагрузку и увеличить производительность. Но как правильно это сделать ?
Простой 6 комментариев
а в чем смысл этого array_chunk? что он даёт для формирования файла?
если разбить большой массив на 1000 маленьких, то скорость работы от этого не изменится, всё равно придется перебрать все 30 тысяч, только не одним циклом, а тысячей.
по-моему вы сейчас выстрелили себе во вторую ногу
обработать 30 тыщ записей — это где-то пол-секунды
если для этого нужен крон — ну ок
но я бы просто повыкидывал весь идиотизм из кода, типа вот этого array_chunk, чтобы он просто стал нормально работать
public function feed()< ini_set('error_reporting', E_ALL); ini_set('display_errors', 1); ini_set('display_startup_errors', 1); // подключаем модель $this->load->model('catalog/product'); // получаем товары с бд $results = $this->model_catalog_product->getProducts(); $file = fopen('csv.csv','w+'); $arr_file = array(); foreach($results as $result) < if($result['quantity'] >0 )< // именно вот тут и была задержка, это формирование юрл на товар, самой системой опенкарт, почему то тут все зависало и не хватало времени на исполнения. //$url = $this->url->link('product/product&product_id='.$result['product_id']); $url = 'https://kancler-gurt.com.ua/index.php?route=product/product&product_id='.$result['product_id']; $arr_file[] = array( 'id' => $result['model'], 'href' => str_replace('&','&',$url), ); > > foreach($arr_file as $arr) < fputcsv($file, $arr, ';','"',' '); >fclose($file); >Если поиск в массиве осуществляется через foreach, то грош цена такому массиву.
Сила массива в том, что доступ к элементу можно осуществлять по индексу, то есть практически моментально. Так что для оптимизации старайтесь делать именно это. То есть обратите внимание на то, какой критерий поиска вы используете, а не что вам нужно извлечь. Ведь при доступе к элементу (который является объектом или структурой), вы и так получите доступ ко всем его свойствам, основное время тратится именно на поиск. Например, если поиск по какому-то уникальному свойству (артикулу, например), то можно сделать ассоциативный массив, ключом которого является именно артикул.
Конечно, на формирование массива тоже тратится время, какой бы оптимизированный поиск ни был. Поэтому супер большие массивы — тоже признак плохой оптимизации. Не зря же придумали базы данных. А что если в базе не 30 тыс. товаров, а миллиард? Тоже загоните их в массив? Надеюсь, что нет, а вместо этого будете пользоваться средствами поиска самой базы данных.
Но если всё же оптимизировать создание массива наравне с последующим поиском по нему, то нужно будет углубиться в суть задачи, а также изучить, какие вообще есть структуры данных в PHP, какие у них плюсы и минусы, как они устроены на низком уровне, и как на их основе сделать более совершенные структуры данных (конкретно для вашей задачи).