Производительность - почему алгоритм генерации простых чисел с диапазоном намного быстрее, чем использование простого списка? - PullRequest
Новая
       19

Производительность - почему алгоритм генерации простых чисел с диапазоном намного быстрее, чем использование простого списка?

0 голосов
/ 03 января 2019

Я написал два кода с почти одинаковой структурой: 

def prime_gen1(Limit = 10000):
    List = [2,]
    for x in range(3,Limit):
        for y in List:
            if not x%y:
                break
        if not x%y:
            continue
        else:
            List.append(x)
            yield x

def prime_gen2(Limit = 10000):
    from math import floor
    for x in range(3,Limit):
        for y in range(2, floor(x**0.5)+2):
            if not x%y:
                break
        if not x%y:
            continue
        else:
            yield x

>>> list(prime_gen1(20000)) == list(prime_gen2(20000))
True
>>> def time1(number):
    st = time()
    list(prime_gen1(number))
    end = time()
    return end - st

>>> def time2(number):
    st = time()
    list(prime_gen2(number))
    end = time()
    return end - st

Один выполняет ту же работу, что и другие, но последний на самом деле работает намного быстрее.Мне интересно, почему это происходит.

Логически - или нелогично, я думал, что проверка с простыми числами превзойдет другой способ, в этом случае - проверка числами от 3 до корня числа. Но проверка времени показала порокнаоборот, проверка со всеми числами работает намного быстрее - примерно в 5 раз.Его производительность все больше различается, 

>>> time1(200000)
8.185129404067993
>>> time2(200000)
0.4998643398284912

Второй метод превосходит его.Что отличает это?

Ответы [ 2 ]

0 голосов
/ 03 января 2019

Некоторые лучшие моменты времени 

%timeit list(prime_gen1(10**5))
2.77 s ± 204 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit list(prime_gen2(10**5))
219 ms ± 10.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

В вашем втором алгоритме вы предприняли ряд шагов по оптимизации, но не в первом: вот некоторые проблемы с вашим первым алгоритмом. 

def prime_gen1(Limit = 10000):
    List = [2,]
    for x in range(3,Limit):  # we're checking all even numbers too
        for y in List:  # only need to check up to sqrt(x)!!
            if not x%y:
                break
        if not x%y:  # why are we checking again? Use a for-else construct
            continue
        else:
            List.append(x)  # just return the list at the end
            yield x  # when wrapped in list just copies List

Вот оптимизированная версия первого алгоритма (не генератор, потому что генератор из списка просто бессмыслен): 

def memeff_primelist(n):
    if n <= 2:
        return []
    primes = []  # Add 2 in at the end, don't need to check non-even
    for i in range(3, int(n), 2):
        for p in primes:
            if i % p == 0:  # non-prime
                break
            if p * p > i:  # no factors bigger than sqrt(i)!!!
                primes.append(i)
                break
        else:
            primes.append(i)  # only for i == 3
    primes.insert(0, 2)
    return primes

%timeit memeff_primelist(10**5)
88.9 ms ± 16.5 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
0 голосов
/ 03 января 2019

версия списка делает намного больше проверок, чем та, которая идет только к квадратному корню из числа

для предела 200000, квадратный корень равен ~ 447, есть 17983 простых числа меньше, чем 200000

просто добавьте счетчик того, сколько раз вы выполняете проверку x% y, например 

def prime_gen1(Limit = 10000):
    List = [2,]
    modulo_checks = 0
    for x in range(3,Limit):
        for y in List:
            modulo_checks += 1
            if not x%y:
                break
        if not x%y:
            continue
        else:
            List.append(x)
            yield x
    print(modulo_checks)

def prime_gen2(Limit = 10000):
    from math import floor
    modulo_checks = 0
    for x in range(3,Limit):
        for y in range(2, floor(x**0.5)+2):
            modulo_checks += 1
            if not x%y:
                break
        if not x%y:
            continue
        else:
            yield x
    print(modulo_checks)

, теперь для предела 200000 версия 1 выполняет 162416226 проверок, а вторая 7185445

, если выдобавьте ранний разрыв для зацикливания списка, версия списка значительно быстрее (в 2 раза быстрее, 1799767 проверяет 0,24 с против 7185445 проверяет 0,64 с) 

...
    sq_root = floor(x ** 0.5) + 2
    for y in List:
        modulo_checks += 1
        if not x % y or y > sq_root:
            break
...

и удаляет математический импорт, если вы хотите сравнить скорости алгоритма

...