python - 这段 python 代码可以更高效吗？

Question

我已经编写了一些代码来查找一个字符串中有多少个子字符串是变位词对。查找 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

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

Answer 1

将字符串的anagram 类 定义为每个字母在字符串中出现次数的计数集。例如，'banana' 具有变位词类 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 采用一个可迭代对象并构建一个表示每个项目出现次数的映射，因此
• Counter(substring) 构建表示字符串的 Anagram 类的映射。
• viewitems() 给出一组类似字母的集合:计数对，以及
• frozenset 将其转换为可用作字典键的不可变集。

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

如果有 x 个具有相同变位词类的子串，它们可以按 x*(x-1)/2 的方式配对，所以 sum 遍历每个 anagram 类的出现次数并计算对数。这需要 O(len(x)**2) 时间，因为它必须通过每个 anagram 类一次，并且不能有比子字符串更多的 anagram 类。

总的来说，这个算法花费了 O(len(x)**3) 时间，虽然不是很好，但比原来的要好很多。这仍有优化的空间，例如通过利用子字符串之间重叠的方式计算 anagram 类，或使用更有效的 anagram 类表示。