这个python代码可以更高效吗？

Question

我编写了一些代码来查找字符串中有多少个子字符串是anagram对.要找到的函数anagram(anagramSolution)具有复杂度O(N).子串函数的复杂度小于N平方.但是,这里的代码就是问题所在.可以更优化吗？

for i in range(T):
    x = raw_input()
    alist = get_all_substrings(x)

    for k, j in itertools.combinations(alist,2):
        if(len(k) == len(j)):
            if(anagramSolution(k,j)):
                counter +=1

    counterlist.append(counter)
    counter = 0

该alist可以有上千项(子集)的.主要问题是循环.迭代所有项目需要花费大量时间.有没有更快或更有效的方法来做到这一点？

Answer 1

将字符串的anagram类定义为每个字母在字符串中出现的次数的计数集.例如,'banana'有anagram类a: 3, b: 1, n: 2.如果它们具有相同的anagram类,则两个字符串是彼此的字谜.我们可以计算每个anagram类中字符串的子串数,然后通过计算(n choose 2)每个具有n个子串的anagram类来计算对的数量:

from collections import Counter

anagram_class_counts = Counter()

for substring in get_all_substrings(x):
    anagram_class_counts[frozenset(Counter(substring).viewitems())] += 1

anagram_pair_count = sum(x*(x-1)/2 for x in anagram_class_counts.viewvalues())

frozenset(Counter(substring).viewitems()) 构建字符串的anagram类的可散列表示.

• Counter 采用迭代并构建一个映射,表示每个项目出现的次数,所以
• Counter(substring) 构建表示字符串的anagram类的映射.
• viewitems() 给出一组类似于字母的集合:计数对,和
• frozenset 把它变成一个可以用作dict键的不可变集合.

这些步骤共同花费时间与子串的大小成比例; 平均而言,子串大约是整个字符串大小的三分之一,因此平均而言,处理每个子字符串需要O(len(x))时间.有O(len(x)**2)子串,因此处理所有子串需要O(len(x)**3)时间.

如果存在x具有相同anagram类的子串,则它们可以以方式配对x*(x-1)/2,因此sum遍历每个anagram类的出现次数并计算对的数量.这需要O(len(x)**2)时间,因为它必须经过一次每个anagram类,并且不能有比字串更多的anagram类.

总的来说,这个算法需要O(len(x)**3)时间,这不是很好,但它比原来要好很多.仍然有优化这一点的空间,例如通过利用子串之间的重叠或使用更有效的anagram类表示来计算anagram类.