go - 将多个映射组合成一个映射，其给定键的值是组合映射中键值的总和

Question

我编写了一个程序，用于识别文本文档中所有不同的单词并计算每个单词出现的次数。为了提高我的程序的性能，我试图将单词计数分解为多个可以并行运行的 goroutine。

最初，我尝试使用通过引用传递给每个 goroutine 的单个映射，其中每个 goroutine 都会计算文档的一部分中的单词。这引起了 panic ，因为该程序试图同时从多个 goroutine 写入同一个映射。为了解决这个问题，我创建了一个互斥锁来防止多个 goroutines 同时写入 map 。此时，程序按预期运行，但与 WordCount 函数的原始顺序实现相比没有性能差异。转念一想，这并不奇怪，因为互斥量会强制其他 goroutine 在写入映射之前等待，从而阻止并行计算。

下面是使用互斥量来避免所描述的运行时 panic 的代码，但也无法并行计算单词数。

func WordCount(words []string, startWord int, endWord int, freqs map[string]int, waitGroup *sync.WaitGroup, mutex *sync.Mutex) {
    mutex.Lock()
    for i := startWord; i < endWord; i++ {
        word := words[i]
        freqs[word]++
    }
    mutex.Unlock()
    waitGroup.Done()
}

func ParallelWordCount(text string) map[string]int {
    // Split text into string array of the words in text.
    text = strings.ToLower(text)
    text = strings.ReplaceAll(text, ",", "")
    text = strings.ReplaceAll(text, ".", "")
    words := strings.Fields(text)
    length := len(words)

    freqs := make(map[string]int)

    var mutex sync.Mutex
    var waitGroup sync.WaitGroup
    waitGroup.Add(2)
    defer waitGroup.Wait()

    threads := 2
    wordsPerThread := length / threads // always rounds down
    wordsInLastThread := length - (threads-1)*wordsPerThread
    startWord := -wordsPerThread
    var endWord int
    for i := 1; i <= threads; i++ {
        if i < threads {
            startWord += wordsPerThread * i
            endWord += wordsPerThread * i
        } else {
            startWord += wordsInLastThread
            endWord += wordsInLastThread
        }
        go WordCount(words, startWord, endWord, freqs, &waitGroup, &mutex)
    }

    return freqs
}

我相信，如果我为每个 goroutine 创建一个本地词频图，并最终将本地频率图与整个文本文件的词数统计结合成一个图，我相信我可以实现并行字数统计。我目前面临的问题是如何合并局部频率图。具体来说，我需要知道如何将多个映射组合成一个映射，其给定键的值是要组合的映射中键值的总和。

为了阐明我正在尝试做的事情的基本逻辑，我提供了以下示例。 ConcurrentSum 函数通过同时计算数组的下半部分和上半部分来返回数组中元素的总和。就我而言，我想并行计算文本文件不同部分的字数，并最终将字数组合成一个代表整个文档的字数统计图。

func sum(a []int, res chan<- int) {
    var sum int
    for i := 0; i < len(a); i++ {
        sum += a[i]
    }
    res <- sum
}

// concurrently sum the array a.
func ConcurrentSum(a []int) int {
    n := len(a)
    ch := make(chan int)
    go sum(a[:n/2], ch)
    go sum(a[n/2:], ch)
    return <-ch + <-ch
}

Answer 1

我相信您可以创建一组 map ，每个 map 用于每个流程，然后使用列表读取每个 map 以跟踪您已经计算过的单词。假设每个单词都是计算次数的关键，看起来就是这样。 考虑到并发方面，这里的并行处理可能不是最佳选择，因为所有内容都需要保持独立才能真正提高性能。如果您有存储空间，那么您肯定可以使用列表并从 map 的集成中获得最坏情况下的 O(N) 效率。您需要将 map 的集成保持在单个线程或单个进程中。