Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 36
И что там за алгоритм у этого array_search?
Мне это самому интересно, но где такую информацию можно найти - не знаю.
Думаю, он просто использует внутреннее представление массивов в PHP. Точно как там это все хранится я не знаю, но сильно подозреваю, что в виде какого-нибудь дерева или хэш-таблицы. Отсюда и разница в скорости с тупым перебором в несколько порядков.
Где-то встречал описание внутренней структуры массивов в PHP, сечас, к сожалению, не могу найти, потому не гарантирую точность. Внутренняя структура массива включает в себя хештаблицу для поиска по ключу, двусвязный список для обхода элементов, плюс служебные поля, например, кол-во элементов, следующий числовой индекс, ссылка на текущий элемент...
В результатах ничего удивительного нет:
1. Бинарный код всегда будет работать быстрее. Внутри, я думаю, простой перебор, т.к. о данных ничего не известно, в пользу этого говорит и то, что при наличии нескольких значений, равных искомому, возвращается ключ первого элемента.
2. При наличии break - то же самое, что и в первом случае, но на PHP... естественно медленнее.
3. Еще хуже. for/while не лучшее решение для перебора элементов массива, т.к. на каждой итерации выполняется поиск в хештаблице. foreach для этого предпочтительней, ибо просто перебирает элементы списка.
В результатах ничего удивительного нет:
1. Бинарный код всегда будет работать быстрее. Внутри, я думаю, простой перебор, т.к. о данных ничего не известно, в пользу этого говорит и то, что при наличии нескольких значений, равных искомому, возвращается ключ первого элемента.
2. При наличии break - то же самое, что и в первом случае, но на PHP... естественно медленнее.
3. Еще хуже. for/while не лучшее решение для перебора элементов массива, т.к. на каждой итерации выполняется поиск в хештаблице. foreach для этого предпочтительней, ибо просто перебирает элементы списка.
Вы не поверите, но там while!
[...]
while (zend_hash_get_current_data_ex(target_hash, (void **)&entry, &pos) == SUCCESS) {
is_equal_func(&res, *value, *entry TSRMLS_CC);
[...]
а вообще это можно посмотреть в исходники php ext/standart/array.c
[...]
while (zend_hash_get_current_data_ex(target_hash, (void **)&entry, &pos) == SUCCESS) {
is_equal_func(&res, *value, *entry TSRMLS_CC);
[...]
а вообще это можно посмотреть в исходники php ext/standart/array.c
думаю, когда элемент найден, вызывается break или return (что там в пхп прерывает циклы?).
Поэтому, если в циклах while & for сделать тот же break, результаты отличаться не будут (проверять не стал. не знаю пхп). Судя по результатам, так оно и есть: массив увеличился на порядок - циклы стали работать дольше на порядок. В то время, как этот аррай_серч по времени почти отрабатывает столько же.
Поэтому, если в циклах while & for сделать тот же break, результаты отличаться не будут (проверять не стал. не знаю пхп). Судя по результатам, так оно и есть: массив увеличился на порядок - циклы стали работать дольше на порядок. В то время, как этот аррай_серч по времени почти отрабатывает столько же.
Вы break не делали.. чего вы ожидали он же всего лишь 277 получался.
А foreach и while о всему массиву шарились
А foreach и while о всему массиву шарились
нет уж, давайте всё-таки вернёмся к "программистскому складу ума"...
данная задача — "состоит ли элемент в массиве данных" — решится значительно быстрее, если данные изначально организовывать по-другому: for($i=0; $i < $mass; $i++) $test_array[$i] = true;
в таком случае время поиска элемента — isset($test_array[$i]) — Вас приятно удивит.
если работать не с целыми числами, а строками, то, предполагаю, такой поиск удивит Вас ещё сильнее и приятнее. =)
данная задача — "состоит ли элемент в массиве данных" — решится значительно быстрее, если данные изначально организовывать по-другому: for($i=0; $i < $mass; $i++) $test_array[$i] = true;
в таком случае время поиска элемента — isset($test_array[$i]) — Вас приятно удивит.
если работать не с целыми числами, а строками, то, предполагаю, такой поиск удивит Вас ещё сильнее и приятнее. =)
Поиск по индексу конечно работает несравнимо быстрее ( даже для интересу сравнил - очень быстро :)) Но здесь все-таки тестовая задача, а в реальном скрипте это не всегда удобно. Хотя где возможно тоже можно применять, согласен.
Давайте вернёмся.
Что быстрей, для каждого чиха изобретать и отлаживать свой велосипед (не о конкретном случае, а вообще), да ещё следить, чтобы он получался высокопроизводительным, безглючным, безопасным, - или пользоваться уже готовыми велосипедами, зная об их существовании?
Что быстрей, для каждого чиха изобретать и отлаживать свой велосипед (не о конкретном случае, а вообще), да ещё следить, чтобы он получался высокопроизводительным, безглючным, безопасным, - или пользоваться уже готовыми велосипедами, зная об их существовании?
чтобы у кого-то всегда были под рукой готовые велосипеды, их должен кто-то изобретать, неправда ли?
ну, и что для одного является "изобретением целого велосипеда", для другого — ясное и очевидное решение.
ну, и что для одного является "изобретением целого велосипеда", для другого — ясное и очевидное решение.
Мне это напоминает о спорах любителей использовать готовые фреймворки (cms, либы и так далее) и любителей писать свои.
Не спорю, в процессе обучения можно и нужно писать своё. Для души можно. Можно даже потом выложить opensource.
А когда есть сроки, заказчики, коллеги - сколько людей КАЖДУЮ функцию сделают быстрей? И насколько раздуются исходники?
В конце-концов, почему-то в программировании уже многие десятилетия идёт тенденция ко всё более высокоуровневым языкам.
Не спорю, в процессе обучения можно и нужно писать своё. Для души можно. Можно даже потом выложить opensource.
А когда есть сроки, заказчики, коллеги - сколько людей КАЖДУЮ функцию сделают быстрей? И насколько раздуются исходники?
В конце-концов, почему-то в программировании уже многие десятилетия идёт тенденция ко всё более высокоуровневым языкам.
попробуй сделать поиск не простым перебором, а как-нибудь улучшить алгоритм, методом (золотого) сечения и т.п., у тебя же упорядоченный массив: например, брать не следующий элемент ($i++), а из середины массива ($i = ($end - $start) div 2), тем самым с каждым шагом цикла отсекая половину массива, должно получиться довольно быстро.
Почти всегда можно найти способ произвести поиск по массиву быстрее, чем array_search. И даже если нет, то скорость не так сильно влияет - как написали выше большие массивы в php редко используются. Однако одна из главных причин, почему я стараюсь этой функцией пользоваться как можно чаще - всегда приятнее использовать определенные в php функции. Приятнее и элегантнее.
а если вот так вот поиск сделать? как скорость?
$test_array_2 = array_flip ( $test_array );
echo $test_array_2 [$ta];
$test_array_2 = array_flip ( $test_array );
echo $test_array_2 [$ta];
Не надо ничего знать и особого склада ума не надо.
Просто, когда вдруг понадобиться поиск по массиву нужно подумать: "а вот есть прекрасная документация на php.net и там огромная куча функций по работе с массивами, давайте в первую очередь просмотрим их список".
Просто, когда вдруг понадобиться поиск по массиву нужно подумать: "а вот есть прекрасная документация на php.net и там огромная куча функций по работе с массивами, давайте в первую очередь просмотрим их список".
Если вдруг вам надо обработать в пхп массив из 100000 элементов - скорее всего вы делаете что-то не так.
Да и в этом случае любой метод достаточно быстр.
А то, что исполнение бинарного кода быстрее, чем интерпретация - это ведь очевидно.
Да и в этом случае любой метод достаточно быстр.
А то, что исполнение бинарного кода быстрее, чем интерпретация - это ведь очевидно.
я тут совершенно случайно выяснил что быстрее array_search() ищет array_key_exists()
правда не намного, но все же.
вот мои результаты:
правда не намного, но все же.
вот мои результаты:
array_key_exists код выполнен в среднем за : 0.0080071 секунды
array_search код выполнен в среднем за : 0.0081417 секунды
foreach код выполнен в среднем за : 0.0488250 секунды
while код выполнен в среднем за : 0.0694158 секунды
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
PHP: array_search — быстрый поиск по массиву