加快字符串分割和拼接

我試圖解決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

加快字符串分割和拼接

回答

相關問題