在python代碼中排序子字符串時拋出內存錯誤

-3

我有這個程序來形成一組字符串按字典順序排列的字符串。輸入字符串和字符串本身的數量作爲輸入，程序意圖按字典順序形成包含來自輸入的字符串和子字符串的集合。在python代碼中排序子字符串時拋出內存錯誤

strst=set() 
nos=input() 

for i in range(0,nos): 
    ele=raw_input() 
    for j in range(0,len(ele),1): 
     for k in range(j+1,len(ele)+1): 
       strst.add(ele[j:k]) 

strlst=sorted(strst) 

print strlst

氏程序存儲子在一組，後來排序，保持字典順序，最後打印出整個列表

爲如：

INPUT : 

2    //number of input strings 
aab 
aac 

OUTPUT 

['a', 'aa', 'aab', 'aac', 'ab', 'ac', 'b', 'c']

程序工作正常進行小尺寸的輸入，但是當輸入大小，即輸入字符串的數量和每個字符串的長度在2000範圍內增加時，它會給出例外：

MemoryError thrown on line 9

我thk我還沒有優化代碼。可以優化分類嗎？可以擴展設置數據結構和列表的大小嗎？

來源

2013-07-28 ranger

如果您可以包含3件事情，這將有所幫助。 1：解釋你所要做的事情，不僅僅是代碼，而且「它不起作用」2：*做的樣本輸入*爲你工作3：輸入經過你的輸入後得到的輸出功能。 –

它真的說'9號線引發的MemoryError？該格式看起來不對。你能粘貼實際的堆棧跟蹤嗎？ – user2357112

這是__Python__不是C - 擺脫分號！ –

陳述它可能看起來多餘我懷疑你得到內存錯誤的原因是你的內存不足。

如果有2個長度爲3的大多是重疊的字符串你得到8個元素則只是非空白覆蓋所有可能的3個字母= 26 + 650 + 15600 = 16276

作爲一個快速測試：

>>> n = 0 
>>> for m in range(1, 20): 
...  for i in itertools.permutations(range(26), m): 
...   n+=1 
...  print m, n 
... 
1 26 
2 676 
3 16276 
4 375076 
5 8268676 
6 174034276

....

來源

2013-07-28 08:15:14

我沒有看到排列在這裏是如何相關的。該程序正在構建子串，而不是排列組合;它應該只在輸入大小上具有二次空間要求，或者如果子字符串實現正在複製數據而不是在字符串之間共享，則應該是立方體。 – user2357112

由於它是秩序關鍵排列給出了問題的大小的指示。 –

正如史蒂夫正確地指出的問題是，你是在內存中的字符串輸入字符串的組合的數量。

正確的解決方案是使用生成器函數來生成輸入字符串的組合。

幸運的是，python標準庫已經包含了itertools包，它將幫助您以更少的代碼和更有效的方式實現您想要的功能。下面給出的是會產生，您顯示在你的問題的例子相同的輸出一個示例代碼段：

import itertools 
from itertools import combinations 
x = "aab" 
y = "aac" 
x_permutation =[] 
y_permutation = [] 

#use the combinations method within the itertools package to generate all possible combinations of a given length for a given string 

for i in xrange(1,len(x)+1): 
     x_permutation = x_permutation + list(map("".join,combinations(x,i))) 

for i in xrange(1,len(y)+1): 
     y_permutation = y_permutation + list(map("".join, combinations(y,i))) 

#if the input string is already sorted for e.g. "ABCD" , you do not really need to call the sort.However, when we do not have this guarantee then it is better to call sort() 

x_permutation.sort() 
y_permutation.sort() 

#merge the two lists into a set and then sort the set using the built-in **sorted()** 
output_set =sorted(set (x_permutation + y_permutation)) 

print output_set

以上腳本的輸出是：['a', 'aa', 'aab', 'aac', 'ab', 'ac', 'b', 'c']

希望這個現在應該幫助你可以考慮使用itertools技術來解決你的問題。

來源

2013-07-28 09:15:29

在python代碼中排序子字符串時拋出內存錯誤

回答

相關問題