C - поиск в массиве с обеих сторон

#c #arrays #search

#c #массивы #Поиск

Вопрос:

Есть ли какая-либо разница в скорости между первым циклом и вторым, когда дело доходит до скорости его выполнения? Я говорю также о массивах большего размера, чем этот пример.

 int main()
{
    int n = 17;
    int posz = 7;
    int array[] = {0, 1, 9, 2, 8, 3, 8, 5, 4, 7, 6, 10, 23, 43, 123, 54, 76, 34};
    for (int i = 0; i < (n / 2)   1; i  )
    {
        if (array[i] == posz || array[n - 1 - i] == posz)
        {
            std::cout << "foundn";
            break;
        }
    }

    for (int i = 0; i < n; i  )
    {
        if (array[i] == posz)
        {
            std::cout << "foundn";
            break;
        }
    }

    return 0;
}

1. Я сомневаюсь в этом. Я предполагаю, что вариант 1 медленнее (больше операций). Если бы я увидел вариант 1 в обзоре кода, вы бы переписали его в вариант 2, поскольку он намного понятнее 🙂

2. Если бы метод 1 был быстрее, разработчики функции std::find алгоритма догадались бы написать цикл таким образом.

Ответ №1:

С точки зрения времени Big-O, нет, поскольку оба метода равны O (n).

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

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

На данный момент это действительно зависит от того, что более понятно о том, чего вы пытаетесь достичь, поэтому я бы рекомендовал цикл # 2. Не говоря уже о том, что второй подход гораздо менее подвержен ошибкам.