Почему использование более крупного колеса не делает моему колеса Prime Prime Syeve быстрее? ⇐ Python

[Anonymous]

Я предполагаю, что вы все знаете, что такое основные цифры и каковы сито Эратостенес, поэтому я не буду тратить время на объяснение их. > 13, 17, 19, 23, 29] % 30. Это видно из природы модуля. Существует только 30 возможностей, если модуль даже в то время, тогда число кратно 2 из 2, а другие возможности означают, что число составляет либо из 3, кратных 5 или обоих. Другими словами, все основные числа должны быть до 30, кроме 2, 3, 5. < /p>
В Python это: < /p>

Код: Выделить всё

wheel3 = [i for i in range(1, 30) if math.gcd(i, 30) == 1]
# [1, 7, 11, 13, 17, 19, 23, 29]

Теперь мы рассчитываем разницу между последовательными парами элементов, начиная с 7 и 1, появляется сразу после 29 из -за характера операции модуля, например, 31 % 30 == 1 , и поэтому разница между ними составляет 2.
Мы получаем следующее: [4, 2, 4, 2, 4, 2, 2, 6] . /> Теперь, из каждых 30 номеров, нам нужно только проверять 8 чисел, мы пропускаем 22 числа. Это значительное улучшение по сравнению с предыдущей оптимизацией только скорлубных нечетных чисел, нам необходимо было обрабатывать 15 чисел из каждых 30 чисел, если мы обрабатываем все нечетные числа, теперь у нас есть 7 чисел меньше, пространство поиска сузится до 4/15, что составляет 0,2666 ...
Мы можем оптимизировать это дальше, используя большие колеса, используя 2 * 3 * 5 * 7 = 210. 210. < /P>

Код: Выделить всё

wheel4 = [i for i in range(1, 210) if math.gcd(i, 210) == 1]
wheel4 == [
1  , 11 , 13 , 17 , 19 , 23 ,
29 , 31 , 37 , 41 , 43 , 47 ,
53 , 59 , 61 , 67 , 71 , 73 ,
79 , 83 , 89 , 97 , 101, 103,
107, 109, 113, 121, 127, 131,
137, 139, 143, 149, 151, 157,
163, 167, 169, 173, 179, 181,
187, 191, 193, 197, 199, 209
]
< /code>
и список изменений индекса: < /p>
[
2 , 4 , 2 , 4 , 6 , 2 ,
6 , 4 , 2 , 4 , 6 , 6 ,
2 , 6 , 4 , 2 , 6 , 4 ,
6 , 8 , 4 , 2 , 4 , 2 ,
4 , 8 , 6 , 4 , 6 , 2 ,
4 , 6 , 2 , 6 , 6 , 4 ,
2 , 4 , 6 , 2 , 6 , 4 ,
2 , 4 , 2 , 10, 2 , 10
]

Теперь из каждых 210 чисел нам нужно только обрабатывать 48 чисел, по сравнению с предыдущими 56 числами, нам нужно обрабатывать 8 чисел меньше, мы сузили пространство поиска до 8/35, что составляет 0,2285714285714287 ... и менее четверти. Время 30-й версии колеса на базе требуется для выполнения, но это не так. < /p>
import math
import numpy as np
import numba as nb

@nb.njit(cache=True)
def prime_wheel_sieve(n: int) -> np.ndarray:
wheel = [4, 2, 4, 2, 4, 6, 2, 6]
primes = np.ones(n + 1, dtype=np.uint8)
primes[:2] = False
for square, step in ((4, 2), (9, 6), (25, 10)):
primes[square::step] = False

k = 7
lim = int(math.sqrt(n) + 0.5)
i = 0
while k np.ndarray:
primes = np.ones(n + 1, dtype=np.uint8)
primes[:2] = False
for square, step in ((4, 2), (9, 6), (25, 10), (49, 14)):
primes[square::step] = False

k = 11
lim = int(math.sqrt(n) + 0.5)
i = 0
while k
In [549]: np.array_equal(prime_wheel_sieve(65536), prime_wheel_sieve4(65536))
Out[549]: True

In [550]: %timeit prime_wheel_sieve(65536)
161 μs ± 1.13 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [551]: %timeit prime_wheel_sieve4(65536)
163 μs ± 1.79 μs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

In [552]: %timeit prime_wheel_sieve4(131072)
330 μs ± 10.6 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [553]: %timeit prime_wheel_sieve(131072)
328 μs ± 7.4 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [554]: %timeit prime_wheel_sieve4(262144)
680 μs ± 14.3 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [555]: %timeit prime_wheel_sieve(262144)
669 μs ± 7.79 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [556]: %timeit prime_wheel_sieve(524288)
1.44 ms ± 16.2 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [557]: %timeit prime_wheel_sieve4(524288)
1.48 ms ± 13.4 μs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

In [558]: %timeit prime_wheel_sieve4(1048576)
3.25 ms ± 81.3 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [559]: %timeit prime_wheel_sieve(1048576)
3.23 ms ± 115 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [560]: %timeit prime_wheel_sieve(2097152)
7.08 ms ± 80.9 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [561]: %timeit prime_wheel_sieve4(2097152)
7.1 ms ± 85.9 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [562]: %timeit prime_wheel_sieve4(4194304)
14.8 ms ± 120 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [563]: %timeit prime_wheel_sieve(4194304)
14.2 ms ± 145 μs per loop (mean ± std. dev. of 7 runs, 100 loops each)

In [564]: %timeit prime_wheel_sieve(8388608)
39.4 ms ± 1.44 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [565]: %timeit prime_wheel_sieve4(8388608)
41.7 ms ± 2.56 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
< /code>
According to my tests, using a bigger wheel makes it slower not faster, why is it this case? Theoretically speaking using a bigger wheel narrows the search space, so it shouldn't cause increase in execution time, why does using a bigger wheel slow down the code?

Подробнее здесь: https://stackoverflow.com/questions/795 ... eve-faster