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

Временная сложность алгоритма может многое сказать о его эффективности — это правда, но важны и детали реализации. Вот, к примеру, два фрагмента кода, в которых проверяется, есть ли в массиве \(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

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

Авторизация