Python中的字符串搜索算法比較[教程作業]

Question

我正在Python中使用defaultdict進行簡單的算法排序，創建一個用作鍵的散列，然後只是通過字典，然後打印出超過一個單詞值。

最初通過使用創建一個排序的字符串製作哈希開始：

def createHashFromFile(fileName): 
    with open(fileName) as fileObj: 
     for line in fileObj: 
      line = line.lower() 
      aHash = ("").join(sorted(line.strip())) 
      aSorter[aHash].append(line.strip()) 

但是，因爲排序（）函數是O（n^2）都配備了由創造過黃金哈希的建議因式分解。我創建了一個已經映射所有的小寫字母的黃金，然後做了解釋：

def keyHash(word): 
    mulValue = 1 
    for letter in word: 
     letter = letter.lower() 
     mulValue = mulValue * primeDict[letter] 

    return mulValue 

在30萬字，在0.75s字符串哈希運行，並在1秒的主要哈希奔跑。我一直在讀這篇文章，但我無法確定我是否錯過了這個或者它爲什麼運行速度較慢。

就作業而言，這已經完成，但我想了解我在這裏失蹤的原因或缺點。

Answer 1

有一大堆的因素會在這裏的：

• sorted是O（n log n）的平均情況，而不是爲O（n^2）。最糟糕的情況在真正的節目中幾乎從不相關。
• 將素數相乘是一個聰明的訣竅，但雖然它是乘法運算中的O（n）代價，但將一個大數N乘以一個小因子將成本爲O（log N），而不是O（1）你必須通過bignum的O（log N）數字）。這意味着主要技術也將是O（n log n），因爲keyHash（s）將具有O（len（s））數字。
• n很小，所以實現細節將比複雜性更重要。
• sorted內置並用C語言編寫。實現已經調整了很多年。您的主要乘法代碼是用Python編寫的。
• 你不會在你的問題中說你如何執行時間。例如，通過對整個程序進行計時而非微觀基準，很容易弄錯。鑑於結果的接近程度，我預計你會犯這樣的錯誤，但這是一個猜測。