这个 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

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

Answer 1

我不认为你可以完全避免这个问题的迭代，但至少你可以将手头的任务缩小 O(2^nC2/2^n) 倍。

您希望在开始迭代之前将子字符串分组为各自的长度，因为您要添加更多的案例来检查。

当前方法比较一组中的所有对，需要 2^nC2 = 次比较。这是一个巨大的数字(2^n)! / ((2^n-2)! * 2!)。

如果我们先列出长度为 1-n 的子串，然后进行比较，我们花费：

2^n 次操作遍历所有子字符串
nC2 操作遍历长度为 1 的子串
...

也就是说，我们做得更好。

编辑：我意识到字符串不是集合，子字符串也不是子集，但这只会影响子集的数量，不会影响主要参数。

Answer 2

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

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()) 构建字符串变位词的可哈希表示 class.

Counter 采用一个可迭代对象并构建一个表示每个项目出现次数的映射，因此
Counter(substring) 构建表示字符串变位词的映射 class.
viewitems() 给出了一组类似字母的集合：计数对，并且
frozenset 将其转换为可用作字典键的不可变集。

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

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

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

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

Can this python code be more efficient?

python

optimization

for-loop

time-complexity

itertools