Golang实现超快字符统计：海量字符串处理仅需2秒

Golang实现超快字符统计：海量字符串处理仅需2秒 你好，我刚接触Go。过去两年一直在学习Go，只是跟着教程写一些用完即弃的代码。虽然还没在生产环境中使用，但我在职业生涯中已处于高级阶段，并计划全职转向Go。我此前使用Nodejs大约5年，编写生产代码。

我想在一些有趣的在线谜题/挑战练习中测试Go，将其作为我的首选工具。我喜欢Go的一点是，它的运行和编译方式几乎像C语言一样，而且速度非常快。但我卡在了一个点上，真的需要一些帮助。我有一段代码已经相当快了，但我需要它更快。这涉及到拆分字符串，甚至是一些很长的字符串，例如：

DXqzxJrCnsAUSmkUkQCedQTcyYHIUPixMbyLKQoAKOuDDgxNWBRCrmErkNafCKeQnfBYxPahgumJclYAMPcFbizNVbuxnbnBgrbDIbmqXbZZOzzdQeItmJhiKdFYevbMMcRWdGnajOZXoaaeGlyTUhbhkifRfgftKzqNfDNQToNhQqmxBmqXtTefDLWJtEEddUsiZfYTVnCMDqjGCbgxUMDZazkVdPZglTQlZqGUEKiJbrSfUYDOKgqKhAGNphTBCmoBCwYIggUJaMPUmUlyadLhDTwTCqWeeMiiigtQOncqBtNNnANPDyygrVBTNxYRjIBTOUmehoXkHmXwMLlpLlXdgbyvyYmkGOdWIpDsfACMMcKapxRaJOFrPeNQcZClphhAZKueMWtaAdaPBtQMKvdbbQtGsVRjdAJcNFgzezcEfEWiYoUIlXlnqFTIAKtDMFhzkoZopDvWhreHFARQadFqIyAiKToxyXWllxzdCUBKNGrUIjLImqAwragDwWawUzHHyhKbDOnTuENEpandTpzkSipoeqKYrUGrbSsgGFBCMphDRWHKlIwdQMTVEgvxaDODwJlEQNhCEQIvMpgzzefqQANWGKtGoiL

将其拆分为所有可能的字符串组合，并在每个子字符串中查找一组字符的出现次数。如果你好奇的话，结果是7811003。

正如我所说，这个程序已经足够快了，但有没有可能让它更快呢？以下是伪代码：

func(words []string){
    var charset = []string{.........}
    count := 0
    for word :=  range words{
        for _, char := range charset{
             count = count + strings.Count(word, char)
        }
    }
}

上面的代码部分我认为是性能瓶颈。为了确保能计算更大的值，我将‘count’变量作为big.Int来处理。我有大约10个输入字符串需要在1.1秒内处理完，并且内存使用量限制在64KB，因为这是C语言的基准。


更多关于Golang实现超快字符统计：海量字符串处理仅需2秒的实战教程也可以访问 https://www.itying.com/category-94-b0.html

2 回复

这段代码可以通过改变算法进行优化。

如果我的理解正确，您想要计算字符集中字符在输入单词中出现的总次数。

您可以遍历每个单词的每个字符，并在一个以字符集中字符为键的映射中递增一个整数计数器。完成此操作后，您的最终计数就是该映射中所有整数值的总和。

您不需要使用 big.Int，因为 int 是 64 位的，而且计数值不会超过单词中的字母数量。使用 big.Int 比使用 int 要慢得多。

如果字符集仅限于 ASCII 字母，您可以使用一个长度为 256 的整数切片，并使用字母的 ASCII 码作为切片的索引。然后，对于每个单词的每个字母，递增切片中对应的整数。完成后，对字符集中字符对应的整数值进行求和。这将是最快的方法。

更多关于Golang实现超快字符统计：海量字符串处理仅需2秒的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


package main

import (
	"strings"
	"sync/atomic"
)

func optimizedCount(words []string, charset []string) int64 {
	var total int64
	charsetBytes := make([]byte, len(charset))
	for i, s := range charset {
		charsetBytes[i] = s[0]
	}

	for _, word := range words {
		wordBytes := []byte(word)
		wordLen := len(wordBytes)
		
		// 预计算字符集位图
		var charSetBitmap [256]bool
		for _, b := range charsetBytes {
			charSetBitmap[b] = true
		}
		
		// 并行处理
		var localCount int64
		const batchSize = 256
		
		for i := 0; i < wordLen; i += batchSize {
			end := i + batchSize
			if end > wordLen {
				end = wordLen
			}
			
			chunk := wordBytes[i:end]
			for _, b := range chunk {
				if charSetBitmap[b] {
					atomic.AddInt64(&localCount, 1)
				}
			}
		}
		
		atomic.AddInt64(&total, localCount)
	}
	
	return total
}

// 更快的版本，使用SIMD思想
func simdStyleCount(words []string, charset string) int64 {
	var total int64
	charMap := [256]uint8{}
	for i := 0; i < len(charset); i++ {
		charMap[charset[i]] = 1
	}
	
	for _, word := range words {
		n := len(word)
		wordPtr := &word[0]
		
		var count int64
		// 手动展开循环
		i := 0
		for ; i+7 < n; i += 8 {
			count += int64(charMap[wordPtr[i]] +
				charMap[wordPtr[i+1]] +
				charMap[wordPtr[i+2]] +
				charMap[wordPtr[i+3]] +
				charMap[wordPtr[i+4]] +
				charMap[wordPtr[i+5]] +
				charMap[wordPtr[i+6]] +
				charMap[wordPtr[i+7]])
		}
		
		for ; i < n; i++ {
			count += int64(charMap[wordPtr[i]])
		}
		
		total += count
	}
	
	return total
}

// 使用strings.Count但优化的版本
func optimizedStringsCount(words []string, charset []string) int64 {
	var total int64
	// 将字符集转换为单个字符串用于strings.Count
	charsetStr := strings.Join(charset, "")
	
	for _, word := range words {
		// 一次性统计所有字符
		for i := 0; i < len(charsetStr); i++ {
			total += int64(strings.Count(word, charsetStr[i:i+1]))
		}
	}
	
	return total
}
回到顶部