Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

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

Anna | 29.05.2014 | нет комментариев

Я хотел бы обратить внимание на одну не явственную специфика php.
Возможен у нас есть массив с целочисленными индексами

$arr = array( $val1, $val2, ..., $valn );

Данный массив дозволено перебрать в цикле двумя методами

foreach($arr as $k => $v ) {...}

и

$n = count( $arr );
for($k = 0; $k < $n; $k   ) {...}

Кажется абсолютно явственным, что 2-й метод должен быть, если и не стремительней, то уж верно не неторопливей.
Давайте разберемся.
— Нет. Никаких бенчмарков. Только код! 

На самом деле, 2-й метод работает неторопливей! Исключительно это кажется не явственным для тех, кто имеет навык программирования на 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;

Конструкция HashTable — это и есть сам массив во внутреннем представлении:

typedef struct _hashtable {
	uint nTableSize;
	uint nTableMask;
	uint nNumOfElements;       // число элементов в массиве
	ulong nNextFreeElement;
	Bucket *pInternalPointer;
	Bucket *pListHead;         // Указатель на 1-й элемент массива
	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 до поиска надобного значения.

Итоги

 

foreach($arr as $i => $v ){...}

Довольно стремительно перебирает все элементы массива, получая их один за иным. Трудность этой операции O(n).

for($i = 0; $i < $n; $i   ){...}

На всякой итерации ищет индекс во внутренней хэш таблице.

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

Что касается массивов со строковыми ключами (либо смешанными — целочисленными и строковыми).
Все вышесказанное объективно и для них с той разницей, что скорость доступа к строковому ключу в среднем в 8 (максимум в 16) раз огромнее чем к целочисленному

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB