Какова временная сложность получения элемента в массиве в PHP?

Question

Я мало представляю, как массивы реализованы в PHP, и знаю, что для большинства языков ООП сложность заключается в постоянном времени, O (1), для массива предопределенного типа. Так в чем же дело в PHP с его динамической типизацией, расширением массивов и т. Д .?

Answer 1

Глядя на array.c в исходном коде PHP показывает, что они реализованы в виде хеш-таблиц, что обычно означает O (1) (на самом деле это O (N), если вы очень строгие, но может быть так же плох, как O (log N)) для поиска элемента.

Если вы сомневаетесь, вы всегда можете измерить, хотя. Создайте массив из 10, 100, 1000, 10000, 100000, 1000000 и т. Д. Элементов и измерьте производительность, экстраполируйте данные на функцию, и вы получите средние характеристики производительности.