Python: сократить время выполнения?

Question

Я недавно начал изучать python, и я использую CodeWars для обучения. Задача состоит в том, чтобы вернуть список [p, p + 4, p + 6, p + 10, p + 12, p + 16], где все они являются простыми числами. Сумма их должна быть выше, чем sum_limit. Для низких значений это работает, но при высоких значениях (около 2 миллионов) время выполнения велико. Как я могу уменьшить время выполнения?

from math import sqrt; from itertools import count, islice

def find_primes_sextuplet(sum_limit):
    for x in range(sum_limit):
        if isPrime(x) and isPrime(x+4) and isPrime(x+6) and isPrime(x+10) and isPrime(x+12) and isPrime(x+16):
            possible = [x, x+4, x+6, x+10, x+12, x+16]
            if sum(possible) > sum_limit:
                return possible


def isPrime(n):
    return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))


print(find_primes_sextuplet(2000000))

Answer 1

Существуют различные способы улучшить время выполнения вашего кода. Например, многие числа проверяются на то, что они являются простыми числами, хотя их сумма в результате не подходит. Вычисление суммы из 6 чисел происходит быстрее, чем проверка их простоты. Вы можете переместить проверку суммы над основной проверкой и проверять числа на простые числа только в том случае, если их сумма будет приемлемой.

Чтобы еще больше улучшить это, вы можете пропустить числа, которые не приведут к приемлемой сумме, начав диапазон на полу возможных чисел.

x + x + 4 + x + 6 + x + 10 + x + 12 + x + 16 = 6x + 48

, который должен быть выше вашего sum_limit

6x + 48 >= sum_limit
x >=(sum_limit - 48) / 6

Так что, если ваш диапазон начинается с x, вы пропустите все числа, которые не приведут к приемлемая сумма в любом случае. Вы также сможете улучшить время выполнения, пропустив четные числа в вашем l oop (через диапазон (y, x, 2)). Дальнейшее улучшение времени выполнения потребует от вас настройки функции isPrime.

Answer 2

Вот мои мысли о снижении сложности и времени выполнения.

Вы можете написать сито в O(n log log n). Вот разумная реализация:

def sieve(n):
    grid = [None for _ in range(n+1)]
    i = 2
    while i < n+1:
       if grid[i] is None:
           grid[i] = True
           for p in range(2*i, n+1, i):
               grid[p] = False
       else:
           i += 1
    return (index for index, b in enumerate(grid) if b)

Есть 6 чисел, и общая сумма, добавленная к первому числу, равна 48. Таким образом, минимально возможное значение для первого числа равно (n - 48) / 6. В моем сите мы можем итерировать генератор до тех пор, пока число не станет больше.

def get_remaining_sieve(n):
    g = sieve(n)
    current = next(g)
    min_value = (n - 48) / 6
    while current < min_value:
        current = next(g)
    return [current] + list(g)

Теперь просто итерируем по каждому срезу длины 6 и проверяем, соответствует ли разделение требуемому разделению (4, 2, 4, 2, 4).

remaining = get_remaining_sieve(n)
for start in range(len(remaining) - 5):
    slice = remaining[start:start+6]
    differences = [slice[j] - slice[j-1] for j in range(1, 6)]
    if differences == [4, 2, 4, 2, 4]:
        print(slice)

---

Резюме

Основываясь на этих принципах, я пришел к следующему решению:

from itertools import dropwhile, islice
def get_solutions(n):
    grid = [None for _ in range(n+1)]
    i = 2
    while i < n+1:
        if grid[i] is None:
            grid[i] = True
            for p in range(2*i, n+1, i):
                grid[p] = False
        else:
            i += 1
    sieve = (index for index, b in enumerate(grid) if b)
    min_value = (n - 48) / 6
    reduced_sieve = dropwhile(lambda v: v < min_value, sieve)
    reference_slice = list(islice(reduced_sieve, 6))
    while True:
        try:
            ref = reference_slice[0]
            differences = [v - ref for v in reference_slice[1:]]
            if differences == [4, 6, 10, 12, 16]:
                yield reference_slice
            reference_slice = reference_slice[1:] + [next(reduced_sieve)]
        except StopIteration:
            break


n = 2000000
print(next(get_solutions(n)))  # 695ms

# or for all solutions
for solution in get_solutions(n):  # 755ms
    print(solution)

Это выполняется в менее чем за секунду на моем компьютере.

Answer 3

Для неотрицательных целочисленных значений n вы можете использовать это:

def isPrime(n):
    if n == 1 or n % 2 == 0 or n % 3 == 0:
        return False

    end = int(sqrt(n)+1)
    for start in [5, 7]:
        for k in range(start, end, 6):
            if n % k == 0:
                return False

    return True

Это не изменит теоретической сложности, но уменьшит практическое время выполнения.

И если вы измените внешний l oop на for x in range(5, sum_limit), то вы также можете избавиться от первоначальной проверки if n == 1 or n % 2 == 0 or n % 3 == 0.