时间戳

首页 > 解决方案 > Python：减少运行时间？

python - Python：减少运行时间？

问题描述

我最近开始学习 python，并且正在使用 CodeWars 进行训练。任务是返回一个列表[p, p + 4, p + 6, p + 10, p + 12, p + 16]，其中所有这些都是素数。它们的总和应该高于 sum_limit。对于低值，它正在工作，但在高值（约 200 万）时，运行时间很高。如何减少运行时间？

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))

标签： pythonruntime

解决方案

这是我关于降低复杂性和运行时间的想法。

你可以写一个筛子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。在我的筛子中，我们可以迭代生成器，直到 number 大于该值。

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)

这在我的计算机上运行不到一秒钟。

推荐阅读