加快字符串拆分和连接

Question

我正在努力解决Project Euler的问题#35

这个数字197被称为圆形素数,因为数字的所有旋转:197,971和719本身都是素数.

一百万以下有多少个圆形素数？

这是我的解决方案:

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)