Оптимизация кода

Временная сложность алгоритма может многое сказать о его эффективности — это правда, но важны и детали реализации. Вот, к примеру, два фрагмента кода, в которых проверяется, есть ли в массиве a элемент x:

ok = False
for i in range(n):
    if a[i] == x:
        ok = True

ok = False
for i in range(n):
    if a[i] == x:
        ok = True
        break

Оба фрагмента работают за время \(O(n)\), однако на практике второй может оказаться значительно эффективнее, потому что прекращает работу, как только элемент x найден. Это полезная оптимизация, потому что она действительно повышает производительность кода и к тому же легко реализуется.

Особенности процессора

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

Кеши

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

В качестве примера рассмотрим два таких фрагмента:

for i in range(n):
    for j in range(n):
        s += a[i][j]

for i in range(n):
    for j in range(n):
        s += a[j][i]

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

\(x[0][0], \; x[0][1], \; \ldots , \; x[0][n-1], \;x[1][0], \; x[1][1], \; \ldots\)

Поэтому лучше, когда во внешнем цикле изменяется первый индекс, а во внутреннем — второй.

Распараллеливание

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

f = 1
for i in range(1, n + 1):
    f = (f * i) % M

Здесь в цикле вычисляется факториал n по модулю M. Можно попробовать сделать этот код эффективнее, поступив следующим образом (в предположении, что n чётно):

f1 = 1
f2 = 1
for i in range(1, n + 1, 2):
    f1 = (f1 * i) % M
    f2 = (f2 * (i + 1)) % M
f = f1 * f2 % M

Идея в том, чтобы использовать две независимые переменные: f1 будет содержать произведение \(1 \cdot 3 \cdot 5 \cdot \ldots \cdot (n – 1)\), а f2 — произведение \(2 \cdot 4 \cdot 6 \cdot \ldots \cdot n\). По завершении цикла оба результата объединяются. Этот код обычно работает в два раза быстрее первоначальной версии, потому что процессор может параллельно выполнять команды, изменяющие переменные f1 и f2 внутри цикла. Можно даже завести больше переменных (скажем, четыре или восемь) и тем самым еще увеличить скорость работы.

Авторизация