python - 将重复的字符串搜索从二次减少到更快

Question

如果标题不够准确，我们深表歉意。

我有一个程序可以在字符串中搜索元音，但它是通过跨字符串的特定大小的滑动窗口来执行的。我想计算元音的密度。假装我不在乎空格和符号；它只是留在那里。我编码的明显解决方案如下:

s = "Lorem ipsum dolor sit amet, consectetur adipiscing elit ... consequat."
# assume s continues after the "..."
v = "aeiou"
v_dict = {}
max_win_size = 100
if max_win_size > len(s): max_win_size = len(s)

for i in range(1, max_win_size):
    v_dict[i] = {}
    for j in range(0, i+1):
        v_dict[i][j] = 0 # set counts to zero
    for j in range(1, len(s)-i+1):
        s_slice = s[j:j+i].lower()
        v_count = sum([s_slice.count(c) for c in v])
        v_dict[i][v_count] += 1

这最终给出了从 1 到字符串大小的不同滑动窗口中元音的频率。这个程序按我的意愿工作，但问题是它非常慢。它显然是二次方的，我想提高效率，因为随着文本变大，程序花费的时间呈指数增长。问题是我不确定如何将问题空间转化为更高效的算法。

有没有人知道如何做到这一点，比如说，对数线性？

编辑:

我尝试了由 cr1msonB1ade 实现的 Ben Voigt 的答案。它像宣传的那样工作。此外，我想我会在速度声明中加入经验证据。

首先是增加字符串大小的运行时间。这两个函数都是线性执行的，但是使用纯 Python 来实现它的开销会导致线性运行时间的系数显着增加。

其次是增加窗口大小的运行时间。我固定了窗口大小并运行了越来越大的窗口大小。这一次，我的函数的二次率显示出来，而 numpy 累积和函数保持线性。

Answer 1

根据累积计数重写算法。

位置i和j(含)之间出现的次数就是cumul_count(j) - cumul_count(i-1)，并且所需的计算不会随着窗口大小的增加而增加。