如何操作很长的字符串以避免 golang 内存不足

Question

我正在尝试提高个人技能以解决黑客等级挑战：

有一串小写英文字母 s 被无限次重复。给定一个整数 n，找出并打印无限字符串的前 n 个字母中字母 a 的个数。

1<=s<=100 && 1<=n<=10^12

非常天真，我虽然这段代码会很好：

fs := strings.Repeat(s, int(n)) // full string

ss := fs[:n]                    // sub string

fmt.Println(strings.Count(ss, "a"))

显然我爆炸了内存并得到了一个：“内存不足”。

我从来没有遇到过这种问题，而且我对如何处理它一无所知。如何操作很长的字符串以避免内存不足？

Answer 1

我希望这会有所帮助，您不必通过遍历字符串来实际计数。这是天真的做法。你需要使用一些基本的算法来得到答案而不会耗尽内存，我希望这些评论对你有所帮助。var answer int64// 1st figure out how many a's are present in s.aCount := int64(strings.Count(s, "a"))// How many times will s repeat in its entirety if it had to be of length nrepeats := n / int64(len(s))remainder := n % int64(len(s))// If n/len(s) is not perfectly divisible, it means there has to be a remainder, check if that's the case.// If s is of length 5 and the value of n = 22, then the first 2 characters of s would repeat an extra time.if remainder > 0{aCountInRemainder := strings.Count(s[:remainder], "a")answer = int64((aCount * repeats) + int64(aCountInRemainder))} else{&nbsp;answer = int64((aCount * repeats))}&nbsp;return answer可能还有其他方法，但这就是我想到的。

Answer 2

正如您所发现的，如果您实际生成字符串，您最终将在 RAM 中拥有巨大的内存块。表示“传入字节的大序列”的一种常见方法是将其实现为io.Reader（您可以将其视为字节流），并让您的代码运行一个r.Read(buff)循环。鉴于您提到的练习的具体情况（固定字符串重复n次数），特定字母的出现次数也可以直接根据该字母在 中出现的次数s以及更多内容（我会让您弄清楚应该做哪些乘法和计数）。如何实现一个重复字符串而不分配 10^12 倍字符串的阅读器？请注意，在实现该.Read()方法时，调用者已经分配了他的缓冲区。您不需要在内存中重复您的字符串，您只需要用正确的值填充缓冲区——例如，将数据逐字节复制到缓冲区中。这是一种方法：type RepeatReader struct {&nbsp; &nbsp; str&nbsp; &nbsp;string&nbsp; &nbsp; count int}func (r *RepeatReader) Read(p []byte) (int, error) {&nbsp; &nbsp; if r.count == 0 {&nbsp; &nbsp; &nbsp; &nbsp; return 0, io.EOF&nbsp; &nbsp; }&nbsp; &nbsp; // at each iteration, pos will hold the number of bytes copied so far&nbsp; &nbsp; var pos = 0&nbsp; &nbsp; for r.count > 0 && pos < len(p) {&nbsp; &nbsp; &nbsp; &nbsp; // to copy slices over, you can use the built-in 'copy' method&nbsp; &nbsp; &nbsp; &nbsp; // at each iteration, you need to write bytes *after* the ones you have already copied,&nbsp; &nbsp; &nbsp; &nbsp; // hence the "p[pos:]"&nbsp; &nbsp; &nbsp; &nbsp; n := copy(p[pos:], r.str)&nbsp; &nbsp; &nbsp; &nbsp; // update the amount of copied bytes&nbsp; &nbsp; &nbsp; &nbsp; pos += n&nbsp; &nbsp; &nbsp; &nbsp; // bad computation for this first example :&nbsp; &nbsp; &nbsp; &nbsp; // I decrement one complete count, even if str was only partially copied&nbsp; &nbsp; &nbsp; &nbsp; r.count--&nbsp; &nbsp; }&nbsp; &nbsp; return pos, nil}https://go.dev/play/p/QyFQ-3NzUDV要获得完整、正确的实施，您还需要跟踪下次.Read()调用时需要开始的偏移量：type RepeatReader struct {&nbsp; &nbsp; str&nbsp; &nbsp; string&nbsp; &nbsp; count&nbsp; int&nbsp; &nbsp; offset int}func (r *RepeatReader) Read(p []byte) (int, error) {&nbsp; &nbsp; if r.count == 0 {&nbsp; &nbsp; &nbsp; &nbsp; return 0, io.EOF&nbsp; &nbsp; }&nbsp; &nbsp; var pos = 0&nbsp; &nbsp; for r.count > 0 && pos < len(p) {&nbsp; &nbsp; &nbsp; &nbsp; // when copying over to p, you should start at r.offset :&nbsp; &nbsp; &nbsp; &nbsp; n := copy(p[pos:], r.str[r.offset:])&nbsp; &nbsp; &nbsp; &nbsp; pos += n&nbsp; &nbsp; &nbsp; &nbsp; // update r.offset :&nbsp; &nbsp; &nbsp; &nbsp; r.offset += n&nbsp; &nbsp; &nbsp; &nbsp; // if one full copy of str has been issued, decrement 'count' and reset 'offset' to 0&nbsp; &nbsp; &nbsp; &nbsp; if r.offset == len(r.str) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r.count--&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; r.offset = 0&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return pos, nil}https://go.dev/play/p/YapRuioQcOz您现在可以a在遍历此 Reader 时计算 s。