python - 克服Ashton String任务中的MemoryError/运行时缓慢

在Ashton String task中，目标是:


Input Format:


Output Format:



和Constraints是



例如，给定输入:

1
dbac
3

输出为:c
我已经尝试使用此代码执行此任务，并且它适用于相对较短的字符串:

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？是否可以使用 native python2或python3以其他方式解决？

我试图通过使用MemoryError修剪堆栈来解决heapq的问题，但是现在它进入了 super 慢的运行时，插入并弹出堆，而不是占用过多内存。

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])

是否可以在不使用过多内存(导致MemoryError)与通过heapq推送和弹出而导致运行时间太慢之间取得平衡？

最佳答案

MemoryError意味着程序消耗了所有可用的内存，因此崩溃了。

可能的解决方案是使用可迭代(它们仅根据需要而不是一次全部计算值)的可迭代变量(它们在Py2中也可以使用，但Py3对其具有更好的支持)。

使您的程序适应生成器仅需稍作更改，即可在不使用列表的情况下为生成器建立索引(这将使懒惰的利益无效)，请参见:Get the nth item of a generator in Python