[解決済み] Pythonのメモリエラー

質問

Traceback (most recent call last):
File "/run-1341144766-1067082874/solution.py", line 27, in 
main()
File "/run-1341144766-1067082874/solution.py", line 11, in main
if len(s[i:j+1]) > 0:
MemoryError
Error in sys.excepthook:
Traceback (most recent call last):
File "/usr/lib/python2.7/dist-packages/apport_python_hook.py", line 64, in apport_excepthook
from apport.fileutils import likely_packaged, get_recent_crashes
File "/usr/lib/python2.7/dist-packages/apport/__init__.py", line 1, in 
from apport.report import Report
MemoryError

Original exception was:
Traceback (most recent call last):
File "/run-1341144766-1067082874/solution.py", line 27, in 
main()
File "/run-1341144766-1067082874/solution.py", line 11, in main
if len(s[i:j+1]) > 0:
MemoryError

以下のプログラムを実行しようとしたところ、上記のエラーが表示されました。どなたか、メモリーエラーとは何か、この問題を克服する方法を説明していただけませんか？. このプログラムは、文字列を入力として受け取り、すべての可能なサブ文字列を見つけ、その中から集合（辞書順）を作成します。そして、ユーザーが尋ねたそれぞれのインデックスの値を表示します。

def main():
    no_str = int(raw_input())
    sub_strings= []
    for k in xrange(0,no_str):
        s = raw_input()
        a=len(s)
        for i in xrange(0, a):
            for j in xrange(0, a):
                if j >= i:
                    if len(s[i:j+1]) > 0:
                        sub_strings.append(s[i:j+1])
    sub_strings = list(set(sub_strings))
    sub_strings.sort()
    queries= int(raw_input())
    resul = []
    for i in xrange(0,queries):
        resul.append(int(raw_input()))
    for p in resul:
        try:
            print sub_strings[p-1]
        except IndexError:
            print 'INVALID'


if __name__ == "__main__":
   main()

解決方法は？

こちらはこちらで。

s = raw_input()
a=len(s)
for i in xrange(0, a):
    for j in xrange(0, a):
        if j >= i:
            if len(s[i:j+1]) > 0:
                sub_strings.append(s[i:j+1])

は、大きな文字列に対して非常に非効率で高価なようです。

より良い方法

for i in xrange(0, a):
    for j in xrange(i, a): # ensures that j >= i, no test required
        part = buffer(s, i, j+1-i) # don't duplicate data
        if len(part) > 0:
            sub_Strings.append(part)

バッファオブジェクトは、元の文字列への参照と、開始と長さの属性を保持します。こうすることで、不必要なデータの重複が発生しません。

長さの文字列 l は l*l/2 平均的な長さのサブストリング l/2 ということで、メモリ消費量はおおよそ l*l*l/4 . バッファを使えば、もっと小さくなります。

なお buffer() は 2.x にしか存在しませんが、3.x では memoryview() というように、微妙に使い勝手が違う。

さらに良いのは、インデックスを計算し、必要に応じて部分文字列を切り出すことです。