python - 加速字符串拆分和连接

Question

我正在尝试解决 Project Euler's problem #35

The number, 197, is called a circular prime because all rotations of the digits: 197, 971, and 719, are themselves prime.

How many circular primes are there below one million?

这是我的解决方案:

import numpy as np

def problem(n=100):

    circulars = np.array([], np.int32)

    p = np.array(sieveOfAtkin(n), np.int32)
    for prime in p:
        prime_str = str(prime)
        is_circular = True
        for i in xrange(len(prime_str)):
            m = int(prime_str[i:]+prime_str[:i])
            if not m in p:
                is_circular = False

        if is_circular:
            circulars = np.append(circulars, [prime])

    return len(circulars)

不幸的是，for 循环非常慢!有什么想法可以加快速度吗？我怀疑字符串连接是瓶颈，但我不完全确定! :)

---

有什么想法吗？ :)

Answer 1

1. 使用集合而不是数组进行成员资格测试。哈希查找将是 O(1) 而不是 O(n)。这是最大的瓶颈。

2. 一旦发现它不是圆素数，就立即跳出循环，而不是尝试其他旋转。这是另一个瓶颈。

---

在这里，我将循环性测试分离到一个函数中，以允许使用列表理解来构建列表。将它放在一个函数中，让它在我们知道它不是循环时立即返回 False。另一种选择是在 for 循环和 break 中执行它，当我们知道它不是循环时。然后附加到循环的 else 子句中的列表。一般来说，列表组合比在循环中追加要快。这里可能不是这种情况，因为它确实增加了函数调用开销。如果您真的关心速度，那么分析这两个选项是值得的。

primes = set(primes_to_one_million_however_you_want_to_get_them)

def is_circular(prime, primes=primes):
   prime_str = str(prime)
   # With thanks to Sven Marnach's comments
   return all(int(prime_str[i:]+prime_str[:i]) in primes 
              for i in xrange(len(prime_str)))


circular_primes = [p for p in primes if is_circular(p)]

我还使用了将全局变量作为默认参数传递给 is_circular 函数的技巧。这意味着它可以在函数内作为局部变量而不是更快的全局变量进行访问。

这是一种在循环中使用 else 子句对其进行编码的方法，以摆脱丑陋的标志并提高效率。

circular = []
for p in primes:
   prime_str = str(prime)
   for i in xrange(len(prime_str)):
       if int(prime_str[i:]+prime_str[:i]) not in primes:
            break
   else:
       circular.append(p)