L oop производительность - PullRequest
Новая
       84

L oop производительность

1 голос
/ 04 августа 2020

В данной задаче нижеуказанная функция должна быть выполнена менее чем за 1 секунду: 

from time import perf_counter


def loop(seed, n):
    tic_0 = perf_counter()

    r, m = seed, 0
    for i in range(1, n+1):
        m += 362437
        r = (r ** 2 + m) % 4294967296
        r = (r // 256) % 65536

    print('\nTotal Runtime = {:.6f}'.format(perf_counter() - tic_0))
    return r

loop(366, 11223300) -> 1 second limit

Единственный совет: скомпилированная программа может работать до 200 раз быстрее, чем математически идентичный сценарий в интерпретаторе Python.

Поскольку следующий член l oop зависит от предыдущего термина, использование модуля "multiprocessing" мне не пригодилось. Не могли бы вы дать мне какое-нибудь представление о том, как можно применить этот совет?

Выполнение кода в настоящее время занимает около 10 секунд.

Ответы [ 2 ]

1 голос
/ 04 августа 2020

Ну, это заняло всего 4,04 с на моей коробке, но я получил мгновенное сокращение до 2,5 с , просто изменив r ** 2 в r * r. Я мог бы дополнительно уменьшить его до 1,6 с , используя битовый сдвиг и побитовые операции, такие как изменение: 

r = (r * r + m) % 4294967296
r = (r // 256) % 65536

на: 

r = (r * r + m) & 0xffffffff
r = (r >> 8) & 0xffff

Затем, когда вы поймете, какие биты переживут эти две операции, вы можете превратить это в одно выражение: 

r = ((r * r + m) & 0xffff00) >> 8

Это сокращает время до 1,33 с. , легко удваивая скорость (уменьшение 67% затраченного времени).

Если вы переключитесь на что-то вроде Numba , вы можете получить еще большее улучшение: 

from numba import jit
from time import perf_counter

@jit()
def loop(seed, n):
    r, m = seed, 0
    for i in range(n):
        m += 362437
        r = ((r * r + m) & 0xffff00) >> 8
    return r

tic_0 = perf_counter()
x = loop(366, 11223300)
print('\nTotal Runtime = {:.6f}'.format(perf_counter() - tic_0))
print(x)

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

И это фактически включает время, необходимое для первоначальной JIT-компиляции кода, поэтому улучшение будет еще лучше при последующих вызовах. Если изменить код таким образом, чтобы мы сначала выполняли JIT-функцию, время снижается до 20 мс , экономия 99,5% : 

x = loop(1, 2)
tic_0 = perf_counter()
x = loop(366, 11223300)
print('\nTotal Runtime = {:.6f}'.format(perf_counter() - tic_0))
print(x)

Это наравне с аналогичным кодом C, который, вероятно, можно рассматривать как эталон производительности. Например, следующий код C выполняется за 27 мс , что примерно на 99,3% по времени (это по умолчанию оптимизация; использование -O3 дает около 18 мс ): 

#include <stdio.h>
int main(void) {
    unsigned long r = 366, m = 0;
    for (int i  = 0; i < 11223300; ++i) {
        m += 362437;
        r = ((r * r + m) & 0xffff00UL) >> 8;
    }
    printf("%ld\n", r);
    return 0;
}
0 голосов
/ 04 августа 2020

Разрешен обман?

Начальное начальное значение не сохраняется, поэтому, если значение r когда-либо достигнет нуля, это означает, что начальное начальное значение бессмысленно.

& 0xffff операция выполняется каждые l oop, и вероятность того, что случайно выбранное число будет иметь конечные цифры как 0x...0000 (в результате получится 0x...0000 & 0xffff = 0), равна (1/16)**4 = 65536.

Это происходит 187 раз для этих заданных начальных значений, что случается каждые 60017 итераций (довольно близко).

Это означает, что вам нужно только вычислить последний миллион или около того значений, чтобы получить «оптимизированный» l oop, который является наблюдательным идентично: 

from time import perf_counter

def loop2(seed, n):
    r, m = seed, 0

    for i in range(max(1, n - 1000000), n+1):
        r = ((r * r + i * 362437) >> 8) & 0xffff

    return r

tic_0 = perf_counter()

for init in range(1000):
    result = loop2(init, 11223300)
    assert result == 1738

print('\nTotal Runtime = {:.6f}'.format(perf_counter() - tic_0))

Эти 1000 циклов дали один и тот же ответ, и на их выполнение на моей машине потребовалось 315 секунд, в среднем 0,315 секунды.

...