如何使下面的 python 程序在大输入时更有效地存储内存

Question

这个程序是为了找到长度为 N 的字符串 S 中至少有 i 个不同字母的子串的数量，其中 1<= i <= 26。

def DistinctChars (N, S):
    # Write your code here
    substrings = " ".join((S[i:j] for i in range(N) for j in range(i+1, N+1)))
    for i in range(1, 27):
        if i==1:
            yield len(substrings.split(" "))
        else:
            yield len([item for item in substrings.split(" ") if len(set(item)) >= i])
    
 
N = int(input())
S = input()
 
out_ = DistinctChars(N, S)
print (' '.join(map(str, out_)))

示例输入

N=4

A=aabc

输出

10 6 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

代码速度快，输出正确。但是无论我怎样尝试，它都超过了分配的250MB内存。

Answer 1

我猜想超出了内存限制，因为所有 substrings 都存储在一个变量中。您可以改为定义一个循环，仅在您的代码中预先计算 len(set(item)) 的值：

def DistinctChars (N, S):
    
    all_U = []
    for i in range(N):
        D = set()
        for j in range(i, N):
            D.add(S[j])
            all_U.append(len(D))
    
    for i in range(1, 27):
        yield sum( 1 for n in all_U if n>=i)

这种方法可以成倍地节省资源，因为所有子字符串都只替换为它们的唯一字符数。

PS。实际上有可能构建一个更高效的算法，其中立即计算具有给定数量的唯一字符的子字符串的数量。最终答案对应于具有相同或更多唯一字符数的条目的累积总和：

def DistinctChars (N, S):
    
    all_N = [0]*27
    for i in range(N):
        D = set()
        for j in range(i, N):
            D.add(S[j])
            all_N[len(D)] += 1
    
    result = []
    s      =  0
    for i in range(26,0,-1):
        s += all_N[i]
        result.append(s)
    return reversed(result)

如何使下面的 python 程序在大输入时更有效地存储内存

How to make the below python program more memory efficient for large input

python-3.x

memory-management

space-complexity

memory-efficient