PHP: array_search — быстрый поиск по массиву

    Я уже достаточно долго использую функцию array_search() для поиска значений в массиве, так как неоднократно слышал и читал о том, что она работает заметно быстрее, чем поиск по массиву в цикле, но насколько она быстрее — не знал. Наконец-то дошли руки самому проверить и посчитать.

    Сравнил скорость поиска в массиве с помощью этой функции с обычным перебором массива в циклах foreach и while. На 10-100 элементах массива разница незаметна да и время столь мало, что им можно принебречь. А вот для больших массивов разница оказалась весьма существенной. С увеличением размера массива на порядок, значительно увеличивалось и время поиска. При ста тысячах элементов скорость foreach падала до 0,013 секунды, а while — до 0,017, при том что array_search() тоже замедлился, но все-таки остался на порядок быстрее — 0.004 секунды. Для большого скрипта, работающего с большими массивами замена поиска в цикле на поиск с помощью array_search() будет вовсе не «блошиной оптимизацией».

    UPD: добавил в циклы break и менял искомое значение так, чтобы оно было в середине массива — 5-50-500 и т.д. Данные в таблице обновленные.
    Число элементов массива   array_search   Цикл foreach  Цикл while  
    10 0.0000068 0.0000064 0.0000076
    100 0.0000078 0.0000153 0.0000185
    1000 0.0000209 0.0001177 0.0001351
    10000 0.0004210 0.0012128 0.0018670
    100000 0.0039679 0.0130989 0.0175215


    В связи с этим вспомнил недавнюю дискуссию с одним из коллег на работе — насчет того, нужно ли программисту знать все эти встроенные функции языка, или достаточно «программистского склада ума» и общих познаний. Не вдаваясь с рассуждения об этом самом складе ума, думаю, что все-таки знать функции надо, может быть не весь синтаксис в деталях, а хотя-бы какие функции есть и что они в общих чертах могут.

    UPD: нужен программистский склад ума, тоже нужен! И внимательность с памятью не помешают (навеяно break и range :)

    Под хабракатом код скрипта, которым подсчитывал время:



    $mass=100000; // число значений в массиве в котором будем искать
    $search=50000; // в массиве будем искать это значение
    $first_result=array(); // массив результатов, для вычисления среднего значения первого варианта
    $second_result=array(); // массив результатов, для вычисления среднего значения второго варианта
    $third_result=array(); // массив результатов, для вычисления среднего значения третьего варианта

    // создаем и наполняем массив
    $test_array = range(0, $mass-1); // спасибо SelenIT ))

    /*
    $test_array=array();
    for ($i=0; $i<$mass; $i++)
    {
    $test_array[]=$i;
    }
    */

    // цикл для подсчета средних значений
    for ($d=0; $d<30; $d++) {

    //*************** Поиск с помощью array_search *******************

    // Запускаем подсчет времени
    $time_start = microtime(1);
    // поиск
    $key = array_search($search, $test_array, true);
    // если нашли
    if ($key!==FALSE) // надо именно !== а не !=, ведь номер первого элемента — 0
    {
    echo $test_array[$key];
    }
    $time_end = microtime(1);
    // конец подсчета времени

    // пишем в массив значений
    $first_result[]= $time_end — $time_start;

    //*************** Поиск по массиву с циклом foreach *******************

    // Запускаем подсчет времени
    $time_start = microtime(1);
    // сам поиск
    foreach ($test_array as $ta)
    {
    if ($ta==$search)
    {
    echo $ta;
    break;
    }
    }
    $time_end = microtime(1);
    // конец подсчета времени

    // пишем в массив значений
    $second_result[]= $time_end — $time_start;

    //*************** Поиск по массиву с циклом while *******************

    // Запускаем подсчет времени
    $time_start = microtime(1);

    // определяем длину массива
    $count=count($test_array);
    $j=0;
    // сам поиск
    while ($j<$count)
    {
    if ($test_array[$j]==$search) // если нашли
    {
    echo $test_array[$j];
    break;
    }
    $j++;
    }
    $time_end = microtime(1);
    // конец подсчета времени

    // пишем в массив значений
    $third_result[]= $time_end — $time_start;
    }

    $srednee1=array_sum ($first_result)/count($first_result);
    $srednee2=array_sum ($second_result)/count($second_result);
    $srednee3=array_sum ($third_result)/count($third_result);

    printf('первый код выполнен в среднем за: %.7f секунды', $srednee1);
    printf('второй код выполнен в среднем за: %.7f секунды', $srednee2);
    printf('третий код выполнен в среднем за: %.7f секунды', $srednee3);

    // результат:
    // первый код выполнен в среднем за: 0.0000295 секунды
    // второй код выполнен в среднем за: 0.0153386 секунды
    // третий код выполнен в среднем за: 0.0226001 секунды

    Похожие публикации

    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

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

      0
      И что там за алгоритм у этого array_search?
        0
        Мне это самому интересно, но где такую информацию можно найти - не знаю.
          0
          Думаю, он просто использует внутреннее представление массивов в PHP. Точно как там это все хранится я не знаю, но сильно подозреваю, что в виде какого-нибудь дерева или хэш-таблицы. Отсюда и разница в скорости с тупым перебором в несколько порядков.
            0
            Где-то встречал описание внутренней структуры массивов в PHP, сечас, к сожалению, не могу найти, потому не гарантирую точность. Внутренняя структура массива включает в себя хештаблицу для поиска по ключу, двусвязный список для обхода элементов, плюс служебные поля, например, кол-во элементов, следующий числовой индекс, ссылка на текущий элемент...

            В результатах ничего удивительного нет:

            1. Бинарный код всегда будет работать быстрее. Внутри, я думаю, простой перебор, т.к. о данных ничего не известно, в пользу этого говорит и то, что при наличии нескольких значений, равных искомому, возвращается ключ первого элемента.

            2. При наличии break - то же самое, что и в первом случае, но на PHP... естественно медленнее.

            3. Еще хуже. for/while не лучшее решение для перебора элементов массива, т.к. на каждой итерации выполняется поиск в хештаблице. foreach для этого предпочтительней, ибо просто перебирает элементы списка.
              +5
              Вы не поверите, но там 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
                0
                Наверно, имелся ввиду while в PHP, а не в C
                  0
                  Нет, интересовались как раз фактом внутренней реализации array_search.
              –1
              думаю, когда элемент найден, вызывается break или return (что там в пхп прерывает циклы?).
              Поэтому, если в циклах while & for сделать тот же break, результаты отличаться не будут (проверять не стал. не знаю пхп). Судя по результатам, так оно и есть: массив увеличился на порядок - циклы стали работать дольше на порядок. В то время, как этот аррай_серч по времени почти отрабатывает столько же.
                0
                Нет, для выхода из цикла нужен break (ну или если цикл не по счетчику а по условию, то можно по изменению этого условия выходить). Ведь это здесь мы ищем один объект, а если нам нужно найти два, три или больше? Если мы с болшим количеством элементов массива должны что-то сделать?
                  0
                  ну не знаю, а если foreach заменить на for? *думаю*
              +2
              Вы break не делали.. чего вы ожидали он же всего лишь 277 получался.
              А foreach и while о всему массиву шарились
                0
                Нда, промашка вышла (( Спасибо что заметили!

                С break и $search=20277; выходит так:
                0.0009716 секунды
                0.0029547 секунды
                0.0040365 секунды

                при $search=50277;
                0.0024067 секунды
                0.0073349 секунды
                0.0104051 секунды

                В общем array_search все равно лидирует, хотя отрыв поменьше получается.
                  0
                  > Нда, промашка вышла (( Спасибо что заметили!
                  Неплохо бы и в статье изменить.
                    0
                    Подправил в статье
                +5
                нет уж, давайте всё-таки вернёмся к "программистскому складу ума"...

                данная задача — "состоит ли элемент в массиве данных" — решится значительно быстрее, если данные изначально организовывать по-другому: for($i=0; $i < $mass; $i++) $test_array[$i] = true;

                в таком случае время поиска элемента — isset($test_array[$i]) — Вас приятно удивит.
                если работать не с целыми числами, а строками, то, предполагаю, такой поиск удивит Вас ещё сильнее и приятнее. =)
                • НЛО прилетело и опубликовало эту надпись здесь
                    0
                    Поиск по индексу конечно работает несравнимо быстрее ( даже для интересу сравнил - очень быстро :)) Но здесь все-таки тестовая задача, а в реальном скрипте это не всегда удобно. Хотя где возможно тоже можно применять, согласен.
                    • НЛО прилетело и опубликовало эту надпись здесь
                      0
                      Давайте вернёмся.
                      Что быстрей, для каждого чиха изобретать и отлаживать свой велосипед (не о конкретном случае, а вообще), да ещё следить, чтобы он получался высокопроизводительным, безглючным, безопасным, - или пользоваться уже готовыми велосипедами, зная об их существовании?
                        +1
                        чтобы у кого-то всегда были под рукой готовые велосипеды, их должен кто-то изобретать, неправда ли?
                        ну, и что для одного является "изобретением целого велосипеда", для другого — ясное и очевидное решение.
                          0
                          Мне это напоминает о спорах любителей использовать готовые фреймворки (cms, либы и так далее) и любителей писать свои.

                          Не спорю, в процессе обучения можно и нужно писать своё. Для души можно. Можно даже потом выложить opensource.
                          А когда есть сроки, заказчики, коллеги - сколько людей КАЖДУЮ функцию сделают быстрей? И насколько раздуются исходники?

                          В конце-концов, почему-то в программировании уже многие десятилетия идёт тенденция ко всё более высокоуровневым языкам.
                      +1
                      попробуй сделать поиск не простым перебором, а как-нибудь улучшить алгоритм, методом (золотого) сечения и т.п., у тебя же упорядоченный массив: например, брать не следующий элемент ($i++), а из середины массива ($i = ($end - $start) div 2), тем самым с каждым шагом цикла отсекая половину массива, должно получиться довольно быстро.
                        0
                        Почти всегда можно найти способ произвести поиск по массиву быстрее, чем array_search. И даже если нет, то скорость не так сильно влияет - как написали выше большие массивы в php редко используются. Однако одна из главных причин, почему я стараюсь этой функцией пользоваться как можно чаще - всегда приятнее использовать определенные в php функции. Приятнее и элегантнее.
                          +1
                          особенно приятно использовать функции по их прямому назначению
                          иногда можно только по-удивляться, на что готов пойти программист для выполнения задачи, только бы не искать готовые встроенные функции
                          • НЛО прилетело и опубликовало эту надпись здесь
                              0
                              Пример у меня получился и как надо делать, и как не надо )) Заменил при обновлении текста.
                          0
                          а если вот так вот поиск сделать? как скорость?

                          $test_array_2 = array_flip ( $test_array );

                          echo $test_array_2 [$ta];
                            0
                            вернее

                            $test_array_2 = array_flip ( $test_array );
                            echo $test_array_2 [$search];
                              0
                              Проверьте.
                              Проверите — доложите :)
                                0
                                медленно )))
                                  0
                                  тут вместо перебора половины (в среднем) массива, перебор полного + создание новых элементов, хэшей и т.п.
                                  А вот если по одному массиву нужно искать несколько раз, тут ваш вариант может и выиграть.
                            • НЛО прилетело и опубликовало эту надпись здесь
                                +2
                                Не надо ничего знать и особого склада ума не надо.
                                Просто, когда вдруг понадобиться поиск по массиву нужно подумать: "а вот есть прекрасная документация на php.net и там огромная куча функций по работе с массивами, давайте в первую очередь просмотрим их список".
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  +1
                                  Если вдруг вам надо обработать в пхп массив из 100000 элементов - скорее всего вы делаете что-то не так.
                                  Да и в этом случае любой метод достаточно быстр.

                                  А то, что исполнение бинарного кода быстрее, чем интерпретация - это ведь очевидно.
                                    0
                                    я тут совершенно случайно выяснил что быстрее array_search() ищет array_key_exists()
                                    правда не намного, но все же.
                                    вот мои результаты:

                                    array_key_exists код выполнен в среднем за : 0.0080071 секунды
                                    array_search код выполнен в среднем за : 0.0081417 секунды
                                    foreach код выполнен в среднем за : 0.0488250 секунды
                                    while код выполнен в среднем за : 0.0694158 секунды

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

                                    Самое читаемое