克服MemoryError <a href="https://www.hackerrank.com/challenges/ashton-and-string" rel="nofollow">Ashton String task</a>でアシュトンストリングタスク

Question

中/低速ランタイム、目標はである：

が 辞書式順序で指定された文字列のすべての異なるサブストリングを配置し、それらを連結します。連結された文字列の のK番目の文字を表示します。与えられたKの値は であり、すなわちK番目の文字が有効であることが保証される。

Input Format：

最初の行は、テストケースの数T即ち番号を含むことになります。各テストケースは、文字 （-z）を含む文字列が含まれ、第二行番号K.

Output Formatを含有するであろう最初の ライン：

プリントK番目の文字（文字列であります索引付け1）

そしてConstraintsは

あります

1≦T≦5
1≦長さ≦105
Kは適切な整数になります。私はこのコードでタスクを実行しようとしましたし、それが比較的短い文字列のために働くc

：

1 
dbac 
3 

出力は次のようになります。入力与え例えば

、

from itertools import chain 

def zipngram(text, n=2): 
    words = list(text) 
    return zip(*[words[i:] for i in range(n)]) 

for _ in input(): 
    t = input() 
    position = int(input())-1 # 0th indexing 
    chargrams = chain(*[zipngram(t,i) for i in range(1,len(t)+1)]) 
    concatstr = ''.join(sorted([''.join(s) for s in chargrams])) 
    print (concatstr[position]) 

入力ファイルが次のようになっていれば：http://pastebin.com/raw/WEi2p09H、出力は

l 
s 
y 
h 
s 

インタプリタはMemoryErrorがスローされます。

Traceback (most recent call last): 
    File "solution.py", line 11, in <module> 
    chargrams = chain(*[zipngram(t,i) for i in range(1,len(t)+1)]) 
    File "solution.py", line 11, in <listcomp> 
    chargrams = chain(*[zipngram(t,i) for i in range(1,len(t)+1)]) 
    File "solution.py", line 6, in zipngram 
    return zip(*[words[i:] for i in range(n)]) 
    File "solution.py", line 6, in <listcomp> 
    return zip(*[words[i:] for i in range(n)]) 
MemoryError 

MemoryErrorを解決することができますか？それは別の方法でネイティブのpython2またはpython3を使用して解決可能ですか？

私はheapqを使用してスタックを剪定によってMemoryErrorを解決しようとしたが、今では押して、あまりにも多くのメモリを占有するのではなく、ヒープをポップユーバー遅いランタイムに入ります。

from itertools import chain 
import heapq 

t = int(input()) 
s = list(input()) 
k = int(input()) 

stack = [] 
for n in range(1,len(s)+1): 
    for j in range(n): 
     ngram = (''.join(s[j:])) 
     ngram_len = len(ngram) 
     # Push the ngram into the heapq. 
     heapq.heappush(stack, ngram) 
     pruned_stack = [] 
     temp_k = 0 
     # Prune stack. 
     while stack != [] and temp_k < k: 
      x = heapq.heappop(stack) 
      pruned_stack.append(x) 
      temp_k+=len(x) 
     # Replace stack with pruend_stack. 
     stack = pruned_stack 

print (''.join(chain(*pruned_stack))[k]) 

heapqを押してポップでそれがMemoryErrorにつながることをあまりにも多くのメモリと遅すぎるランタイムを使用していない間のバランスをとる方法はありますか？

Answer 1

MemoryErrorは、プログラムが使用可能なすべてのメモリを消費したため、クラッシュしたことを意味します。

可能な解決策は、怠惰なiterables（Py2でも動作しますが、Py3ではより効果的です）を使用することです。それは大量のサンプルのために働く、Get the nth item of a generator in Python

Answer 2

は、このコードを試してみてください。

参照（それは怠惰な利益を無効にします）のリストを使用せずにインデックスに、発電機をわずかな変更を必要とすべきである発電機にプログラムを適応。

def ashton(string, k): 
    #We need all the substrings, and they have to be sorted 
    sortedSubstrings = sorted_substrings(string) 
    count = 0 
    currentSubstring = 0 
    #Loop through the substrings, until we reach the kth character 
    while (count < k): 
     substringLen = len(sortedSubstrings[currentSubstring]) 
     #add the number of characters of the substring to our counter 
     count += substringLen 
     #advance the current substring by one 
     currentSubstring += 1 
    #We have the correct substring now, and calculate to get the right char 
    diff = count - k 
    #Return answer, index 1 = substring, index 2 = char in substring 
    return(sortedSubstrings[currentSubstring][substringLen-diff-1]) 

#Determine the substrings in correct order 
#Input: 'dbac', returns: a, ac, b, ba, bac, c, d, db, dba, dbac 
def sorted_substrings(string): 
    a = set() 
    length = len(string) 
    #loop through the string to get the substrings 
    for i in range(length): 
     for j in range(i + 1, length + 1): 
      #add each substring to our set 
      a.add(string[i:j]) 
    #we need the set to be sorted 
    a = sorted(a) 
    return a 

t = int(input()) 
for i in range(t): 
    s = input() 
    k = int(input()) 
    print(ashton(s, k))