python - 我的递归 python 代码中的瓶颈

Question

我使用递归编写了以下代码来执行CYK 算法，以便语法G可以生成任何具有相同数量的a' 后跟任意数量b' 的单词，但由于某种原因它非常慢，不知道为什么？当我使用 s2 时，它可以工作，但如果我使用 s1 ，它是一个较长的字符串，它需要永远。谁能告诉我，因为我不知道瓶颈在哪里？

def fn(G, w, i, j, T):
    if T[i, j]:
        print '1'
        return T[i, j]
    elif i == j:
        for r in G:
            print '2'
            if r.endswith(w[i]) and r[0] not in T[i, j]:    
                print '3'
                T[i, j].append(r[0])
    else:
        print '4'
        for k in range(i, j):
            print '5'
            for a in fn(G, w, i, k, T):
                print '6'
                for b in fn(G, w, k+1, j, T):
                    print '7'
                    for r in G:
                        print '8'
                        if r.endswith(a+b) and r[0] not in T[i, j]:
                            print '9'
                            T[i, j].append(r[0])
    return T[i, j]


def fnmain(G, S, w):
    dict = {}
    for x in range(0, len(w)):
        for y in range(x, len(w)):
            dict[x,y] = []
    print dict        
    v = fn(G, w, 0, len(w) - 1, dict)
    print (w, v)
    if S in v:
        print ("T")
        return True
    else:
        print ("F")
        return False

G = ["S->AB", "S->XB", "T->AB", "T->XB", "X->AT", "A->a", "B->b"]

s1 = "aaaaabbbbb"
s1 = "aaaaaaaaabbbbbbbbb"

fnmain(G, "S", s1)

我已cProfile按照@wwii 的建议使用，结果如下：

当 s1 = "aaaaabbbbb" 当 s1 = "aaaaaaaaabbbbbbbbbb"