Python字典內存用完

我想在hackerrank.com代碼這個問題：Python字典內存用完

https://www.hackerrank.com/challenges/find-strings

我的代碼運行很好地爲小的情況下，但我的字典迅速耗盡內存在大案例。我能做些什麼來解決這個問題？我不想用一個列表，因爲那將需要很長時間才能檢查條目是否已經存在...這裏是我的代碼：

n = int(raw_input()) 
words = [] 
for x in range(n): 
    words.append(raw_input()) 
test = int(raw_input()) 
queries = [] 
for x in range(test): 
    queries.append(raw_input()) 

dict_of_subwords = {} 
for x in words: 
    len_of_x = len(x) 
    for i in range(len_of_x): 
     for j in range(i, len_of_x): 
      dict_of_subwords[x[i:j+1]] = 1 

list_of_subwords = dict_of_subwords.keys() 
list_of_subwords.sort() 
for x in queries: 
    try: 
     print list_of_subwords[int(x)-1] 
    except: 
     print "INVALID"

來源

2013-03-18 Chris

btw嘗試使用'set_of_subwords = set（）'而不是'dict_of_subwords = {}'。 – 9000 2013-03-18 17:30:43

我應該說，我也嘗試過套餐，並且得到相同的錯誤。 – Chris 2013-03-18 17:33:21

到目前爲止，我沒有重現它;問題中最大的'n'是50，所以我試圖用50個隨機的50個字符的字符串來提供算法，沒有任何不良影響。請發佈確切的錯誤消息。此外，嘗試在另一行計算'x [i：j + 1]'，以確保它是導致問題的'dict_of_subwords'訪問。 – 9000 2013-03-18 17:44:26

由於對製作更加內存 - 提出的許多建議有效的版本，下面是試圖最小化存儲量的版本（而仍然使用相同的算法方法）：

subwords = set() 

num_words = int(raw_input()) 
for i in xrange(num_words): 
    word = raw_input() 
    for i in xrange(len(word)): 
     for j in xrange(i, len(word)): 
      subwords.add(word[i:j+1]) 

subwords = sorted(subwords) 

num_queries = int(raw_input()) 
for x in range(num_queries): 
    query = raw_input() 
    try: 
     print subwords[int(query)-1] 
    except: 
     print "INVALID"

來源

2013-03-19 02:48:43 Moshe

同樣的問題。我試着運行它，我得到：第8行拋出的MemoryError – Chris 2013-03-19 05:46:26

這意味着這是有缺陷的方法，而不是代碼。這種方法構建了大量的子字符串，並將它們全部存儲起來。你需要更多的記憶效率算法。你看過後綴數組嗎？他們重新使用相同的字符串，並簡單地引用字符串中的索引。因此，不需要每個需要新對象的「字符串」，都可以在現有字符串中存儲引用和索引。 – Moshe 2013-03-20 00:38:33

您已經使用後綴陣列，wiki

suffix array implementation in python:

個

後綴陣列密切相關的後綴樹：

後綴數組可以通過執行後綴樹的深度優先遍歷來構造。後綴數組對應於在遍歷過程中訪問它們的順序中給出的葉標籤，如果邊以其第一個字符的字典順序訪問的話。
後綴樹可以通過使用後綴和LCP數組的組合在線性時間內構建。有關該算法的說明，請參閱LCP陣列文章中的相應部分。

來源

2014-02-06 11:00:49

Python字典內存用完

回答

相關問題