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

Question

我正在尝试提高个人技能以解决黑客等级挑战：有一串小写英文字母 s 被无限次重复。给定一个整数 n，找出并打印无限字符串的前 n 个字母中字母 a 的个数。1<=s<=100 && 1<=n<=10^12非常天真，我虽然这段代码会很好：fs := strings.Repeat(s, int(n)) // full stringss := fs[:n]                    // sub stringfmt.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 n

repeats := 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{ 

answer = int64((aCount * repeats))

}

 

return answer

可能还有其他方法，但这就是我想到的。

Answer 2

正如您所发现的，如果您实际生成字符串，您最终将在 RAM 中拥有巨大的内存块。

表示“传入字节的大序列”的一种常见方法是将其实现为io.Reader（您可以将其视为字节流），并让您的代码运行一个r.Read(buff)循环。

鉴于您提到的练习的具体情况（固定字符串重复n次数），特定字母的出现次数也可以直接根据该字母在 中出现的次数s以及更多内容（我会让您弄清楚应该做哪些乘法和计数）。

如何实现一个重复字符串而不分配 10^12 倍字符串的阅读器？

请注意，在实现该.Read()方法时，调用者已经分配了他的缓冲区。您不需要在内存中重复您的字符串，您只需要用正确的值填充缓冲区——例如，将数据逐字节复制到缓冲区中。

这是一种方法：

type RepeatReader struct {

    str   string

    count int

}

func (r *RepeatReader) Read(p []byte) (int, error) {

    if r.count == 0 {

        return 0, io.EOF

    }

    // at each iteration, pos will hold the number of bytes copied so far

    var pos = 0

    for r.count > 0 && pos < len(p) {

        // to copy slices over, you can use the built-in 'copy' method

        // at each iteration, you need to write bytes *after* the ones you have already copied,

        // hence the "p[pos:]"

        n := copy(p[pos:], r.str)

        // update the amount of copied bytes

        pos += n

        // bad computation for this first example :

        // I decrement one complete count, even if str was only partially copied

        r.count--

    }

    return pos, nil

}

https://go.dev/play/p/QyFQ-3NzUDV

要获得完整、正确的实施，您还需要跟踪下次.Read()调用时需要开始的偏移量：

type RepeatReader struct {

    str    string

    count  int

    offset int

}

func (r *RepeatReader) Read(p []byte) (int, error) {

    if r.count == 0 {

        return 0, io.EOF

    }

    var pos = 0

    for r.count > 0 && pos < len(p) {

        // when copying over to p, you should start at r.offset :

        n := copy(p[pos:], r.str[r.offset:])

        pos += n

        // update r.offset :

        r.offset += n

        // if one full copy of str has been issued, decrement 'count' and reset 'offset' to 0

        if r.offset == len(r.str) {

            r.count--

            r.offset = 0

        }

    }

    return pos, nil

}

https://go.dev/play/p/YapRuioQcOz

您现在可以a在遍历此 Reader 时计算 s。