加快字符串分割和拼接

我试图解决Project Euler's problem #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循环是强大的慢！任何想法我可以加快这一点？我怀疑字符串连接是瓶颈，但我不完全确定！ :)

任何想法？ :)

来源

2011-01-25 RadiantHex

为什么你使用字符串呢？ – hwiechers 2011-01-25 12:29:07

不要为`circulars`使用NumPy数组 - 它具有固定大小，并且需要在每次*调用`numpy.append（）`时重新分配。 Python列表在这里是更好的选择。（删除numpy标签，因为既不是问题也不是当前答案与numpy有关。） – 2011-01-25 13:08:46

使用一组用于成员资格测试，而不是一个数组。哈希查找将是O（1）而不是O（n）。这是最大的瓶颈。
只要你看到它不是一个圆形的素数而不是尝试其他的旋转就打破循环。这是另一个瓶颈。

在这里，我已经分离出的圆检测到的功能，允许列表与列表理解之上。把它放在一个函数中，只要我们知道它不是循环的就让它返回False。另一种方法是在for循环中执行此操作，如果我们知道它不是循环的，则执行break。然后追加到循环的else子句中的列表。一般来说，list comp比在循环中追加更快。这可能不是这种情况，因为它确实增加了函数调用开销。如果你真的关心速度，那么分析这两个选项是值得的。

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)

来源

2011-01-25 12:07:53 aaronasterling

加快字符串分割和拼接

回答

相关问题