克服Ashton String任务中的MemoryError/Slow Runtime

Question

在Ashton String任务中,目标是:

按字典顺序排列给定字符串的所有不同子串并将它们连接起来.打印连接字符串的第K个字符.确保K的给定值有效,即将存在第K个字符.

的Input Format:

第一行将包含数字T即测试用例数.每个测试用例的第一行将包含一个包含字符(a-z)的字符串,第二行将包含一个数字K.

的Output Format:

打印第K个字符(字符串为1索引)

而且Constraints是

1≤:T≤5
1≤长度≤105
k将是一个适当的整数.

例如,给定输入:

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？是否可以使用本机python2或python3以另一种方式解决？

我尝试MemoryError通过修剪堆栈来解决这个问题,heapq但现在它进入了一个非常慢的运行时推送和弹出堆而不是占用太多内存.

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推送和弹出的运行时太慢之间取得平衡？

Answer 1

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

一个可能的解决方案是使用惰性迭代器（它们也可以在 Py2 中工作，但 Py3 对它们有更好的支持）（它们仅根据需要计算值，而不是一次性计算所有值）。

使您的程序适应生成器应该只需要进行微小的更改，即可在不使用列表的情况下索引生成器（这会抵消惰性的好处）请参阅：Get the nth item of a Generator in Python