python - 在制作大量重复子字符串时如何避免 MemoryError？

Question

我正在尝试编写一个程序来计算给定字符串 s 中字符 'a' 的出现次数，只考虑第一个 字符串的 n 个字符。如果字符串的长度小于数字 n，例如 s = "abca" 和 n = 10，则 s 应该变成 "abcaabcaab"。我编写的算法适用于小的 n，但是当我尝试更大的数字时，它会给我一个内存错误。我该如何避免？

s = input ()
n = int (input ())
def num_occur (s,n):
  flag = False
  while not flag:
    if len(s)==(n-1):
      s = s + s[0]
      flag = True
    elif len(s)<n:
      s = s * int(n / len(s))
    elif len(s)>n:
      s = s[0:n]
      flag = True
    else:
      flag = True
  occ = 0
  for ind in range (0, len(s)):
    if s[ind] == "a":
      occ += 1
  return occ

print (num_occur(s,n))

Answer 1

实际上不需要将字符串的多个副本相互链接，这是导致内存错误的原因。相反，您可以只检查索引对字符串长度的模数:

def count(s, n, c):
    return sum(1 for i in range(n) if s[i % len(s)] == c)

>>> count("abca", 10, "a")
5

然而，虽然这是内存高效的，但如果 n 比字符串的长度大很多倍，它仍然会做很多不必要的工作。相反，您可以只检查字符在字符串中出现了多少次，将其乘以字符串必须重复的次数，然后加上其余的计数。

def count_2(s, n, c):
    return s.count(c) * (n // len(s)) + s[:n % len(s)].count(c)

>>> count_2("abca", 12**34, "a")
2461117621476013352018556621561004032