在Go语言中并行计算不同单词的数量

Question

Jakob Østergaard提出了这个挑战：

编写一个从标准输入读取文本并返回（打印）文本中找到的不同单词总数的程序。

我们如何使用并行编程（最好是Go，但用英语描述也可以）来满足这个挑战？

- Yktula

---

你认为为什么这个问题适合进行有效的并行化处理？ - peterSO

似乎并不太可能通过并行化来提高效率。你需要一个单一的进程将文本分割成标记，这是工作的相当大的一部分，而剩下的任务则是在字典中增加计数，这要么需要锁定，要么需要为每个工作线程保留一个单独的字典并合并它们，这很可能会消除你从分别计数中获得的任何好处。 - Nick Johnson

Tim Bray为处理日志文件创建了一个并行基准测试，使用多种编程语言，称为“Wide Finder”（http://www.tbray.org/ongoing/When/200x/2008/05/01/Wide-Finder-2）。您可能会发现它很相关。处理文件是可以并行完成的，但标准输入可能不行。 - kristianp

Answer 1

有几种可能性，但我猜你的意思是“高效地”？

总体思路是将文本拆分成可管理的块，将这些块堆叠到队列中，并让多个消费者处理这些块。

对我来说，这看起来像一个典型的Map/Reduce应用程序：

          _ Worker_
         /          \
        /            \
Splitter--- Worker ---Aggregator
        \            /
         \_ Worker _/

理想情况下，“多个”队列应该是一个带有多个消费者的单一队列，这样如果一个工作人员放慢了速度，整个过程不会减缓得太多。

我还会使用从Splitter到Workers的信号，让他们知道输入已经完全被消耗，并且他们可以开始将结果发送到Aggregator。

- Matthieu M.

Answer 2

这是 Go 语言解决 Jakob Østergaard's problem 的方案。

/*
    The problem: Write a program that reads text from 
    standard-input, and returns (prints) the total 
    number of distinct words found in the text. 

    C versus C++, Jakob Østergaard, February 24th, 2004
    http://unthought.net/c++/c_vs_c++.html
*/

package main

import (
    "bufio"
    "fmt"
    "os"
    "unicode"
)

func main() {
    rdr := bufio.NewReader(os.Stdin)
    words := make(map[string]bool, 1024*1024)
    word := make([]int, 0, 256)
    for {
        r, n, _ := rdr.ReadRune()
        if unicode.IsSpace(r) || n == 0 {
            if len(word) > 0 {
                words[string(word)] = true
                word = word[:0]
            }
            if n == 0 {
                break
            }
        } else {
            word = append(word, r)
        }
    }
    fmt.Println(len(words))
}

在这个问题以及其他大多数问题中，仅仅添加“并行编程”这个短语是很幼稚的，并期望有所神奇的改进。从流中按顺序读取输入和执行微不足道的计算并不提供任何显著的并行计算机会。

- peterSO

---

(-1) 从标准输入读取只是一个简化，真正的问题是关于并行计算中进行计数去重的算法工作，它在并行计算中具有实际应用和真正的效率。 - Soren