python - 这个python代码可以更有效吗？

我已经编写了一些代码来查找一个字符串中有多少子字符串是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可以有数千个项（子集）主要的问题是循环。迭代所有项需要花费大量时间。有没有更快或更有效的方法来做到这一点？

最佳答案

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

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获取iterable并构建一个映射，表示每个项出现的次数，因此
Counter(substring)生成表示字符串的anagram类的映射。
viewitems()给出了一组类似于字母的集合：计数对，以及
frozenset将其转换为可用作dict键的不可变集。
这些步骤所花费的时间与子字符串的大小成正比；平均而言，子字符串大约是整个字符串大小的三分之一，因此平均而言，处理每个子字符串需要O(len(x))时间。有O(len(x)**2)子字符串，因此处理所有子字符串需要O(len(x)**3)时间。
如果有具有相同anagram类的x子串，则它们可以以x*(x-1)/2方式配对，因此sum将遍历每个anagram类的出现次数并计算对的数目。这需要O(len(x)**2)时间，因为它必须遍历每个anagram类一次，并且不能有比子字符串更多的anagram类。
总的来说，这个算法需要O(len(x)**3)时间，虽然不是很好，但是比原来的要好得多仍有优化的余地，比如通过利用子串之间的重叠来计算anagram类，或者使用更有效的anagram类表示。

关于python - 这个python代码可以更有效吗？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/30270880/